Geum.ru

Учебно-методический комплекс по дисциплине 230100 Теория алгоритмов Направление подготовки

Вид материалаУчебно-методический комплекс
Iv. организация самостоятельной работы студентов
Требования к экзамену
Vi темы для рефератов
Vii. вопросы к коллоквиуму
Viii. вопросы к экзамену
Неразрешимые алгоритмические проблемы.
Подобный материал:
1   2   3   4   5

IV. ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ



Самостоятельная работа студентов состоит в изучении рекомендуемой литературы, проработке лекционного материала, решении задач.

Предполагаются следующие виды самостоятельной работы студентов:
  1. работа студентов с конспектами лекций и рекомендованной литературой;
  2. работа студентов по разбору заданий, выполняемых на семинарских занятиях;
  3. подготовка студентов к контрольной работе, экзамену.


Образцы контрольных заданий.

Вариант №1.

1. Пусть дан алфавит А{в,с}. Постройте алгорифм И, перерабатывающий всякое слово Р в алфавите А, содержащее хотя бы одно вхождение буквы “в” в слово, которое получается вычеркиванием в Р самого левого вхождения “в”. Пустое слово перерабатывает в пустое. Алгорифм И неприменим к непустым словам, не содержащим вхождений буквы “в”.

2. Пусть А произвольный алфавит {а0, а1,…, аn}. Постройте нормальный алгорифм И в алфавите В=А такой, чтобы для любого слова Р в алфавите А выполнялось равенство И(Р)=Р. Причем Р- слово, обратное слово или обращение слова Р.
  1. Пусть дан произвольный алфавит {а0, а1,…, аn}. Постройте нормальный алгорифм И, перерабатывающий всякое слово в пустое.
  2. Постройте алгорифм И над алфавитом А, приписывающий к произвольному слову Р в А фиксированное слово в алфавите А слева.
  3. Постройте алгорифм И в алфавите В=А, приписывающий к произвольному слову Р в А фиксированное слово в алфавите В справа. А={а0, а1,…, аn}.


Вариант №2.


1. Пусть дан произвольный алфавит {а0, а1,…, аn} и пусть В=А. Постройте алгорифм И в В такой, что И(Л)=Л и И(Р)=Р для любой буквы А и для произвольного слова Р в А. (т. е. алгорифм, “стирающий” первую букву во всяком слове а алфавите А).

2. Пусть буква не входит в алфавиты А и В, и пусть а0, а1,…, аn – фиксированные буквы алфавита А, а о0, о1,…, оn – фиксированные слова в алфавите В. Постройте нормальный алгорифм в алфавите А В, перерабатывающий всякое слово Р в алфавите А в слово, полученное в результате одновременной подстановки слов а0, а1,…, аn в слово Р вместо букв о0, о1,…, оn.
  1. Постройте нормальный алгорифм над алфавитом А={а0, а1,…, аn}, “стирающий” произвольное слово в алфавите А и заменяющий его фиксированным словом О в алфавите А.
  2. Постройте алгорифм над алфавитом А={а0, а1,…, аn}, заменяющий каждую букву в произвольном непустом слове буквой.

Постройте нормальный алгорифм над алфавитом А={а0, а1,…, аn}, перерабатывающий пустое слово в О и всякое непустое слово в алфавите В в пустое


V .ТРЕБОВАНИЯ К ЭКЗАМЕНУ


Для получения экзамена по курсу студент должен сдать коллоквиум, успешно пройти тестирование, набрать достаточное количество баллов Полезно написание реферата.


VI ТЕМЫ ДЛЯ РЕФЕРАТОВ

  • Проблема алгоритмической разрешимости в математике.
  • Основатели теории алгоритмов – Клини, Черч, Пост, Тьюринг.
  • Основные определения и теоремы теории рекурсивных функций
  • Тезис Черча.
  • Проблемы вычислимости в математической логике. Машина Поста. Машина Тьюринга.
  • Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту.
  • Неформальные аксиоматические теории
  • Формальные аксиоматические теории
  • Неразрешимые алгоритмические проблемы
  • Применение логики предикатов к логико-математической практике и формализованном исчислении предикатов
  • Свойства аксиоматических теорий
  • Логика предикатов


VII. ВОПРОСЫ К КОЛЛОКВИУМУ

  1. Понятие алгоритма и его характерные черты. Уточнение понятия алгоритма.
  2. Алгоритм как формальная математическая система.
  3. Разрешимые и перечислимые множества.
  4. Вычислимые функции. Частично рекурсивные и общерекурсивные функции.
  5. Машина Тьюринга.
  6. Примеры схем машины Тьюринга.
  7. Нормальные алгоритмы Маркова.
  8. Исчисление высказываний
  9. Неразрешимые алгоритмические проблемы (обзор).


VIII. ВОПРОСЫ К ЭКЗАМЕНУ
Интуитивное представление об алгоритмах. Неформальное понятие алгоритма.
2


Свойства алгоритмов




Формы представления алгоритмов




Основные структуры алгоритмов




Основные алгоритмы сортировки




Оценка эффективности и сложности алгоритмов




Формализация понятия алгоритма




Вычислимые функции, разрешимые и перечислимые множества.
2


Определение машины Тьюринга. Применение машины Тьюринга к словам.

2


Определение машины Поста. Команды . Примеры программ




Конструирование машин Тьюринга.
2


Вычислимые по Тьюрингу функции. Основная гипотеза теории алгоритмов.

Машины Тьюринга и современные ЭВМ.
2


Тьюрингов подход к понятию «алгоритм». Алгоритмически разрешимые и неразрешимые проблемы.
2


Нормальные алгоритмы Маркова. Эквивалентность различных теорий алгоритмов.
2


Способы композиции нормальных алгоритмов Маркова



16.
Рекурсивные функции. Тезис Черча.
2

17.

Неразрешимые алгоритмические проблемы.
2

18.
Эффективные операции над вычислимыми функциями.
2

19
Теорема о неподвижной точке. Общее понятие исчисления. Грамматики.
2

20.
Языки. Иерархия языков по Хомскому. Языки и машины.
2

21.
Пример невычислимой функции. Проблема распознавания самоприменимости.
2

22.
Основные меры сложности вычисления.
2

23
Приложения теории алгоритмов в информатике



24
Примеры алгоритмической неразрешимости
28



IX Тест по курсу «Теория алгоритмов»