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

Алгоритмически неразрешимые массовые проблемы в теории алгоритмов: проблемы самоприменимости, применимости, остановки и рекурсивности для машин Тьюринга. S-m-n теорема. Теорема Райса. Ассоциативные исчисления и порождаемые ими конечно определенные полугруппы и группы. Проблема Туэ, ее разрешимость. Проблемы тождества для конечно определенных полугрупп и групп. Их разрешимость. 10-я проблема Гильберта, ее разрешимость.

Нормальные алгоритмы Маркова

Нормальный алгоритм Маркова в алфавите и над алфавитом. Нормально-вычислимые функции. Примеры нормальных алгоритмов: тождественный нормальный алгоритм, нормальный алгоритм левого присоединения, нормальный алгоритм правого присоединения, нормальный алгоритм удвоения. Некоторые арифметические алгоритмы.

Алгоритмическая сводимость

Понятие алгоритмической сводимости. m-cводимость, ее свойства. M-эквивалентность, ее свойства. Несравнимые множества. Степени неразрешимости. Теорема о неподвижной точке. Теорема Клини.

Примерный пepeчeнь вoпpocoв для экзaмeнa:

1. Перечислите и поясните основные этапы полного построения алгоритмов.

2. Какие известны способы записи алгоритмов, дайте их краткую характеристику. Перечислите основные требования к записи алгоритмов.

3. Графический (блок-схемный) способ записи алгоритмов. Его преимущества и недостатки. Перечислите основные обозначения и приведите пример.

4. Сформулируйте основные определения абстрактного алфавита (алфавит, слово алфавита, расширение алфавита, алфавитный оператор).

5. Области применения теории алгоритмов.

6. Требования к составу микроопераций и логических условий алгоритма.

7. Дайте определение алгоритма, его особенности.

8. Перечислите и поясните основные этапы полного построения алгоритмов.

9. Какие известны способы записи алгоритмов, дайте их краткую характеристику. Перечислите основные требования к записи алгоритмов.

10. Графический (блок-схемный) способ записи алгоритмов. Его преимущества и недостатки. Перечислите основные обозначения и приведите пример.

11. Сформулируйте основные определения абстрактного алфавита (алфавит, слово алфавита, расширение алфавита, алфавитный оператор).

12. Области применения теории алгоритмов.

13. Требования к составу микроопераций и логических условий алгоритма.

14. Дайте определение алгоритма, его особенности.

15. Разрешимые и перечислимые множества.

16. Словесная форма записи алгоритмов. Его преимущества и недостатки, приведите пример.

17. Правила составления алгоритмов. В чем суть принципов поэтапной детализации, ограниченного числа структур, модульного принципа.

18. Приведите примеры алгоритмов с использованием типовых структур алгоритмов.

19. Что такое алгоритмизация? Дайте определение и приведите примеры логических и численных алгоритмов.

20. Свойства и виды алгоритмов и соотношение между ними.

21. Интерпретации и модели.

22. Семантическая и формальная непротиворечивость.

23. Полнота. Непротиворечивость и семантическая полнота исчисления высказываний.

24. Теорема Геделя о полноте исчисления предикатов.

25. Общее понятие формальной системы. Примеры.

26. Формальная арифметика. Теорема Геделя о неполноте формальной арифметики (формулировка).

27. Формальные языки и формальные грамматики и классификация Хомского.

28. Контекстно-свободные грамматики и деревья вывода.

29. Интуитивное понятие алгоритма. Требования к алгоритмам.

30. Формализация понятия алгоритма и универсальные алгоритмические модели.

31. Машина Тьюринга - основные определения. Понятие вычислимости на машине Тьюринга.

32. Операции над машинами Тьюринга. Универсальная машина Тьюринга.

33. Понятие алгоритмической неразрешимости. Теорема Райса.

34. Проблема остановки - формулировка теоремы и ее доказательство.

35. Понятие рекурсии. Примитивно-рекурсивные функции. Примеры.

36. Неограниченный оператор минимизации. Примеры. Определение частично-рекурсивной функции.

37. Разрешимые и перечислимые множества и предикаты.

38. Конечные автоматы. Основные определения. Способы задания автоматов.

39. Алгоритмические возможности: что могут и что не могут вычислять автоматы. Примеры.

40. Эквивалентность автоматов. Алгоритм минимизации автоматов.

41. Автоматы и логические схемы. Программная реализация автоматов.

42. Интуитивное опре­де­ле­ние по­ня­тия «ал­го­ритм». Свой­ст­ва ал­го­рит­ма

