Просмотр кода страницы APA-25

<big>'''Алгоритмические вопросы алгебры'''
</big>

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

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

'''Расписание'''

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

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

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

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

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

[https://homepage.mi-ras.ru/~altal/files/apa-25/homew_1-upd.pdf 1-ое домашнее задание (крайний срок сдачи задач 2-5 — 6 марта, 14:40; задачи 1 — 12 марта, 13:00 )]

[https://homepage.mi-ras.ru/~altal/files/apa-25/homew_2.pdf 2-ое домашнее задание (крайний срок сдачи — 19 марта, 13:00)]

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

'''Список литературы'''
# А. Саломаа, Жемчужины теории формальных языков, М.: Мир, 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.
# Доказательство сводимости ММПСП к ПСП.

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

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_1.pdf Семинар 1]

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_2.pdf Семинар 2]

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_3.pdf Семинар 3]

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_4.pdf Семинар 4]

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_5.pdf Семинар 5]

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_6.pdf Семинар 6]

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_7.pdf Семинар 7]

*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_8.pdf Семинар 8]