Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnością problemów obliczeniowych a strukturalną złożonością modeli obliczeń. Hierarchia Chomsky'ego. Podstawowe zagadnienia złożoności obliczeniowej.
1. Pojęcie alfabetu i języka
2. Automaty skończenie, ich minimalizacji i równoważność. Lemat o pompowaniu.
3. Wyrażenie regularne
4. Gramatyki bezkontekstowe
5. Uniwersalne modele obliczeniowe
- Nauczyciel: Tomasz Stypuła