APA-25

Алгоритмические вопросы алгебры

Преподаватель

Таламбуца Алексей Леонидович <atalambutsa@hse.ru>

Расписание

Лекции: среда, с 13:00 до 14:20, ауд.S328

Семинары: среда, с 14:40 до 16:00, ауд.D203

Внимание!
Экзамен пройдёт в пятницу, 28 марта, в ауд.D206, с 11:00 до 18:00.

Экзамен проводится устно, по вопросам, рассматривавшимся в лекционном курсе.

На подготовку ответа даётся 45 минут, при подготовке ответа можно использовать любые заранее подготовленные материалы, в том числе и электронные.

Экзаменационные билеты

Формула оценки

Итог = Округление(0.3 * ДЗ + 0.3 * КР + 0.4 * Э),
где ДЗ — средняя оценка за все домашние задания,
КР — оценка за контрольную работу,
Э — оценка за экзамен.
Округление арифметическое.

Расписание элементов контроля

1-ое домашнее задание (крайний срок сдачи задач 2-5 — 6 марта, 14:40; задачи 1 — 12 марта, 13:00 )

2-ое домашнее задание (крайний срок сдачи — 19 марта, 13:00)

Письменная контрольная работа состоится 17-го марта в 18:10, ауд.G409

Список литературы

1. А. Саломаа, Жемчужины теории формальных языков, М.: Мир, 1986.
2. M. Sipser Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012 (ISBN 113318779X)
3. H.A. Maurer, A. Salomaa, D. Wood, L codes and number systems, Theoretical Computer Science 22 (1983), 331–346.
4. J. Honkala, Unique representation in number systems and L codes, Discrete Applied Mathematics 4 (1982), 229–232.
5. M. Paterson, Unsolvability in 3 × 3 matrices, Studies in Applied Mathematics. 49 (1970), 105–107.
6. J. Cassaigne, T. Harju, J. Karhumaki, On the Undecidability of Freeness of Matrix Semigroups, Int. J. Algebra Comput. 9, 3–4 (1999), 295–305.

Список дополнительной литературы

1. Ю.В. Матиясевич, Десятая проблема Гильберта, Издательство ФИЗМАТЛИТ, 1993.
2. М.Н. Вялый, В.В. Подольский, А.А. Рубцов, Д.А. Шварц, А. Шень, Лекции по дискретной математике, Издательство ВШЭ, 2023.
3. T. Nagell, Introduction to number theory, Wiley, 1951.
4. С. И. Адян, В. Г. Дурнев, Алгоритмические проблемы для групп и полугрупп, УМН, 55:2(332) (2000), 3–94.
5. P. de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago. ISBN 0-226-31719-6

Темы прошедших лекций

1. Алгоритмические проблемы. Тезис Чёрча-Тьюринга. Десятая проблема Гильберта, теорема МРДП (формулировка).
2. Коды и L-коды. Теорема Маурера-Саломаа-Вуда о соответствии унарных L-кодов нестандартным системам счисления.
3. Алгоритм Хонкалы проверки единственности записи числа в нестандартной системе счисления (с доказательством корректности).
4. Алгоритм Сардинаса-Паттерсона проверки единственности декодирования (с доказательством корректности).
5. Полугруппы и моноиды. Свободный моноид. Свободные порождающие моноида. Пинг-понг-лемма для моноидов биекций.
6. Проблема соответствия Поста (ПСП) и её модифицированная версия (МПСП). Доказательство неразрешимости МПСП. Сводимость ПСП к МПСП.
7. Доказательство теоремы Патерсона о неразрешимости проблемы вырождения для матриц 3x3.
8. Доказательство сводимости ММПСП к ПСП.
9. Доказательство неразрешимости проблемы свободного порождения для матриц 3x3. Теорема Гольдбаха о простых значениях многочлена.

Задачи с семинаров

• Семинар 1

• Семинар 2

• Семинар 3

• Семинар 4

• Семинар 5

• Семинар 6

• Семинар 7

• Семинар 8

• Семинар 9