Мин. объем дисциплины: 3 з.е. (108 ч.).
Рекомендуемый объем дисциплины: 4 з.е. (144 ч.) – 30 ч. лек., 30 ч. лаб., 57 ч. сам. раб., 27 ч. экз.
Форма отчетности: экзамен.
Цель дисциплины
Ознакомление с основными положениями формальной теории алгоритмов, включая теорию вычислимости, теорию эффективности.
Задачи дисциплины:
- Овладение практическими навыками в области анализа эффективности алгоритмов.
- Формирования навыков решения алгоритмических задач.
- Овладение навыками проверки алгоритмической разрешимости и неразрешимости.
Преподаватели
Стась Андрей Николаевич, зав. кафедрой информатики ТГПУ, к.т.н., доцент.
Долганов Виталий Михайлович, старший преподаватель кафедры информатики ТГПУ, учитель информатики МБОУ СОШ №68, г. Томск.
Формируемые компетенции
ПК-1. Способен осваивать и использовать теоретические знания и практические умения и навыки в предметной области при решении профессиональных задач.
Содержание дисциплины в соответствии с требованиями ядра ВПО
Понятие алгоритма.
Интуитивное (неформальное) понятие алгоритма. Необходимость в формализации понятия «алгоритм». Подходы к формализации понятия «алгоритм».
Оценка эффективности алгоритма.
Элементарный шаг. Временная трудоемкость и ее асимптотический порядок. Трудоемкость в наихудшем. Трудоемкость в среднем. Оценка трудоемкости. Емкостная сложность.
Алгоритмы сортировки и поиска.
Внутренняя и внешняя сортировка. Простые методы. Пирамидальная сортировка. Быстрая сортировка Хоара. Сортировка слиянием. Цифровая сортировка (сортировка подсчетом). Бинарный поиск. Бинарный поиск по ответу. Поиск минимума в скользящем окне.
Теория вычислимости.
Понятие вычислимой функции. Рекурсивно-вычислимые функции. Разрешимые и перечислимые множества. Тезис Черча. Машины с неограниченными регистрами. Понятие программы. Нумерация программ и вычислимых функций. Диагональный метод. Теорема о параметризации. Существование универсальной программы. Пример невычислимой функции. Примеры алгоритмически-неразрешимых проблем. Теорема о неподвижной точке. Понятие машины Тьюринга. Формальное описание машины Тьюринга. Недетерминированные машины Тьюринга и недетерминированные алгоритмы. Мгновенные описания. Машины Поста. Нормальные алгоритмы Маркова.
NP-полные проблемы.
Формальные грамматики. Языки, иерархия языков по Хомскому. Языки и проблемы. Алгоритмическая сводимость проблем. Понятие NP-полноты.
Актуальность дисциплины
Теория алгоритмов является одной из базовых дисциплин теоретической информатики. В рамках дисциплины изучаются подходы к оценке возможности и эффективности решения алгоритмических задач, а также эффективные алгоритмы решения базовых задач. Изучение дисциплины способствует формированию алгоритмического стиля мышления, что является одной из базовых задач школьного курса информатики и ИКТ. Дисциплина способствует формированию межпредметных навыков на стыке информатики и математики.
Технологии реализации дисциплины
Реализация дисциплины предполагает курс лекций, направленных на изложение теоретической базы, лабораторные работы, направленные на формирование практических навыков в области решения алгоритмических задач и оценки их эффективности, самостоятельную работу студентов. Предполагается применение элементов проблемного обучения, проектной технологии, электронного обучения (видеоролики, анимации, иллюстрирующие работу изучаемых алгоритмов), командной работы обучающихся при решении практических задач. Технически целесообразно применение автоматизированных систем проверки задач на программирование.
