Учебно-методический комплекс по дисциплине 230100 Теория алгоритмов Направление подготовки
| Вид материала | Учебно-методический комплекс |
- Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
- Учебно-методический комплекс по дисциплине «Ботаника» Направление подготовки, 1843.23kb.
- Учебно-методический комплекс дисциплины б дв1 Теория систем и системный анализ Направление, 568.62kb.
- Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
- Учебно-методический комплекс по дисциплине опд. Ф. 04 Теория и методика обучения литературе, 2205.11kb.
- Учебно-методический комплекс умк учебно-методический комплекс теория и методика воспитания, 1435.61kb.
- Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов, 144.09kb.
- Учебно-методический комплекс по опд. Ф. 15 «Конституционное право зарубежных стран», 1206.51kb.
- Учебно-методический комплекс по дисциплине Теория систем Направление подготовки, 684.83kb.
- Учебно-методический комплекс дисциплины «Микроэкономика» Направление подготовки, 1978.69kb.
- СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ.
- Содержание учебного материала. Лекционный курс.
- Содержание учебного материала. Лекционный курс.
- Содержание практических занятий.
| | Определение машины Тьюринга. Применение машины Тьюринга к словам. | 2 |
| | Конструирование машин Тьюринга. | 2 |
| | Вычислимые по Тьюрингу функции. | 2 |
| | Основная гипотеза теории алгоритмов. Машины Тьюринга и современные ЭВМ. | 2 |
| | Тьюрингов подход к понятию «алгоритм». Алгоритмически разрешимые и неразрешимые проблемы. | 2 |
| | Нормальные алгоритмы Маркова. | 2 |
| 7. | Эквивалентность различных теорий алгоритмов. | 2 |
| 8. | Рекурсивные функции. Тезис Черча. | 2 |
| 9. | Неразрешимые алгоритмические проблемы. | 2 |
| 10. | Эффективные операции над вычислимыми функциями. | 2 |
| 11. | Преобразование символьных данных в компьютере. | 2 |
| 12. | Алгоритмы символьных преобразований. | 2 |
| 13. | Числа, многочлены, выражения, дифференцирование, интегрирование. | 2 |
| | | |
| | ВСЕГО: | 26 |
III.Содержание учебной дисциплины
1. Содержание лекций
Лекция № 1
Тема: Интуитивное представление об алгоритмах..
Содержание:
- Понятие алгоритма и его характерные черты.
- Уточнение понятия алгоритма.
- Алгоритм как формальная математическая система.
Лекция № 2
Тема: Неформальное понятие алгоритма
Содержание:
- Свойства алгоритма и его характерные черты.
- Формы представления алгоритмов.
Лекция № 3
Тема: Разрешимые и перечислимые множества. Вычислимые функции. Частично рекурсивные и общерекурсивные функции.
Содержание:
- Разрешимые и перечислимые множества.
- Диагональный метод.
- Вычислимые функции.
- Частично рекурсивные и общерекурсивные функции.
- Тезис Черча.
Лекция №4
Тема: Определение машины Поста
Содержание:
1.Абстрактные машины.
2.Система команд.
3.Примеры схем машины Поста.
Лекция №5
Тема: Применение машины Тьюринга к словам. Конструирование машин Тьюринга.
Содержание:
1.Абстрактные машины.
2.Система команд.
3.Примеры схем машины Тьюринга.
Лекция №6
Тема: Вычислимые по Тьюрингу функции. Основная гипотеза теории алгоритмов. Машины Тьюринга и современные ЭВМ.
Содержание:
1. Вычислимые по Тьюрингу функции.
2. Основная гипотеза теории алгоритмов.
3. Машины Тьюринга и современные ЭВМ.
Лекция №7
Тема: Тьюрингов подход к понятию «алгоритм». Алгоритмически разрешимые и неразрешимые проблемы.
Содержание:
1. Тьюрингов подход к понятию «алгоритм».
2. Алгоритмически разрешимые проблемы.
3. Алгоритмически неразрешимые проблемы
Лекция № 8
Тема: Ассоциативные исчисления. Нормальные алгоритмы Маркова.
Содержание:
- Основные понятия ассоциативного исчисления
- Способы композиции нормальных алгоритмов.
Лекция № 9
Тема: Эквивалентность различных теорий алгоритмов.
Содержание:
1.Основные понятия ассоциативного исчисления
2. Эквивалентность различных теорий алгоритмов
Лекция № 10
Тема: Тезис Чёрча. Рекурсивные функции.
Содержание:
1.Исчисление высказываний. Аксиомы и правила вывода.
2.Абстрактные формальные системы.
3.Языки и грамматики.
Лекция № 11
Тема: Эффективные операции над вычислимыми функциями.
Содержание:
1. Эффективные операции над вычислимыми функциями.
2.Абстрактные формальные системы.
Лекция № 12
Тема: Языки. Иерархия языков по Хомскому. Языки и машины. Основные меры сложности вычисления.
Содержание:
1. Языки. Иерархия языков по Хомскому.
2. Языки и машины.
3. Основные меры сложности вычисления.
Лекция № 13
Тема: Неразрешимые алгоритмические проблемы (обзор). Понятие о сложности решения задач. Приложения теории алгоритмов в информатике
Содержание:
1.Неразрешимость проблемы распознавания выводимости в математической логике.
2.Неразрешимость проблемы распознавания самоприменимости.
3.Проблема эквивалентности слов для ассоциативных вычислений.
4.Неразрешимость десятой проблемы Гильберта о диофантовых уравнениях.
5.Индивидуальная и массовая задачи, временная сложность алгоритма. Классы P и NP.
2. Содержание практических занятий
Лабораторная работа № 1,2. Поиск и сортировка данных.
Цель работы: Изучить алгоритмы поиска и сортировки данных.
Рекомендации к самостоятельной работе:
Изучить материал лекции «Способы обработки данных: перебор, поиск, сортировка элементов. Последовательный и бинарный поиск».
Содержание работы:
- Сформировать массив a[1..n], элементы которого выбираются случайным образом из интервала [100, 200]. Определить, содержит ли он заданное число. Если элемент найден, то удалить его из массива.
- Задан массив В[1..20]. Отсортировать все элементы, стоящие на нечетных местах по невозрастанию.
- Задана матрица NxN. Отсортировать четные строки по невозрастанию.
Форма представления отчета:
Отчет представить в письменном виде, который должен содержать:
алгоритм в виде блок-схемы, программу и результат ее выполнения;
Лабораторная работа № 3. Моделирование стека.
Цель работы: Отработка практических навыков по разработке основных этапов решения задачи моделирования стека.
Рекомендации к самостоятельной работе:
Изучить материал лекции «Понятие о структурах данных. Моделирование ряда структур данных: стека, очереди, списка».
Содержание работы:
- Заполнить стек 10 случайными числами из интервала [-10;20]. Просмотреть содержимое стека. Найти сумму положительных чисел, хранящихся в стеке.
- Сформировать стек из 5 чисел. Найти произведение 3-го и 4-го чисел из стека. Результат поместить в стек.
- Заполнить стек 10 случайными числами из интервала [-10;20]. Найти максимальное число.
Форма представления отчета:
Отчет представить в письменном виде, который должен содержать:
алгоритм в виде блок-схемы, программу и результат ее выполнения;
Лабораторная работа № 4. Моделирование очереди.
Цель работы: Отработка практических навыков по разработке основных этапов решения задачи моделирования очереди.
Рекомендации к самостоятельной работе:
Изучить материал лекции «Понятие о структурах данных. Моделирование ряда структур данных: стека, очереди, списка».
Содержание работы:
- Сформировать очередь из 8 чисел. Устроить модуль разности между 2-м и 3-м числом очереди.
- Заполнить очередь 8 случайными числами из интервала [0;50]. Найти среднее арифметическое четных чисел.
- Сформировать очередь из 8 чисел. Найти сумму 2-го и 4-го чисел из очереди.
Форма представления отчета:
Отчет представить в письменном виде, который должен содержать:
алгоритм в виде блок-схемы, программу и результат ее выполнения;
Лабораторная работа № 5. Рекурсия.
Цель работы: Изучить рекурсивные алгоритмы.
Рекомендации к самостоятельной работе:
Изучить материал лекции «Рекурсия».
Содержание работы:
- Вычислить (a! + b!)/a!, используя рекурсивную функцию вычисления факториала
- Вычислить (1+2+3+4+5)/( 1+2+3+4+5+6+7+8), используя рекурсивную функцию вычисления суммы первых n натуральных чисел.
- Составить рекурсивную функцию вычисления n-го члена последовательности: а1= 0, ai = 2*ai-1+i. Найти произведение 3-го и 7-го членов последовательности.
- Составить рекурсивную функцию нахождения суммы n членов арифметической прогрессии 1, 3, …Найти сумму с 5-го по 10-й членов прогрессии
Форма представления отчета:
Отчет представить в письменном виде, который должен содержать:
алгоритм в виде блок-схемы, программу и результат ее выполнения;
Практическое занятие № 6.
Тема: Частично рекурсивные и общерекурсивные функции.
Цель работы: Ознакомиться с базисными функциями и основными операторами.
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 9, 10, 13, 15, 19],
План:
Нуль-функция, функция следования, функция проекции.
Суперпозиция функций.
Схема примитивной рекурсии.
Операция минимизации.
Форма представления отчета: выполнить задание [7 , с. 124, 19, с. 51].
Практическое занятие № 7
Тема: Машины Тьюринга и Поста
Цель работы: Ознакомиться с автоматным подходом к формальному определению алгоритма.
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 13, 15, 17, 19, 20],
План:
Устройство машины Тьюринга. Программа.
Реализация алгоритма в машине Тьюринга.
Основная гипотеза теории алгоритмов.
Форма представления отчета: выполнить задание [7 , с. 136, 17, с.46, 19, с.52-57].
Практическое занятие № 8
Тема: Машины Тьюринга и Поста
Цель работы: Ознакомиться с автоматным подходом к формальному определению алгоритма.
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 13, 15, 17, 19, 20],
План:
Устройство машины Поста. Программа.
Реализация алгоритма в машине Поста.
Основная гипотеза теории алгоритмов.
Форма представления отчета: выполнить задание [7 , с. 136, 17, с.46, 19, с.52-57].
Практическое занятие № 9
Тема: Машины Тьюринга и Поста
Цель работы: Ознакомиться с автоматным подходом к формальному определению алгоритма.
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 13, 15, 17, 19, 20],
План:
Реализация алгоритма в машине Тьюринга.
Реализация алгоритма в машине Поста.
Основная гипотеза теории алгоритмов.
Форма представления отчета: выполнить задание [7 , с. 136, 17, с.46, 19, с.52-57].
Практическое занятие № 10
Тема: Машины Тьюринга и Поста
Цель работы: Ознакомиться с автоматным подходом к формальному определению алгоритма.
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 13, 15, 17, 19, 20],
План:
Реализация алгоритма в машине Тьюринга.
Реализация алгоритма в машине Поста.
Форма представления отчета: выполнить задание [7 , с. 136, 17, с.46, 19, с.52-57].
Практическое занятие № 11
Тема: Нормальные алгоритмы Маркова.
Цель работы: Ознакомиться с языковым подходом к формальному определению алгоритма.
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 18, 19, 20],
План:
Основные понятия.
Способы композиции нормальных алгоритмов.
Решение задач.
Форма представления отчета: выполнить задание [20 , с. 63].
Практическое занятие № 12
Тема: Преобразование символьных данных в компьютере.
Цель работы: Ознакомиться с языковым подходом к формальному определению алгоритма.
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 18, 19, 20],
План:
Основные понятия.
Способы композиции нормальных алгоритмов.
Решение задач.
Форма представления отчета: выполнить задание [20 , с. 63].
Практическое занятие № 13
Тема: Алгоритмы символьных преобразований. (числа, многочлены, выражения)
Цель работы: Ознакомиться с основными алгоритмами работы с символьными переменными
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 18, 19, 20],
План:
Основные алгоритмы работы с символьными переменными
Составление алгоритмов
Форма представления отчета: выполнить задание [20 , с. 63].
Практическое занятие № 14
Тема: Алгоритмы символьных преобразований. (дифференцирование, интегрирование).
Цель работы: Ознакомиться с основными алгоритмами работы с символьными переменными
Рекомендации к самостоятельной работе:
Ознакомиться с дополнительными материалами [4, 5, 7, 8, 18, 19, 20],
План:
Основные алгоритмы работы с символьными переменными
Составление алгоритмов
Решение задач.
Форма представления отчета: выполнить задание [20 , с. 63].