Teoretické základy informatiky

Prednášajúci:Otokar Grošek
Cvičiaci:Otokar Grošek

Upozornenie

Sem napíšte upozornenie

Organizácia
Podmienky
Oznamy
Viac

Organizácia predmetu

Predmet je členený do nasledujúcich aktivít:

  • Prednášky: 2 hodiny týždenne podľa rozvrhu, streda 11 – 13h, C517
  • Cvičenie: 2 hodiny týždenne podľa rozvrhu, štvrtok 10 – 12h, C517
Konzultácie:

dohodou (na prednáške/mailom)

Plán semestra

  1. História počítania.
  2. Pojem množstva informácie. Entrópia a jej využitie.
  3. Binárne relácie a ich aplikácie v informatike.
  4. Komunikačné relácie.
  5. Pologrupy, monoidy, transformačný monoid, Mealyho automaty.
  6. Deterministické a nedeterministické konečné automaty, pumpovacia lema pre regulárne jazyky, Kleenova veta.
  7. Stochastické automaty.
  8. Lineárne automaty.
  9. Triedy asymptotickej zložitosti výpočtu.
  10. Pojem náhodnej postupnosti a odlíšiteľnosť v informatike.
  11. Pojem jednosmernej funkcie.
  12. Turingové stroje a problém zastavenia.

Podmienky absolvovania

Počas semestra poslucháči absolvujú 2 testy, oba s bodovou hodnotou 30 bodov. Obsahom 1. testu bude entrópia, aplikácie relácie tolerancie a ekvivalencie, HMR a sústava maticových booleovských rovníc.

Obsahom 2. testu budú: kardinalita množín, pologrupy, monoidy, transformačný monoid, Mealyho automaty, deterministické a nedeterministické konečné automaty, pumpovacia lema pre regulárne jazyky, Kleenova veta, syntaktický monoid, minimálny automat. Na teste môžete používať vlastnú kalkulačku (nie mobil!) a akékoľvek VLASTNÉ poznámky. Akákoľvek komunikácia s kolegom má za následok vylúčenie z testu bez možnosti náhrady.

Skúška bude mať bodovú hodnotu 50 bodov.

Na úspešné absolvovanie predmetu musí študent získať zo skúšky aspoň 25 bodov a aspoň 56 bodov za celý semester. Body získané za semester a zo skúšky sa sčitujú u študentov, ktorí získali zápočet a môžu vykonať skúšku.

Termíny testov budú vždy upresnené minimálne s týždňovým predstihom.  Na písomke môžete používať vlastné poznámky z prednášky / cvičení a taktiež aj dostupné výukové materiály.

Pozn.: Odhalené podvádzanie pri zadaniach, napr. kopírovanie (aj časti) zadaní, snaha odovzdať cudzie riešenie, a iné, môže cvičiaci penalizovať vylúčením študenta z predmetu (nepridelením/zrušením bodov aj z iných zadaní).

Náhradný termín testu, či skúšky neexistuje!!! Iba v prípade naozaj vážnych dôvodov neúčasti Vás prosím, aby ste ma s tým dostatočne v predstihu oboznámili (najneskôr do hodiny začatia písania písomky). V takom prípade sa možno dohodneme na náhradnom termíne.

 

 

Literatúra
  • zahraničná:

  • Bridges, D. S.: Computability. Springer-Verlag, New York, 1994.
  • Demlová, M., Koubek, V.: Algebraická teorie automatu. SNTL 1990.
  • Gallager, R.G.: Information Theory and Reliable Communication. J. Wiley and sons, Inc., New York, 1968.
  • Gatial, J., Hejný, M.: Stavba planimetrie. SPN Bratislava, 1973.
  • Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Springer-Verlag, Berlin, 1999.
  • Howie, J.M.: Automata and Languages. Clarendon Press, Oxford,1991.
  • Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton Univ. Press, Princeton, 1996.
  • O´Regan, G.: A Brief History of Computing, Spinger-Verlag, 2008.
  • domáca:

  • Hopcroft, J.E., Ullman, J.D.: Formálne jazyky a automaty. ALFA, Bratislava, 1978.
  • Molnár, Ľ., Češka, M., Melichar, B.: Gramatiky a jazyky. ALFA/SNTL, Bratislava, 1987.
  • Preparata, F.P., Yeh, R.T.: Úvod do teórie diskrétnych matematických štruktúr. ALFA Bratislava, 1982.
  • Satko, L.: Vyčísliteľnosť a programovanie. SVŠT Bratislava, 1988.