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




Скачать 91.47 Kb.
Название Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов
Дата публикации 19.06.2014
Размер 91.47 Kb.
Тип Методические указания
literature-edu.ru > Информатика > Методические указания

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ


ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


«Утверждаю»

Декан ФВТИ

доцент к.т.н.

____________Лапко В.В.

______________2006 г.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ

ПО КУРСУ

ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
(для студентов специальности 7.080403 «Программное обеспечение вычислительной техники и автоматизированных систем»)


Рассмотрено на заседании кафедры


Прикладной математики и информатики

Протокол № ____ от « »_______2006г.

Донецк 2006

Методические указания для самостоятельной работы студентов по курсу «Теория алгоритмов и вычислительных процессов» (для студентов специальности 7.0804.03)

Сост.: Барашко А. С., Коломойцева И. А.
Методические указания предназначены для закрепления знаний студентов профессионального направления «Программное обеспечение вычислительной техники и автоматизированных систем» (специалистов и магистров) дневной формы обучения факультета вычислительной техники и информатики, получаемых при изучении лекционного материала. Методические указания (МУ) содержат теоретические вопросы и задачи по всем разделам курса «Лекции по теории алгоритмов и вычислительных процессов» (адрес электронной версии pmi_nt_server\student\text\taivp\лекции.rar). Для каждого теоретического вопроса в МУ указаны страницы «лекций», где содержится ответ. В конце основных разделов «лекций» содержатся формулировки условий задач, которые предлагаются студенту для самостоятельного решения.
Введение
1. Неформальное определение алгоритма. Необходимость уточнения этого понятия.

Стр.2, 4-5.

2. Основная гипотеза теории алгоритмов. Понятие всеобщего (универсального) алгоритма.

Стр. 3-6.

3. Формулировка 10-й проблемы Гильберта и её решение.

Стр.3.


  1. Формальные языки и грамматики.


1. Алфавиты и языки. Проблема задания языка конечным описанием.

Стр. 9.

2. Формальное определение грамматики и вывод в ней слов. Язык, порождённый грамматикой.

Стр. 9.

3. Типы грамматик. Иерархия Хомского.

Стр. 10-11.

4. Пустое слово. Как следует изменить КЗ-грамматику, чтобы она порождала пустое слово?

Стр. 11.

5. Деревья ввода для КС-грамматик. Результат порождающего дерева. Необходимое и достаточное условие возможности вывода сентенциальной формы.

Стр. 11-13.

6. Синтаксический анализ. Продемонстрировать на примере грамматики синтаксический анализ слова .

Стр. 13-14.

7. LL(k) – грамматики. Проблемы, касающиеся LL(1) грамматик.

Стр. 14-16.
Задачи
1. Пусть 1. , 2. , 3. , 4. 5. 6. , 7., 8. .

Построить вывод слова , указав номера используемых продукций. Найти язык L(G).

2. Пусть G – грамматика, все продукции которой имеют вид , где А и В – одиночные переменные (нетерминалы), а х – слово терминалов. Показать, что L(G) может быть порождён регулярной грамматикой.

3. Какой язык порождает грамматика где Р состоит из: . Определить тип грамматики.

4. Построить регулярную грамматику, порождающую язык .

5. Пусть - два языка и - произведение языков . Доказать, что произведение двух КС – языков является КС–языком.

6. Пусть G = ({S,T},{a,b,c},P,S), где Определить тип грамматики G и язык L(G).

7. Пусть , где . Определить тип грамматики G и язык L(G).
II. Распознающие машины Тьюринга.
1. Определение базовой модели мТ.

Стр. 18.

2. Описание движений мТ с помощью последовательности конфигураций (протокол работы распознающей мТ).

Стр. 19.

3. Язык, представимый (распознаваемый) мТ.

Стр 19.

4. Рекурсивно перечислимые и рекурсивные языки.

Стр. 21.

5. Машина Тьюринга с двусторонне бесконечной лентой. Отличие определения отношения между конфигурациями по сравнению с базовой моделью.

Стр. 21-22.

6. Моделирование мТ с двусторонне бесконечной лентой базовой моделью мТ.

Стр. 22-23.

7. Многоленточная мТ.

Стр. 23-24.

8. Моделирование многоленточной мТ базовой моделью мТ.

Стр. 24.

9. Недетерминированная мТ.

Стр. 24-25.

10. Моделирование недетерминированной мТ детерминированной.

Стр. 25-26.


Задачи
Построить мТ, определив её как совокупность шести объектов, которая распознаёт язык L. Записать 2 протокола работы этой машины на словах длины не меньше 5, одно из которых принадлежит L, а второе – нет.

