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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м
 
(не показано 45 промежуточных версии этого же участника)
Строка 8: Строка 8:
 
'''Расписание'''
 
'''Расписание'''
  
−
Лекции по средам с 13:00 до 14:20
+
Лекции: среда, с 13:00 до 14:20, ауд.S328
  
−
Семинары по средам с 14:40 до 16:00
+
Семинары: среда, с 14:40 до 16:00, ауд.D203
  
−
'''Формула оценки и пересдачи'''
+
'''Внимание!''' <br />
 +
Экзамен пройдёт в пятницу, 28 марта, в ауд.D206, с 11:00 до 18:00.
 +
 
 +
Экзамен проводится устно, по вопросам, рассматривавшимся в лекционном курсе.
 +
 
 +
На подготовку ответа даётся 45 минут, при подготовке ответа можно использовать любые заранее подготовленные материалы, в том числе и электронные.
 +
 
 +
[https://homepage.mi-ras.ru/~altal/files/apa-25/exam.pdf Экзаменационные билеты]
 +
 
 +
'''Формула оценки'''
 
   
 
   
 
Итог = Округление(0.3 * ДЗ + 0.3 * КР + 0.4 * Э),<br />
 
Итог = Округление(0.3 * ДЗ + 0.3 * КР + 0.4 * Э),<br />
 
где ДЗ — средняя оценка за все домашние задания, <br /> КР — оценка за контрольную работу, <br /> Э — оценка за экзамен.<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-го марта в 18:10, ауд.G409
  
 
'''Список литературы'''
 
'''Список литературы'''
Строка 23: Строка 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
  
 
'''Темы прошедших лекций'''
 
'''Темы прошедших лекций'''
 
# Алгоритмические проблемы. Тезис Чёрча-Тьюринга. Десятая проблема Гильберта, теорема МРДП (формулировка).
 
# Алгоритмические проблемы. Тезис Чёрча-Тьюринга. Десятая проблема Гильберта, теорема МРДП (формулировка).
 
# Коды и L-коды. Теорема Маурера-Саломаа-Вуда о соответствии унарных L-кодов нестандартным системам счисления.
 
# Коды и L-коды. Теорема Маурера-Саломаа-Вуда о соответствии унарных L-кодов нестандартным системам счисления.
−
# Алгоритм Хонкалы проверки единственности записи числа в нестандартной системе счисления.
+
# Алгоритм Хонкалы проверки единственности записи числа в нестандартной системе счисления (с доказательством корректности).
−
# Алгоритм Сардинаса-Паттерсона проверки единственности декодирования.
+
# Алгоритм Сардинаса-Паттерсона проверки единственности декодирования (с доказательством корректности).
 +
# Полугруппы и моноиды. Свободный моноид. Свободные порождающие моноида. Пинг-понг-лемма для моноидов биекций.
 +
# Проблема соответствия Поста (ПСП) и её модифицированная версия (МПСП). Доказательство неразрешимости МПСП. Сводимость ПСП к МПСП.
 +
# Доказательство теоремы Патерсона о неразрешимости проблемы вырождения для матриц 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»