APA-25 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия этого же участника)
Строка 12: Строка 12:
 
Семинары: среда, с 14:40 до 16:00, ауд.D203
 
Семинары: среда, с 14:40 до 16:00, ауд.D203
  
−
Дополнительно в марте будет проведено 2 лекции и 2 семинара вместо несостоявшихся январских занятий
+
'''Внимание!''' <br />
 +
Экзамен пройдёт в пятницу, 28 марта, в ауд.D206, с 11:00 до 18:00.
 +
 
 +
Экзамен проводится устно, по вопросам, рассматривавшимся в лекционном курсе.
 +
 
 +
На подготовку ответа даётся 45 минут, при подготовке ответа можно использовать любые заранее подготовленные материалы, в том числе и электронные.
 +
 
 +
[https://homepage.mi-ras.ru/~altal/files/apa-25/exam.pdf Экзаменационные билеты]
  
 
'''Формула оценки'''
 
'''Формула оценки'''
Строка 22: Строка 29:
 
'''Расписание элементов контроля'''
 
'''Расписание элементов контроля'''
  
−
1-ое домашнее задание будет выдано после 5-ой лекции
+
[https://homepage.mi-ras.ru/~altal/files/apa-25/homew_1-upd.pdf 1-ое домашнее задание (крайний срок сдачи задач 2-5 — 6 марта, 14:40; задачи 1 — 12 марта, 13:00 )]
  
−
2-ое домашнее задание будет выдано после 5-ой лекции
+
[https://homepage.mi-ras.ru/~altal/files/apa-25/homew_2.pdf 2-ое домашнее задание (крайний срок сдачи — 19 марта, 13:00)]
  
−
Письменная контрольная работа состоится вместо 9-го семинара
+
Письменная контрольная работа состоится 17-го марта в 18:10, ауд.G409
  
 
'''Список литературы'''
 
'''Список литературы'''
Строка 33: Строка 40:
 
# H.A. Maurer, A. Salomaa, D. Wood, L codes and number systems, Theoretical Computer Science 22 (1983), 331–346.
 
# 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. 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.
 
# M. Paterson, Unsolvability in 3 × 3 matrices, Studies in Applied Mathematics. 49 (1970), 105–107.
−
# С. И. Адян, В. Г. Дурнев, Алгоритмические проблемы для групп и полугрупп, УМН, 55:2(332) (2000), 3–94.
+
# 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.
 
# Ю.В. Матиясевич, Десятая проблема Гильберта, Издательство ФИЗМАТЛИТ, 1993.
 
# М.Н. Вялый, В.В. Подольский, А.А. Рубцов, Д.А. Шварц, А. Шень, Лекции по дискретной математике, Издательство ВШЭ, 2023.
 
# М.Н. Вялый, В.В. Подольский, А.А. Рубцов, Д.А. Шварц, А. Шень, Лекции по дискретной математике, Издательство ВШЭ, 2023.
−
# О.Богопольский, Введение в теорию групп, Издательство URSS, 2002.
+
# 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
  
 
'''Темы прошедших лекций'''
 
'''Темы прошедших лекций'''
Строка 47: Строка 55:
 
# Алгоритм Хонкалы проверки единственности записи числа в нестандартной системе счисления (с доказательством корректности).
 
# Алгоритм Хонкалы проверки единственности записи числа в нестандартной системе счисления (с доказательством корректности).
 
# Алгоритм Сардинаса-Паттерсона проверки единственности декодирования (с доказательством корректности).
 
# Алгоритм Сардинаса-Паттерсона проверки единственности декодирования (с доказательством корректности).
 +
# Полугруппы и моноиды. Свободный моноид. Свободные порождающие моноида. Пинг-понг-лемма для моноидов биекций.
 +
# Проблема соответствия Поста (ПСП) и её модифицированная версия (МПСП). Доказательство неразрешимости МПСП. Сводимость ПСП к МПСП.
 +
# Доказательство теоремы Патерсона о неразрешимости проблемы вырождения для матриц 3x3.
 +
# Доказательство сводимости ММПСП к ПСП.
 +
# Доказательство неразрешимости проблемы свободного порождения для матриц 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]
 +
 +
*[https://homepage.mi-ras.ru/~altal/files/apa-25/probl_9.pdf Семинар 9]

Текущая версия на 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

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

  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. Теорема Гольдбаха о простых значениях многочлена.

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

Источник — «http://wiki.cs.hse.ru/index.php?title=APA-25&oldid=90301»