Předmět Teorie ICT (EIE76E)

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 EIE76E - Teorie ICT, Provozně ekonomická fakulta, Česká zemědělská univerzita v Praze (ČZU).

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

Cíl

Cíl předmětu je vybavit studenty základními znalostmi a dovednostmi z oblasti aplikované matematiky, aplikované logiky, algoritmizace a teorie výpočtu, nezbytnými pro porozumění dalším specializačním předmětům v magisterském studijním programu Informatika. Vzhledem k tomu, že návazný magisterský obor mohou studovat i uchazeči z různým předchozím vzděláním bakalářského stupně, je předmět i prostředkem k sjednocení základů pro další studium. V předmětu se studenti seznámí se základy teorie množin, pojmem mlhavé(fuzzy) množiny, pojmem relace a mlhavé relace a s pojmem operace. Seznámí se s pojmy datové zprávy, informace a znalosti. Relace budou aplikovány na různé typy uspořádání jako preferenční relace i na vyjádření informace daty v databázových strukturách. Seznámí se s problematikou popisu atributů reálného světa čísly měřením, representací těchto informací daty a s možnostmi interpretace výsledků získaných výpočtem z těchto dat jako smysluplných výroků o reálném světě. Seznámí se s výrokovým a predikátorovým počtem a s procesem odvozování důsledků v dané teorii. Seznámí se s orientovanými i neorientovanými grafy a s jejich užitím pro popis procesu a algoritmu, v teorii rozhodování, pro problémy plánování procesů a pro řešení vybraných optimalizačních úloh pro ekonomické aplikace. Seznámí se dále s pojmem formálního jazyka, formálních gramatik a s matematickými modely výpočtu. Součástí předmětu bude i studium algoritmické rozhodnutelnosti a přečíslitelnosti jazyka a problému na formálních modelech i z praktického pohledu. Pozornost bude věnována problematice výpočetní složitosti algoritmů. Studenti budou seznámeni s problematikou NP-těžkých a NP-úplných problémů a s možnostmi alternativních heuristických přístupů k jejich řešení. Stručně se seznámí i s algoritmy pro klasifikaci, rozpoznání vzorů a shlukovou analýzu.

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ův stroj, RASP stroj) a o teorii vyčíslitelnosti. Formální i praktické znalosti z teorie výpočetní složitosti, 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 znalosti 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 navrhovat 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ý algoritmus zná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:Absolventi mají kompetenci exaktní formulace problémů na základě prostředků dvouhodnotové i vícehodnotové logiky a logického odvozová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ýpoč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. a kol Teoretické základy informatiky, Kemberg Publ. Praha, 2007, 432 stran, ISBN 978-80-903962-4-1Merunka, V. Datové modelování, Alfa, Praha, 2005.DoporučenáKolář, J. Jazyky pro umělou inteligenci. Praha ČVUT, FEL, 1994, 333 stran, ISBN 80-01-01107-0Demlová, M. Mathematical logic. Praha Vydavatelství ČVUT, 1999, 165 pages, ISBN 80-01-2011-8Hehner, E.C.R. The logic of programming, Englewood Cliffs Prentice-Hall Inc. Prentice-Hall International series in computer science, 1984Sochor, A. Klasická matematická logika. Praha Karolinum, 2001, 401 stran, ISBN 80-246-0218-0WIRTH, N. Algoritms + data structures = programs . Prentice Hall, Englewood Cliffs N.J., 1976Copi, I.M. Introduction to logic. New York MacMillan Publishing Company, 1961, 617 pagers, ISBN 0-02-325020-8Chytil, M. Automaty a gramatiky, Praha SNTL, 1984, 331 stran, ISBN 04-012-84Hopcroft, J.E. and Ullman, J.D. Formálné jazyky a automaty. Bratislava Allfa, 1978, ISBN 63-096-78Manna Z. Matematická teorie programů. Praha SNTL, 1981, 467 stran, ISBN 04-031-81Weiss, M.A. Data structures and algorithm analysis in C. Menlo Park Addison-Wesley, 1997, ISBN 0-201-49840-5Davis, M.D; Sigal, R and Weyuaker, E.J. Computability, Complexity and Languages. Fundamentals of Theoretical Computer Science, Second EditionSAn Diego, Accademic Press, 1994

Požadavky

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

Garant

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