| What: | Lecture |
| When: | Sunday, 30 September 2007, 10:00–11:35 |
| Where: | ПОМИ РАН |
| Slides: | introductorycourse_lecture_300907.pdf |
Ещё немного теории сложности вычислений: классы PSPACE, EXP, RP, BPP. Конечные автоматы: недетерминированные КА, регулярные выражения, pumping лемма.