43. Про­стей­шие фун­кции. Опе­ра­ция под­ста­но­вки. Свой­ст­ва опе­ра­ции под­ста­но­вки. Опе­ра­ция при­ми­тив­ной ре­кур­сии. Свой­ст­ва опе­ра­ции при­ми­тив­ной ре­кур­сии. При­ми­тив­но-ре­кур­сивное опи­са­ние фун­кции.

44. При­ми­тив­но-ре­кур­сив­ная фун­кция. Свой­ст­ва при­ми­тив­но-ре­кур­сив­ных фун­кций. При­ме­ры при­ми­тив­но-ре­кур­сив­ных фун­кций. От­но­си­те­ль­ная при­ми­тив­ная ре­кур­сив­ность. Свой­ст­ва от­но­си­те­ль­ной при­ми­тив­ной ре­кур­сив­но­сти.

45. При­ми­тив­но-ре­кур­сив­ные опе­ра­ции (опе­ра­ция вве­де­ния фик­тив­ных пе­ре­мен­ных, опе­ра­ция под­ста­но­вки кон­стант, опе­ра­ция про­из­во­ль­ной под­ста­но­вки). Опе­ра­ции ко­неч­но­го сум­ми­ро­ва­ния и ко­неч­но­го про­из­ве­де­ния. При­мер ис­по­ль­зо­ва­ния опе­ра­ции ко­неч­но­го сум­ми­ро­ва­ния для до­ка­за­те­ль­ст­ва при­ми­тив­ной ре­кур­сив­но­сти фун­кции [x/y].

46. Пред­став­ля­ющая фун­кция пре­ди­ка­та. При­ми­тив­но-ре­кур­сив­ный пре­ди­кат. При­ми­тив­но-ре­кур­сив­ный пре­ди­кат от­но­си­те­ль­но со­во­куп­но­сти фун­кций и пре­ди­ка­тов. Ло­ги­че­с­кие опе­ра­ции. Опе­ра­ции на­ве­ши­ва­ния огра­ни­чен­ных кван­то­ров. Ку­со­чное за­да­ние фун­кции.

47. m-опе­ра­ция (опе­ра­ция ми­ни­ми­за­ции). Час­тич­но ре­кур­сив­ное опи­са­ние фун­к­ции. Час­тич­но ре­кур­сив­ная фун­кция. При­ме­ры час­тич­но ре­кур­сив­ных фун­кций. Об­ще­ре­кур­сив­ная фун­кция. При­ме­ры об­ще­ре­кур­сив­ных фун­кций.

48. Фор­ма­ль­ная сис­те­ма ре­кур­сив­ных фун­кций Эр­бра­на-Гё­де­ля. Фун­кция, вы­чис­ли­мая по Эр­бра­ну-Гё­де­лю.

49. Ре­кур­сив­но-пе­ре­чис­ли­мое мно­же­ст­во. Кри­те­рий ре­кур­сив­ной пе­ре­чис­ли­мо­сти мно­же­ст­ва. Ре­кур­сивные мно­же­ст­во. Кри­те­рий ре­кур­сив­но­сти мно­же­ст­ва (те­оре­ма По­ста).

50. Нор­ма­ль­ный ал­го­ритм Мар­ко­ва в ал­фа­ви­те и над ал­фа­ви­том. Нор­ма­ль­но-вы­чис­ли­мые фун­кции.

51. При­ме­ры нор­ма­ль­ных ал­го­рит­мов (тож­де­ст­вен­ный нор­ма­ль­ный ал­го­ритм, нор­ма­ль­ный ал­го­ритм ле­во­го при­со­еди­не­ния, нор­ма­ль­ный ал­го­ритм пра­во­го при­со­еди­не­ния, нор­ма­ль­ный ал­го­ритм уд­во­ения, не­ко­то­рые ариф­ме­ти­че­с­кие ал­го­ритмы).

52. Ма­ши­на Тью­рин­га. Опе­ра­ции над ма­ши­на­ми Тью­рин­га (опе­ра­ция ком­по­зи­ции, опе­ра­ция вет­вле­ния, опе­ра­ция за­цик­ли­ва­ния). Гё­де­ле­ва ну­ме­ра­ция ма­шин Тью­рин­га.

53. Фун­кция, вы­чис­ли­мая по Тью­рин­гу. До­ка­за­те­ль­ст­во су­ще­ст­во­ва­ния фун­к­ций, не­вы­чис­ли­мых по Тью­рин­гу. При­мер не­вы­чис­ли­мой по Тью­рин­гу фун­кции.

54. При­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых проблем (про­бле­ма рас­по­зна­ва­ния са­мо­при­ме­ни­мо­сти, про­бле­ма при­ме­ни­мо­сти).

55. Ма­ши­на По­ста. Ма­ши­на По­ста-Успен­ско­го.

56. Ма­ши­на с не­огра­ни­чен­ны­ми ре­ги­стра­ми (МНР