APA-25

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

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

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

Расписание

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

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

Внимание!
Вторая дополнительная лекция и семинар пройдут 17-го марта (понедельник)
На семинаре будет проходить контрольная работа.

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

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

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

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

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

2-ое домашнее задание будет выдано после 8-ой лекции

Письменная контрольная работа состоится вместо 9-го семинара

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

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

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

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

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

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

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