1. не содержит 2-х идущих подряд единиц}

2. содержит ровно вдвое больше символов а, чем b}

3. состоит из одинакового числа символов }.

4.

5.

6.

7.

8.

9.
III. Временная и ленточная сложность.
1. Ленточная и временная сложности мТ.

Стр. 27-28.

2. Теорема об «уменьшении ленты».

Стр. 29.

3. Утверждение о сохранении ленточной сложности при переходе от мТ с к лентами памяти к мТ с одной лентой памяти.

Стр. 29-30.

4. Наименьшая верхняя и наибольшая нижняя грани множеств действительных чисел. Супремум и инфимум.
Стр. 30.

5. Теорема «ускорения» для многоленточной мТ.

Стр. 30-32.

6. Утверждение об изменении временной сложности многоленточной мТ при моделировании её одноленточной и двухленточной мТ.

Стр. 32-33.

7. Теорема «ускорения» для одноленточной мТ.

Стр. 33.

Задачи


1. Определить базовую модель мТ, распознающую язык (см. стр. 20-21), и найти её ленточную и временную сложность.

2. Определить базовую модель мТ, распознающую язык , и найти её ленточную и временную сложность.

3. Показать, что язык имеет линейную временную и логарифмическую ленточную сложности. (см. стр. 28)

4. Определить такую 2-х ленточную мТ, распознающую язык , для которой ленточная и временная сложности являются линейными функциями. Составить протокол работы этой машины на слове .

5. Пусть - одноленточная мТ, где |K|=k и |Г-{B}|=m. Для ленточной сложности L(n) мТ Т выразить верхнюю границу через временную сложность T(n), а для временной - через ленточную. Считать что L(n) и T(n) – всюду определенные функции.

6. Любая строка начинающаяся с 1, может интерпретироваться как целое двоичное число. Пусть N(w) есть это число Положим



Например, слово 1с10с11с100с101 принадлежит L. Показать, что язык L находится в классе ленточной сложности, ограниченном log n. Точнее, описать действия 2-х ленточной мТ Т, распознающую L и для которой L(n)=log n.

IV. Рекурсивные функции
1. Определения мТ, вычисляющей значения функции. Совместимый набор четвёрок.

Стр. 35-36.

2. Определения ЧРФ и рекурсивных функций.

Стр. 36-37.

3. Геделева нумерация.

Стр. 37-38.

4. Тезис Черча. Его использование при доказательстве теорем.

Стр. 38.

5. Счётные и континуальные множества. Примеры.

Стр. 38-39.

6. Диагональный метод Кантора. Доказательство того, что множество подмножеств натурального ряда континуально.

Стр. 38-39.

7. Теорема о мощности классов ЧРФ и рекурсивных функций.

Стр. 39-40.

8. Теорема о существовании функций, не являющихся частично рекурсивными.

Стр. 40.

9. Теорема о мощности множества номеров произвольной ЧРФ.

Стр. 40.

10. Определения универсальных функций.

Стр. 41.

11. Теорема о существовании универсальной функции.

Стр. 41.

12. Формулировка s-m-n- теоремы.

Стр. 41-42.

13. Теорема о существовании двухместной рекурсивной функции, определяющей по номерам 2-х ЧРФ номер функции, которая является суперпозицией этих ЧРФ.

Стр. 42-43.

14. Теорема о рекурсивной неразрешимости проблемы остановки.

Стр. 43-44.

15. Теорема о рекурсивной неразрешимости проблемы самоприменимости.

Стр. 44.

16. Теорема о несуществовании алгоритма, определяющего по номеру ЧРФ, является ли она рекурсивной (теорема Клини).

Стр. 45.

17. μ- оператор и μ- теорема.

Стр. 46-47.

18. Теорема о несуществовании рекурсивной функции, которая ограничивает сверху число шагов произвольной ЧРФ в точках её определения.

Стр. 46-47.
Задачи

1. Пусть Доказать, что .

2. Пусть . Доказать существование такой , что .

3. Пусть - взаємно однозначна и . Доказать, что .

4. Пусть . Доказать: .

5. Пусть из задачи 4. Рассмотрим бинарное отношение на множестве подмножеств множества N:

.

Доказать, что - отношение эквивалентности.

6. Пусть - такие, что A=Arg α и для некоторого множества А. Доказать, что .

7. Доказать, что для любой существует , удовлетворяющая равенству .

8. Пусть для любой и . Доказать, что C=R.
V. Неразрешимые проблемы.
1. Доказать рекурсивную неразрешимость проблемы определения по номеру алгоритма, реализует ли он константную функцию.

Стр. 48-49.

