APA-25 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
| (не показано 5 промежуточных версии этого же участника) | |||
| Строка 13: | Строка 13: | ||
'''Внимание!''' <br /> | '''Внимание!''' <br /> | ||
| − | + | Экзамен пройдёт в пятницу, 28 марта, в ауд.D206, с 11:00 до 18:00. | |
| − | + | ||
| + | Экзамен проводится устно, по вопросам, рассматривавшимся в лекционном курсе. | ||
| + | |||
| + | На подготовку ответа даётся 45 минут, при подготовке ответа можно использовать любые заранее подготовленные материалы, в том числе и электронные. | ||
| + | |||
| + | [https://homepage.mi-ras.ru/~altal/files/apa-25/exam.pdf Экзаменационные билеты] | ||
'''Формула оценки''' | '''Формула оценки''' | ||
| Строка 41: | Строка 46: | ||
# Ю.В. Матиясевич, Десятая проблема Гильберта, Издательство ФИЗМАТЛИТ, 1993. | # Ю.В. Матиясевич, Десятая проблема Гильберта, Издательство ФИЗМАТЛИТ, 1993. | ||
# М.Н. Вялый, В.В. Подольский, А.А. Рубцов, Д.А. Шварц, А. Шень, Лекции по дискретной математике, Издательство ВШЭ, 2023. | # М.Н. Вялый, В.В. Подольский, А.А. Рубцов, Д.А. Шварц, А. Шень, Лекции по дискретной математике, Издательство ВШЭ, 2023. | ||
| − | # | + | # T. Nagell, Introduction to number theory, Wiley, 1951. |
# С. И. Адян, В. Г. Дурнев, Алгоритмические проблемы для групп и полугрупп, УМН, 55:2(332) (2000), 3–94. | # С. И. Адян, В. Г. Дурнев, Алгоритмические проблемы для групп и полугрупп, УМН, 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 | # P. de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago. ISBN 0-226-31719-6 | ||
| Строка 50: | Строка 55: | ||
# Алгоритм Хонкалы проверки единственности записи числа в нестандартной системе счисления (с доказательством корректности). | # Алгоритм Хонкалы проверки единственности записи числа в нестандартной системе счисления (с доказательством корректности). | ||
# Алгоритм Сардинаса-Паттерсона проверки единственности декодирования (с доказательством корректности). | # Алгоритм Сардинаса-Паттерсона проверки единственности декодирования (с доказательством корректности). | ||
| − | # Полугруппы и моноиды. Свободный моноид. Свободные порождающие моноида. Пинг-понг-лемма для моноидов. | + | # Полугруппы и моноиды. Свободный моноид. Свободные порождающие моноида. Пинг-понг-лемма для моноидов биекций. |
# Проблема соответствия Поста (ПСП) и её модифицированная версия (МПСП). Доказательство неразрешимости МПСП. Сводимость ПСП к МПСП. | # Проблема соответствия Поста (ПСП) и её модифицированная версия (МПСП). Доказательство неразрешимости МПСП. Сводимость ПСП к МПСП. | ||
# Доказательство теоремы Патерсона о неразрешимости проблемы вырождения для матриц 3x3. | # Доказательство теоремы Патерсона о неразрешимости проблемы вырождения для матриц 3x3. | ||
Текущая версия на 10:24, 25 марта 2025
Алгоритмические вопросы алгебры
Преподаватель
Таламбуца Алексей Леонидович <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
Список литературы
- А. Саломаа, Жемчужины теории формальных языков, М.: Мир, 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.
- T. Nagell, Introduction to number theory, Wiley, 1951.
- С. И. Адян, В. Г. Дурнев, Алгоритмические проблемы для групп и полугрупп, УМН, 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.
- Доказательство сводимости ММПСП к ПСП.
- Доказательство неразрешимости проблемы свободного порождения для матриц 3x3. Теорема Гольдбаха о простых значениях многочлена.
Задачи с семинаров
