Домашние задания по Лаврову. Решённые домашние задания посылать в pdf (LaTeX) на vyahhi@spbsu.ru.

Книги по LaTeX: [1], [2].

TeXnicCenter - IDE for LaTeX.
Detexify2 - LaTeX symbol classifier

К 19 марта:

• 7-в (стр. 51),
• 9-г (стр. 51), не строя таблицу истинности
• 20-м (стр. 53),
• 35-в (стр. 55).

К 12 апреля:

• 26-и (стр. 70),
• 15-в (стр. 84),
• 6-л (стр. 92).

К 26 апреля:

• Написать алгоритм для машины Тьюринга, складывающий два двоичных числа, например "...$$$$111+101$$$$..." -> "...$$$$1100$$$$...".
• Написать алгоритм Маркова для перемножения двух двоичных чисел, например "111*101" -> "100011".
• Написать алгоритм Маркова для перевода двоичного числа в унарное, например "101" -> "|||||"
• Выучить аксиомы ZFC (как в Лаврове, стр. 100).

К 17 мая:
Подготовиться к докладу по классу сложности (5 минут, определение, отношение с другими классами, примеры задач).

1. P
2. NP, NP-complete, NP-hard (Путин)
3. co-NP, co-NP-complete (Ульянов)
4. L, NL (Вартанова)
5. PSPACE, PH (Лукьянов)
6. EXPTIME, ELEMENTARY (Журавлев)
7. PP (Михайлова)
8. BPP, ZPP (Тюшев)
9. BQP (Сергеев)
10. NC (Зубаревич)
11. #P, #P-complete (Крень)
12. RP
13. UP (Калмук)