Úvod do teoretické informatiky (01UTI)

poslední změna: 18-02-2021

Aktuálně

Vzhledem k aktuální epidemiologické situaci probíhá výuka předmětu (na základě příkazu rektora 21/2020) nekontaktně v týmu. Team-Predmet-B202-01UTI v MS Teams. Pokud máte 01UTI zapsaný s přesto nejste členy tohoto týmu, ozvěte se emailem/v TEAMS.

Anotace

Základní oblasti teoretické informatiky:
1) Jazyky a automaty – konečné automaty, regulární jazyky a vyhledávání, zásobníkové automaty, bezkontextové jazyky, Turingovy stoje.
2) Složitost algoritmů – algoritmus, výpočetní složitost, třída P, základy NP-úplnosti.

Literatura

  • J. Mareš. Jazyky, gramatiky a automaty. Skriptum ČVUT, 2011.
  • V. Majerech. Úvod do složitosti a NP-úplnosti. link
  • O. Carton. Langages formels, calculabilité et complexité. Vuibert, 1993.