2. Доказать рекурсивную неразрешимость проблемы определения по номеру алгоритма и произвольному числу, вычисляет ли этот алгоритм данное число.

Стр. 49.

3. Доказать рекурсивную неразрешимость проблемы определения по номеру алгоритма и двум произвольным числам, вычисляет ли этот алгоритм второе число, если первое он использует в качестве входной информации.

Стр. 49-50.

4. Доказать рекурсивную неразрешимость проблемы определения по номерам 2-х алгоритмов, реализуют ли они одинаковые функции.

Стр. 50.

5. Доказать рекурсивную неразрешимость проблемы определения по номеру алгоритма, вычисляет ли он бесконечное множество чисел.

Стр. 50-51.

6. Для заданного фиксированного числа доказать рекурсивную неразрешимость проблемы определения по номеру алгоритма, вычисляет ли этот алгоритм данное число.

Стр. 51.

7. Для заданного номера алгоритма разрешимой или рекурсивно неразрешимой является следующая проблема: по произвольному числу определить, вычисляет ли данный алгоритм это число.

Стр. 51-52.

8. Определение ЧРФ, продолжимой до рекурсивной функции. Теорема о существовании ЧРФ, которую нельзя продолжить до рекурсивной функции.

Стр. 52.

9. Теорема о существовании ЧРФ, которую нельзя получить из рекурсивной функции однократным применением оператора минимизации.

Стр. 52-53.

10. Определение сводимости проблем (множеств). Примеры.

Стр. 53-54.
Задачи.
1. Пусть Доказать, что .

2. Пусть . Доказать, что .

3. Пусть и . Доказать, что .

4. Показать существование таких х1 и х2, что обладает рекурсивной характеристической функцией, а - нет.

5. Пусть для фиксированного . Доказать, что .

6. Пусть



Доказать, что и не продолжима до рекурсивной.

7. Пусть и для фиксированного z0 . Доказать, что проблема А сводится к проблеме К.

8. Пусть и . Доказать, что проблема К сводится к проблеме А.
VI. Труднорешаемые задачи.
1. Полиномиальные и экспоненциальные алгоритмы.

Стр. 56-57.

2. Задачи, труднорешаемость которых доказуема. Проблема: P=NP-?

Стр. 58-59.

3. Понятие, сводимости задач за полиномиальное время. NP – полные задачи.

Стр. 59-60.

4. Формулировка теоремы о связи между временными сложностями детерминированных и недетерминированных алгоритмов.

Стр. 60.

5. Примеры NP – полных задач.

Стр. 61-62.
Перечень рекомендуемой литературы


  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. – М.: Мир, т. 1,2, 1978. – 1099 с.

  2. Рейуорд – Смит В. Дж. Теория формальных языков. – М.: Радио и связь, 1988. – 129 с.

  3. Хопкрофт Дж. Е., Ульман Дж. Формальные языки и автоматы. – М.: Мир, 1982. – 346 с.

  4. Трахтенброт Б. А. Алгоритмы и вычислительные автоматы. – М.: Советское радио, 1974. – 201 с.

  5. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972 – 624 с.

  6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.

Добавить документ в свой блог или на сайт

Похожие:

Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания по выполнению лабораторных работ по курсу «Теория...
Сар. Методические указания по выполнению лабораторных работ по курсу «Теория автоматического управления» для студентов направлений...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания и задания к самостоятельной работе студентов...
Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по курсу «Протоколы компьютерных...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания и варианты заданий для самостоятельной работы студентов
Основы вариационного исчисления. Ч. III: метод указания и варианты заданий для самостоятельной работы студентов III курса специальностей...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические рекомендации к самостоятельной и индивидуальной работе...
Формирование навыков самостоятельной работы происходит в процессе выполнения заданий по срс (самостоятельной работе студентов) и...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания к выполнению контрольных работ по курсу Отечественной...
Методические указания утверждены на заседании кафедры государственного управления и истории пгту «13» апреля 2005 г
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания по выполнению курсовой работы по дисциплине...
Методические указания предназначены для студентов, обучающихся по специальности 080507. 65«Менеджмент организации». В них предложены...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания и контрольные задания для студентов специальности...
Методические указания содержат тематический план, программу курса, задания и методические указания к выполнению контрольных работ,...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания и контрольные задания для студентов специальности...
...
Методические указания для самостоятельной работы студентов по курсу теория алгоритмов и вычислительных процессов icon Методические указания к выполнению курсовой работы для студентов...
Методические указания предназначены для студентов специальностей 200700 Радиотехника, 201600 Радиоэлектронные системы. В указаниях...
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции