Předmět ICT Theory (EIE28E)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu EIE28E - ICT Theory, Provozně ekonomická fakulta, Česká zemědělská univerzita v Praze (ČZU).

Materiál	Typ	Datum	Počet stažení

Osnova

PřednáškaÚvodRelace, operace, struktury, algebryGrafyKonečné automatyZásobníkové automatyAplikace konečných a zásobníkových automatůFormální jazyky a gramatikySyntaktická analýzaPřekladačeJazyk PrologAlgoritmizace v ProloguAnalýza algoritmů - lineární algebra, optimalizační úlohyCvičeníVýrokový počet, booleovská algebra - formule, ekvivalence, logický důsledek, DNF a KNFRelace, vlastnosti relací, uspořádáníKonečné automatyGramatiky, jazyky a překladačeJazyk PrologRekurze, seznamy, operace se seznamy v PROLOGu

Získané způsobilosti

Znalosti:Absolventi získají znalosti teoretických a matematických disciplin, na kterých je založena současná informatika. Konkrétně získají přehled o matematické logice, výrokovém a predikátovém poštu, víceznačných logikách a formálním odvozování důsledku. Dále základní znalosti o teorii množin, včetně fuzzy množin, o relacích, operacích na množinách a o teorii grafu. Znalosti teorie formálních jazyků a gramatik a matematických modelů výpočtu (konečný automat, zásobníkový automat, Turingůc stroj, RASP stroj) a o teorii vyčíslitelnosti. Formální i praktické znalosti z teorie výpčetní složitoasti, včetně aplikace na základní typy úloh (vyhledávání v datech, řazení dat, optimalizační úlohy na grafech). Získají znalosti základních principů návrhu účinných algoritmů (metoda divide et impera, gradientní metody, dynamické programování). Dále pak znlosti o vybraných typech heuristických postupů (prořezávání stromů, evoluční a genetické algoritmy, neuronové sítě).Dovednosti:Absolventi získají dovednost identifikace teoretických základů na kterých jsou založeny postupu uplatňované v současné informatice. Získají dovednost přesného odvozování důsledků, včetně užití principů logického jazyka PROLOG pro řešení úloh na základě rekurze a prohledávání stavového prostoru s návratem (backtracking). Získají dovednost exaktní formulace problémů a vyhledávání osvědčených postupů pro jejich řešení. Získají dovednost nabrhovat pro řešení obtížných úloh algoritmy s minimálními nároky na čas výpočtu a paměťový prostor. Pro úlohy u kterých není přijatelně výpočetně složitý algioritmus zbnám získají dovednost navrhnout účinný heuristický postup umožňující nalézt přibližné řešení problému.Kompetence - komunikace:Absolventi mají kompetenci pro oboustrannou odbornou komunikaci s pracovníky v oblasti matematiky a teoretické informatiky. Získají "společný jazyk", které jim umožní formulovat požadavky pro teoretiky a využít teoretické výsledky jejich práce.Kompetence - úsudek:Absolveni mají kompetenci exaktní formulace problémů na základě prostředků dvouhodnotové i vícehodnotové logiky a logického odvozávání důsledků ve formalizovaném prostředí. Mají kompetenci pro užití formálních model§ů výpočtu a pro hodnocení algoritmu na základě jejich výopočetní složitosti, pro návrh algoritmů s vyhovující složitostí a heuristik pro případ, kdy takový algoritmus neexistuje.

Literatura

ZákladníVaníček, J. Mathematical theory of programs. Part 1 Computational models. Praha ČZU, PEF, 2004WIRTH, N. Algoritms + data structures = programs. Prentice Hall, Englewood Cliffs N.J., 1976Copi, I.M. Introduction to logic. New York MacMillan Publishing Company, 1961, ISBN 0-02-325020-8DoporučenáHehner, E.C.R. The logic of programming, Englewood Cliffs Prentice-Hall Inc. Prentice-Hall International series in computer science, 1984, ISBN 0-3-539966-1Manna Z. Mathematical theory of computation. McGraw-Hill book company, 1974, ISBN 0-07-039810-7Davis M.D, Sigal, R., Weyuker, E. J. and Davis, M.D. Computability, Complexity and Languages. Fundamental of Theoretical Computer Sci., 1983, 86, ISBN 0-12-206380-5Weiss, M.A. Data structures and algorithm analysis in C. Menlo Park Addison-Wesley, 1997, ISBN 0-201-49840-5Kozen, D.C. The Design and Analysis of Algorithms. New York Springer-Verlag, 1991, 320 pages, ISBN 0-387-97687-6Hopcroft, J.E. and Ullman, J.D. Formal languages and their relations to automata. Adison-Wesley Publishing Company.

Požadavky

Základy matematiky na bakalářské úrovni oboru Informatika

Garant

doc. Ing. Vojtěch Merunka, Ph.D.