4EK112 — Matematické základy informatiky

O předmětu

Předmět má seznámit studenty informatiky s matematickými aplikacemi v informatice, zejména s teorií grafů a souvislosti s datovými strukturami, vyhledávacími metodami v databázích, výrokovým a predikátovým počtem a problémem vyhodnocování logických výrazů, teorií formálních jazyků a podstaty překladačů, problémy spojenými s ukládání čísel a numerickou stabilitou algoritmů a výpočetní složitostí algoritmů a úloh. Ve cvičení budou témata prakticky procvičena na implementacích a s využitím "meta-kódu".

Co se naučíš

Po úspěšném absolvování budou studenti schopni porozumět matematické podstatě vybraných algoritmů, problémům spojeným s časovým trváním výpočtů a vlivu zaokrouhlovacích chyb na výsledek získaný výpočtem na počítači

Obsah předmětu

1. Ukládání čísel v počítači, problém zaokrouhlovacích chyb. 2. Časová výpočetní složitost algoritmů, velké 0. 3. Základní datové struktury: pole, spojový seznam, fronta, zásobník, operace na těchto strukturách. 4. Teorie grafů, binární kořenové stromy, Vyhledávací stromy. 2-3-4 strom, optimální vyhledávací strom, Huffmanův strom, halda. 5. Metody třídění. 6. Matematická logika. 7. Teorie výpočetní složitosti, třídy úloh: NP, NPC, NPH, P. 8. Teorie čísel, využití v kryptografii (šifra RSA a další). 9. Teorie automatů, vyhledávací automat Aho-Corasickové.

Literatura

Základní:

Jak uspět v předmětu

Doporučená příprava:

• Pravidelná příprava během semestru místo drcení na zkoušku
• Přednáškové slidy a materiály dostupné přes Moodle VŠE (dl.vse.cz)
• Stará zkouška / typové otázky — zeptej se cvičícího nebo hledej na InSIS
• Studijní skupiny a sdílení poznámek

• Přečti si sylabus — co je povinná vs. doporučená literatura
• Podmínky zápočtu (zápočtové testy, projekty, docházka)
• Termíny zkoušek zapisovat včas — kapacita bývá omezená

Doporučené zdroje

• Sylabus na InSIS — osnova, literatura, garant
• Moodle VŠE — prezentace a studijní materiály
• Knihovna VŠE — přístup k e-knihám a databázím
• SIS VŠE — výsledky zkoušek, zkušební termíny