Контрольная работа №1 «Машина Тьюринга»

Вид материала

Контрольная работа

Подобный материал:

• Пояснительная записка к курсовому проекту на тему «Машина Тьюринга» по дисциплине, 256.01kb.
• Задача точного определения понятия алгоритма была полностью решена в 30-х годах, 519.73kb.
• Контрольная работа По философии техники Студентки 4 курса, 113.06kb.
• Сложность вычислений, 29.79kb.
• Контрольная работа выполняется в виде реферата в соответствии с требованиями по оформлению., 11.15kb.
• Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.
• Базовые программы для машины тьюринга реферат по дисциплине «Дискретная математика», 52.31kb.
• Ю. А. Самарский 10 июня 2011 г. Программа, 140.09kb.
• Контрольная работа по алгебре «Правила вычисления производных» Контрольная работа, 65.69kb.
• Контрольная работа для студентов первого- второго курса заочного отделения. Контрольная, 11.95kb.

Теория алгоритмов

Содержание текущего промежуточного контроля

Темы контрольных работ

1.Контрольная работа №1 «Машина Тьюринга»

2.Контрольная работа №2 «Рекурсивные функции». «Нормальные алгоритмы Маркова»


ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ К ЗАЧЕТУ

1. Необходимость уточнения понятия алгоритма.
   
2. Машина Поста.
   
3. Машина Тьюринга.
   
4. Нормальные алгоритмы Маркова.
   
5. Машина Тьюринга и современные ЭВМ.
   
6. Основная гипотеза теории алгоритмов (тезис Тьюринга).
   
7. Операции над машинами Тьюринга.
   
8. Происхождение рекурсивных функций.
   
9. Примитивно рекурсивные функции.
   
10. Оператор минимизации.
    
11. Вычислимость функций на машине Тьюринга.
    
12. Оператор примитивной рекурсии.
    
13. Разрешимые множества и их свойства.
    
14. Перечислимые множества и их свойства.
    
15. Теорема Поста.
    
16. Алгебраически неразрешимые проблемы.
    
17. Понятие универсальной функции.
    
18. Неразрешимость проблемы самоприменимости.
    
19. Понятие сложности вычисления.
    
20. Теорема Райса.
    
21. Марковские подстановки.
    
22. Нормальные алгоритмы и их применение к словам.
    

Примерные темы рефератов

1. Алгоритмы вокруг нас.
   
2. Основатели теории алгоритмов – Клини, Черч, Пост, Тьюринг.
   
3. Тезис Черча.
   
4. Проблема вычислимости математической логике.
   
5. Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту.
   
6. Методы разработки алгоритмов.
   
7. Средства и языки описания (представления) алгоритмов.
   
8. История формирования «понятия алгоритмов».
   
9. Известнейшие алгоритмы в истории математики.
   
10. Нормальные алгоритмы Маркова.
    
11. Принцип нормализации Маркова.
    
12. Эквивалентность различных теорий алгоритмов.
    
13. Алгоритмические проблемы.
    
14. Теорема Гёделя о неполноте формальной арифметики.
    

Работа при подготовке к зачету

1. Внимательно прочитать вопрос.
   
2. Составить план и при необходимости конспект вопроса.
   
3. Вспомнить основные термины, понятия, закономерности и законы по теме.
   
4. Найти соответствующие наглядные пособия (таблицы, схемы и т. д.), имеющиеся в учебном кабинете.
   
5. Подтвердить ответ схематическими рисунками и примерами.