APA-25

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

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

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

Расписание

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

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

Дополнительно в марте будет проведено 2 лекции и 2 семинара:
(вместо несостоявшихся занятий в январе)

3-го марта (понедельник)
лекция с 16:20 до 17:40 (ауд.D202)
семинар с 18:10 до 19:30 (ауд.D202)
17-го марта (понедельник)

Внимание!!!

На первой неделе марта занятия переносятся со среды на четверг,
они состоятся 6-го марта: лекция с 14:40 до 16:00 (ауд.R305), семинар с 16:20 до 17:40 (ауд.D102)

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

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

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

1-ое домашнее задание (крайний срок сдачи - 6 марта, 14:40)

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.
J. Cassaigne, T. Harju, J. Karhumaki, On the Undecidability of Freeness of Matrix Semigroups, Int. J. Algebra Comput. 9, 3–4 (1999), 295–305.
M. Paterson, Unsolvability in 3 × 3 matrices, Studies in Applied Mathematics. 49 (1970), 105–107.

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

Ю.В. Матиясевич, Десятая проблема Гильберта, Издательство ФИЗМАТЛИТ, 1993.
М.Н. Вялый, В.В. Подольский, А.А. Рубцов, Д.А. Шварц, А. Шень, Лекции по дискретной математике, Издательство ВШЭ, 2023.
О.Богопольский, Введение в теорию групп, Издательство URSS, 2002.
С. И. Адян, В. Г. Дурнев, Алгоритмические проблемы для групп и полугрупп, УМН, 55:2(332) (2000), 3–94.

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

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

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