МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«УДМУРТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет информационных технологий и вычислительной техники
Кафедра теоретических основ информатики
УТВЕРЖДАЮ
_______________________
«______» ________________20__ г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
«Алгоритмы и анализ сложности»
Степень выпускника
БАКАЛАВР
по направлению «010300 Фундаментальная информатика и информационные технологии»
Форма обучения
очная
Ижевск 2013
Введение
Теория алгоритмов и сложности является основой информатики и программной инженерии. Фактическая производительность программной системы зависит от двух факторов: во-первых, от применяемых в ней алгоритмов и, во-вторых, от эффективности реализации на различных уровнях. Поэтому разработка хорошего алгоритма имеет решающее значение для любой программной системы. Кроме того, изучение алгоритмов и сложности позволяет более глубоко вникнуть в задачу и может подсказать методы решения, не зависящие от языка программирования, парадигмы программирования, аппаратного обеспечения и других аспектов реализации.
Важной основной частью знаний в области информатики является способность выбрать алгоритм, подходящий для решения данной задачи, или доказать, что такого алгоритма не существует. Эта способность основывается на знании класса алгоритмов, которые предназначены для решения определенного набора известных задач, понимании их сильных и слабых сторон, применимости различных алгоритмов в данном контексте. Эффективность является важнейшим вопросом в данной области.
1. Цель и задачи освоения дисциплины
Основная цель преподавания Теории алгоритмов и сложности для будущих специалистов по информатике – дать им инструмент для установления границ, при переходе за которые формулировки задач по программированию становятся некорректными: задачи становятся или неразрешимыми даже в принципе (в идеале), или неразрешимыми с учетом конкретной возможности использования вычислительных ресурсов. В свете этого некоторые традиции в изложении этой науки в академической литературе нуждаются в пересмотре для того, чтобы излагаемые результаты формулировались в виде пригодном для их практического применения без приложения дополнительных теоретических усилий.
Традиционно результаты данной науки относятся к следующим разделам:
(1) классическая теория (идеальной) вычислимости,
(2) теория сложности вычислений,
(3) теория сложности алгоритмов (дескриптивной сложности),
(4) структурная теория сложности (одновременный учет ограничений, рассматриваемых в разделах (2) и (3)).
Непосредственно наиболее близок к практике раздел (4).Более того, все классические результаты предыдущих разделов в настоящее время нетрудно трансформировать в результаты раздела (4). Классические результаты необходимо, тем не менее, изучать, во-первых, с целью получения общей культуры в знании данного вопроса и его истории, во-вторых, потому что результаты первых разделов проще для изложения и могут быть использованы для постепенного перехода к более сложным вопросам. Однако, стоит подчеркнуть, что некоторые факты, изучаемые в первых разделах носят неадекватный характер с точки зрения практического применения. Наиболее яркие примеры этого:
- идеальная вычислимость ничего не говорит о практической вычислимости, например, разрешимость множества истинных формул ограниченной арифметики на поверку означает, что в настоящее время мы обладаем разрешающим алгоритмом, даже не являющимся элементарным по Кальмару, а выполнение его для некоторых формул, запись которых, например, в системе TeX, занимает всего 1000байт, параллельно на всех компьютерах, имеющихся сейчас в мире, займет время, гораздо большее, чем время, прошедшее с гипотетического "Большого взрыва" при образовании наблюдаемой Вселенной;
- идеальная не вычислимость может также означать только отсутствие алгоритма, охватывающего все математически идеальное бесконечное множество возможных аргументов функции, тогда как на практике нужно вычислять определенную функцию только для относительно небольших значений аргумента (хотя практически идеальная не вычислимость может быть и полезна: она предотвращает появление совсем уж некорректных постановок задач);
- асимптотический характер большинства традиционных сложностных результатов также неадекватен: асимптотически время работы n(log_2 n)^2 считается хуже, чем время работы 10000 n log_2 n, но те длины входных данных (n), при которых первое время действительно становится хуже, неосуществимы в наблюдаемой нами части Вселенной с помощью известных нам физических эффектов; и наоборот, время работы 1.0001^{n^0.0001} с точки зрения асимптотики должно считаться очень плохим: почти экспоненциальным, но реальный его рост начинается также с совершенно неосуществимых n: больше 10000^{10000};
- традиционные модели вычислимости: машины Тьюринга, нормальные алгоритмы и т.п., - очень далеки от практики, когда речь заходит о конкретных (не асимптотических и даже иногда -асимптотических) сложностных характеристиках вычислений; относительно адекватной в этом отношении является модель РАМ.
В сведе вышесказанного в настоящем курсе делается следующее.
Во-первых, берутся три вида базовых моделей вычислений (три вида нужны для иллюстрации тезиса Черча):
- равнодоступные адресные машины с сохраняемой в памяти программой (РАСП), кроме всего прочего, это еще и математически точная иллюстрация архитектуры Фон-Неймана (можно ее развить идо параллельной архитектуры ПРАСП, что сейчас актуально);иллюстрация методов программирования на такой модели заодно является и экскурсом в историю информатики; для изучения сложностных ограничений вычислимости изучается практически точная модель семейств реальных компьютеров с сокращенным набором команд: ограниченные РАСП (и ПРАСП) - ОРАСП (и ОПРАСП),на которые накладываются ограничения по используемым диапазонам адресов и чисел вообще; эти модели очень удобны для того, чтобы приводить примеры практической относительной неразрешимости, когда даются задачи, которые в идеале, вообще говоря, можно решить алгоритмически, но для некоторых конкретных сложностных ограничений они становятся неразрешимыми;
- для иллюстрации свойств замкнутости классов (ограниченной)вычислимости удобно в качестве примера модели привести определение вычислимости на основе идеального языка; лучше всего для этой цели подходят идеализированные подмножества реальных наиболее традиционных алгоритмических языков, например, pascal и C (можно подобрать даже подходящее" семантическое пересечение" этих языков); заодно это помогает студентам понять, что представляет собой "ядро" этих языков, избавившись от вторичных деталей; наиболее удачными представляются чисто арифметические языки (работающие с натуральными или целыми числами) и "структурные" языки, работающие с бинарными деревьями или термами; возможно и наложение сложностных ограничений на используемые данные; арифметический язык удобно использовать для построения ИНТЕРПРЕТАТОРА (универсального алгоритма) для РАСП (ОРАСП) и эта конструкция удобно с самого начала излагается в сложностной форме; меры сложности для этой модели - более грубые, чем для РАСП, но легче поддаются оценке;
- в любом случае необходимы модели, основанные на рекурсивных схемах: числовых, словарных и структурных (на термах); эти модели - наиболее традиционные математические конструкции (сточки зрения остальной математики); кроме того, с точки зрения иллюстрации тезиса Черча, рекурсивые схемы могут проиллюстрировать алгоритмы преобразования программ на идеальных алгоритмических языках в программы РАСП; это также является иллюстрацией понятия компилятора и одним из его простейших примеров; рекурсивные схемы удобно определить так, что они окажутся в результате сужением идеального алгоритмического языка (который должен содержать подпрограммы, в том числе и рекурсивные); семантика идеального алгоритмического языка также удобно определяется через рекурсию(возможно и преобразование - компиляция идеальных программ в рекурсивные схемы).
В качестве вспомогательных моделей вычислимости с ограниченной сложностью берутся модели, основанные на схемах излогических элементов и на конечных автоматах (модель конечных автоматов полезна в виду ее широкой известности и практического использования многих связанных с ней понятий). Модели на схемах из логических элементов нужны для получения конкретных примеров задач большой сложности.
Во-вторых, излагаемые результаты сразу даются и в конкретном сложностном варианте, как можно более близком к практике. Например, приводится не просто пример неразрешимого множества, а излагается способ определения множеств, неразрешимых при заданных сложностных ограничениях (и разрешимых при других - более слабых ограничениях). При этом, если быть ближе к практике, то фактически получается некоторое комбинированное ограничение на размер программы, размер используемой памяти и время работы. Надо подчеркнуть при этом, что есть некоторый разрыв между нижними теоретическими границами сложности и верхними практическими, более того, мы незнаем, что будет происходить при ослаблении только ОДНОГО ограничения - мы знаем, лишь, что если одновременно ослабить ВСЕ (хотя и относительно немного), то задача из разряда неразрешимых перейдет в разряд разрешимых.
В-третьих, с крайней осторожностью даются полные задачи классов, для которых достаточно эффективные универсальные разрешающие процедуры неизвестны: таким, как NP-полные проблемы. Для многих из NP-полных задач известны очень сложные сводимости к ним классически трудных задач. В подобных анализируется не асимптотическая сложность сводимости, а конкретные относительные границы сложности вычислений: сводимость может быть настолько сложной, что окажется бесполезной с практической точки зрения. С другой стороны, иногда сама формулировка задачи в этом случае оказывается непрактичной: например, «задача о рюкзаке» с «суперастрономической» точностью. Следует заметить, что результаты об относительной неразрешимости, хотя и в любом случае негативны, но могут обладать "здоровым" и "нездоровым" негативизмом. В первом случае мы строго обосновали конкретные ограничения, во втором - ссылаемся на то, что задачу никто еще не решил. От вторых формулировок следует избавляться, заменяя их на относительные оценки сложности.
Задачи освоения дисциплины:
После изучения теоретических разделов курса и выполнения практических занятий в объеме рабочей программы студент должен
- знать и уметь использовать основные понятия и методы теории сложности алгоритмов и вычислений: модели вычислимости, статические и динамические меры сложности алгоритмов и вычислений, сложностные классы и их иерархии, доказуемо сложные задачи, описательную сложность объектов, алгоритмическое определение случайности и его свойства;
- иметь опыт оценки динамической и статической сложности алгоритмов;
- иметь представление о соотношении практической и теоретической вычислимости.
2. Место дисциплины в структуре ООП бакалавриата
Курс входит в базовую (общепрофессиональную) часть профессионального цикла дисциплин основной образовательной программы бакалавриата по направлению «010300 Фундаментальная информатика и информационные технологии» в Удмуртском университете.
Ядро курса – сложностные модели вычислимости, с помощью которых ведется изложение всего остального материала. Курс для начала освоения требует знания курсов «Дискретная математика», «Математическая логика и теория алгоритмов».
Полученные знания закладывают представления о структуре сложности вычислений и алгоритмов, используемых в программировании, в представлении знаний, в информационных и интеллектуальных системах. Знание основ теории сложности алгоритмов и вычислений дает возможность бакалавру грамотно, с математической строгостью, формулировать свои профессиональные задачи, оценивать качество функционирования построенных информационных и вычислительных систем.
Для успешного освоения дисциплины должны быть сформированы умения и навыки универсальных способов деятельности и ключевых компетенций, формируемых на этапе основного общего образования. В этом направлении приоритетными для учебной дисциплины «Анализ алгоритмов и сложности» являются:
В познавательной деятельности:
определение существенных характеристик изучаемого объекта;
самостоятельное создание алгоритмов деятельности;
формулирование полученных результатов.
В информационно-коммуникативной деятельности:
поиск нужной информации по заданной теме;
умение развернуто обосновывать суждения, давать определения, приводить доказательства;
владение основными видами публичных выступлений, следование этическим нормам и правилам ведения диалога.
В рефлексивной деятельности:
понимание ценности образования как средства развития культуры личности;
объективное оценивание своих учебных достижений, поведения, черт своей личности;
владение навыками организации и участия в коллективной деятельности.
Программа дисциплины построена линейно-хронологически. В ней выделены разделы: теоретический, практический и контрольный.
В курсе выделено 7 основных направлений:
основы анализа алгоритмов,
распределенные алгоритмы,
основы теории вычислимости,
классы сложности P и NP,
теория автоматов,
углубленный анализ алгоритмов,
параллельные алгоритмы.
Курс имеет практическую часть в виде практических занятий с преподавателем в аудитории и выполнения некоторых домашних заданий. Оценка знаний и умений студентов проводится с помощью тестирования, проверки зачетных заданий и экзамена.
3. Компетенции обучающегося, формируемые
в результате освоения дисциплины
«Анализ алгоритмов и сложности»
Процесс изучения дисциплины направлен на формирование следующих компетенций:
- владение основными методами, способами и средствами получения, хранения, переработки информации, иметь навыки работы с компьютером как средством управления информацией (ОК-12);
- способность разрабатывать и реализовывать методы и механизмы оценки и анализа функционирования средств и систем информационных технологий (ПК-3);
-детальное знание методов и базовых алгоритмов обработки информационных структур, методов анализа сложности алгоритмов (ПК-17).
В результате освоения дисциплины обучающийся должен:
Знать/понимать:
теоретические основы анализа алгоритмов и сложности вычислений: используемые сложностные модели вычислимости, динамические и статические меры сложности, наиболее важные сложностные классы, оценки сложности и разрешимости важных массовых проблем;
способы использования сложностных моделей вычислимости;
языки моделей теории алгоритмов;
Уметь:
формулировать утверждения о сложности решаемых задач и алгоритмов их решения;
строить доказательства и опровержения утверждений об алгоритмической и вычислительной сложности;
формулировать известные задачи информатики и математики в виде задач построения алгоритмов в заданных сложностных классах;
оценивать алгоритмическую сложность практических задач;
применять методы теории сложности при построении математических моделей задач информатики.
Владеть:
знаниями основ теории сложности алгоритмов и вычислений;
системой практических умений и навыков построения и использования оценок вычислительной и алгоритмической сложности;
навыками техники проверки принадлежности алгоритмов заданным сложностным классам;
методикой решения задач построения алгоритмов ограниченной вычислительной сложности.
Использовать приобретенные знания и умения в практической деятельности для:
решения практических задач доказательства и проверки утверждений о сложностных оценках алгоритмов и задач;
создания компьютерных программ и информационных систем с учётом сложностных ограничений.
4. Структура дисциплины по видам учебной работы.
Виды учебной работы
|
Всего часов/
зачетных
единиц
|
Семестры
|
III
|
IV
|
V
|
VI
|
Аудиторные занятия (всего)
|
68
(2 зач. един.)
|
-
|
-
|
-
|
68
|
В том числе:
|
-
|
-
|
-
|
-
|
-
|
Лекции
|
34
|
-
|
-
|
-
|
34
|
Практические занятия
|
34
|
-
|
-
|
-
|
34
|
Вид промежуточной аттестации (зачет, экзамен)
|
Экзамен 72
|
-
|
-
|
-
|
Экзамен 72
|
Общая трудоемкость (в часах)
|
144
|
-
|
-
|
-
|
144
|
№
|
Название темы
|
Всего часов по дисциплине
|
Аудиторные часы
|
Самостоятельная работа
|
Формы
|
|
Лекции
|
Практические
|
контроля
|
Компетенции
|
1
|
Математическая логика и теория алгоритмов
|
5
|
2
|
2
|
1
|
Тест
|
ОК 12, ПК 3, 17
|
2
|
Виды алгоритмов
|
5
|
2
|
2
|
1
|
Тест
|
ОК 12, ПК 3, 17
|
3
|
Магазинные автоматы. Нормальные алгоритмы. Регистровые машины
|
5
|
2
|
2
|
1
|
Тест
|
ОК 12, ПК 3, 17
|
4
|
Равнодоступные адресные машины (РАМ)
|
5
|
2
|
2
|
1
|
Тест
|
ОК 12, ПК 3, 17
|
5
|
Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
6
|
Примитивно рекурсивные предикаты, множества и отношения.
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
7
|
Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале.
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
8
|
Программа машины Джонса как структура данных
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
9
|
Разрешимые и неразрешимые множества
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
10
|
Элементарные по Кальмару функции
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17 4,2.3
|
11
|
Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 174,2.3
|
12
|
Методы оценки сложности вычислений и алгоритмов.
Доказуемо трудные задачи. Полные переборные задачи
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 174,2.3
|
13
|
On-line - вычисления, вычисления в реальное время
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17.4,2.3
|
14
|
Автоматные вычисления. Регулярные множества
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
15
|
Регулярность автоматных и автоматность регулярных множеств
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
16
|
Связь логики и вычислимости
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
17
|
Логический синтез алгоритмов ограниченной вычислительной сложности.
|
4
|
2
|
2
|
0
|
Тест
|
ОК 12, ПК 3, 17
|
|
Итого
|
72
|
34
|
34
|
4
|
|
|
5. Содержание дисциплины
5.1. Содержание разделов дисциплины
Раздел 1. Теоретический раздел
Теоретический раздел программы включает в себя необходимый минимум знаний в области теории сложности алгоритмов и вычислений. Формирует у студента систему научно-практических знаний и отношение к проблематике теории сложности.
|
