Рабочая программа по дисциплине «теория алгоритмов и сложности» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная
| Вид материала | Рабочая программа |
СодержаниеПринципы построения Цели курса Учебно-тематический план Количество часов |
- Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика, 292.77kb.
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 81.9kb.
- Паспорт (государственный стандарт) Специальности «прикладная информатика (по областям)», 504.1kb.
- Рабочая программа дисциплины: интеллектуальные информационные системы для специальностей:, 369.71kb.
- Программа по курсу "Математика. Алгебра и геометрия" для специальности 080801 (351400), 143.45kb.
- Рабочая программа по курсу Проектирование информационных систем для специальностей, 202.08kb.
- Рабочая программа дисциплины для магистрантов направления «Прикладная математика, 128.62kb.
- Рабочая программа учебной дисциплины «теория систем и системный анализ» Направление, 223.11kb.
- Рабочая программа по курсу «Мировые информационные ресурсы» 351400 «Прикладная информатика, 315.91kb.
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 88.44kb.
Курс входит в раздел: национально-региональный (вузовский) компонент
- Принципы построения
Традиционно результаты данной науки относятся к следующим
разделам:
(1) классическая теория (идеальной) вычислимости,
(2) теория сложности вычислений,
(3) теория сложности алгоритмов (дескриптивной сложности),
(4) структурная теория сложности (одновременный учет
ограничений, рассматриваемых в разделах (2) и (3)).
Непосредственно наиболее близок к практике раздел (4).
Более того, все классические результаты предыдущих разделов
в настоящее время нетрудно трансформировать в результаты
раздела (4). Классические результаты необходимо, тем не менее,
изучать, во-первых, с целью получения общей культуры в знании
данного вопроса и его истории, во-вторых, - потому что
результаты первых разделов проще для изложения и могут быть
использованы для постепенного перехода к более сложным
вопросам. Однако, стоит подчеркнуть, что некоторые факты,
изучаемые в первых разделах носят неадекватный характер с точки
зрения практического применения. Наиболее яркие примеры этого:
- идеальная вычислимость ничего не говорит о практической
вычислимости, например, разрешимость множества истинных формул
ограниченной арифметики на поверку означает, что в настоящее
время мы обладаем разрешающим алгоритмом, даже не являющимся
элементарным по Кальмару, а выполнение его для некоторых формул,
запись которых, например, в системе TeX, занимает всего 1000
байт, параллельно на всех компьютерах, имеющихся сейчас в мире,
займет время, гораздо большее, чем время, прошедшее с
гипотетического "Большого взрыва" при образовании наблюдаемой
Вселенной;
- идеальная невычислимость может также означать только
отсутствие алгоритма, охватывающего все математически идеальное
бесконечное множество возможных аргументов функции, тогда как на
практике нужно вычислять определенную функцию только для
относительно небольших значений аргумента (хотя практически
идеальная невычислимость может быть и полезна: она
предотвращает появление совсем уж некорректных постановок
задач);
- асимптотический характер большинства традиционных сложностных
результатов также неадекватен: асимптотически время работы
n(log_2 n)2 считается хуже, чем время работы 10000 n log_2 n,
но те длины входных данных (n), при которых первое время
действительно становится хуже, неосуществимы в наблюдаемой
нами части Вселенной с помощью известных нам физических
эффектов; и наоборот, время работы 1.0001{n0.0001} с точки
зрения асимптотики должно считаться очень плохим: почти
экспоненциальным, но реальный его рост начинается также с
совершенно неосуществимых n: больше 10000{10000};
- традиционные модели вычислимости: машины Тьюринга, нормальные
алгоритмы и т.п., - очень далеки от практики, когда речь
заходит о конкретных (не асимптотических и даже иногда -
асимптотических) сложностных характеристиках вычислений;
относительно адекватной в этом отношении является модель РАМ.
Можно привести и массу других замечаний в этом же роде. Все это
говорит о том, что следует пересмотреть традиции преподавания
теории алгоритмов и сложности.
Предлагается сделать следующее.
Во-первых, надо взять три вида базовых моделей вычислений (три
вида нужны для иллюстрации тезиса Черча):
- равнодоступные адресные машины с сохраняемой в памяти
программой (РАСП), кроме всего прочего, это еще и математически
точная иллюстрация архитектуры Фон-Неймана (можно ее развить и
до параллельной архитектуры ПРАСП, что сейчас актуально);
иллюстрация методов программирования на такой модели заодно
является и экскурсом в историю информатики; для изучения
сложностных ограничений вычислимости изучается практически
точная модель семейств реальных компьютеров с сокращенным
набором команд: ограниченные РАСП (и ПРАСП) - ОРАСП (и ОПРАСП),
на которые накладываются ограничения по используемым
диапазонам адресов и чисел вообще; эти модели очень удобны для
того, чтобы приводить примеры практической относительной
неразрешимости, когда даются задачи, которые в идеале, вообще
говоря, можно решить алгоритмически, но для некоторых конкретных
сложностных ограничений они становятся неразрешимыми;
- для иллюстрации свойств замкнутости классов (ограниченной)
вычислимости удобно в качестве примера модели привести
определение вычислимости на основе идеального языка; лучше
всего для этой цели подходят идеализированные подмножества
реальных наиболее традиционных алгоритмических языков,
например, pascal и C (можно подобрать даже подходящее
"семантическое пересечение" этих языков); заодно это помогает
студентам понять, что представляет собой "ядро" этих языков,
избавившись от вторичных деталей; наиболее удачными
представляются чисто арифметические языки (работающие с
натуральными или целыми числами) и "структурные" языки,
работающие с бинарными деревьями или термами; возможно и
наложение сложностных ограничений на используемые данные;
арифметический язык удобно использовать для построения
ИНТЕРПРЕТАТОРА (универсального алгоритма) для РАСП (ОРАСП) и
эта конструкция удобно с самого начала излагается в сложностной
форме; меры сложности для этой модели - более грубые, чем для
РАСП, но легче поддаются оценке;
- в любом случае необходимы модели, основанные на рекурсивных
схемах: числовых, словарных и структурных (на термах); эти
модели - наиболее традиционные математические конструкции (с
точки зрения остальной математики); кроме того, с точки зрения
иллюстрации тезиса Черча, рекурсивые схемы могут
проиллюстрировать алгоритмы преобразования программ на
идеальных алгоритмических языках в программы РАСП; это также
является иллюстрацией понятия компилятора и одним из его
простейших примеров; рекурсивные схемы удобно определить так,
что они окажутся в результате сужением идеального
алгоритмического языка (который должен содержать подпрограммы,
в том числе и рекурсивные); семантика идеального
алгоритмического языка также удобно определяется через рекурсию
(возможно и преобразование - компиляция идеальных программ в
рекурсивные схемы).
В качестве вспомогательных моделей вычислимости с
ограниченной сложностью берутся модели, основанные на схемах из
логических элементов и на конечных автоматах (модель конечных
автоматов полезна в виду ее широкой известности и практического
использования многих связанных с ней понятий). Модели на схемах
из логических элементов нужны для получения конкретных примеров
задач большой сложности.
Во-вторых, излагаемые результаты должны сразу даваться и в
конкретном сложностном варианте, как можно более близком к
практике. Например, приводится не просто пример неразрешимого
множества, а излагается способ определения множеств,
неразрешимых при заданных сложностных ограничениях (и
разрешимых при других - более слабых ограничениях). При этом,
если быть ближе к практике, то фактически получается некоторое
комбинированное ограничение на размер программы, размер
используемой памяти и время работы. Надо подчеркнуть при этом,
что есть некоторый разрыв между нижними теоретическими
границами сложности и верхними практическими, более того, мы не
знаем, что будет происходить при ослаблении только ОДНОГО
ограничения - мы знаем, лишь, что если одновременно ослабить
ВСЕ (хотя и относительно немного), то задача из разряда
неразрешимых перейдет в разряд разрешимых.
В-третьих нужно с крайней осторожностью относиться к полным
задачам классов, для которых достаточно эффективные
универсальные разрешающие процедуры неизвестны: таким, как
NP-полные проблемы. Для многих из NP-полных задач известны
очень сложные сводимости к ним классически трудных задач. В
подобных случаях нужно анализировать не асимптотическую
сложность сводимости, а конкретные относительные границы
сложности вычислений: сводимость может быть настолько сложной,
что окажется бесполезной с практической точки зрения. С другой
стороны, иногда сама формулировка задачи в этом случае
оказывается непрактичной: например, задача о рюкзаке с
"суперастрономической" точностью. Следует заметить, что
результаты об относительной неразрешимости, хотя и в любом
случае негативны, но могут обладать "здоровым" и "нездоровым"
негативизмом. В первом случае мы строго обосновали конкретные
ограничения, во втором - ссылаемся на то, что задачу никто
еще не решил. От вторых формулировок следует избавляться,
заменяя их на относительные оценки сложности.
- Цели курса
Общие требования к курсам по теории алгоритмов и сложности
для специалистов по информатике
(разработаны на основе кн.: "Рекомендации по преподаванию
информатики в университетах" / Пер. с англ., С.-Петербург:
Изд-во СПбГУ, 2002)
Основная цель преподавания Теории алгоритмов и сложности для
будущих специалистов по информатике - дать им инструмент для
установления границ, при переходе за которые формулировки
задач по программированию становятся некорректными: задачи
становятся или неразрешимыми даже в принципе (в идеале), или
неразрешимыми с учетом конкретной возможности использования
вычислительных ресурсов. В свете этого некоторые традиции в
изложении этой науки в академической литературе нуждаются в
пересмотре для того, чтобы излагаемые результаты
формулировались в виде пригодном для их практического
применения без приложения дополнительных теоретических усилий.
- Учебно-тематический план
| № | Тема | Количество часов | ||
| Лекц | Лаб. | Сам | ||
| 1 | Математическая логика и теория алгоритмов | 2 | 1 | 3 |
| 2 | Виды алгоритмов | 2 | 1 | 3 |
| 3 | Магазинные автоматы. Нормальные алгоритмы. Регистровые машины | 2 | 1 | 3 |
| 4 | Равнодоступные адресные машины (РАМ) | 2 | 1 | 3 |
| 5 | Примитивно рекурсивные, частично-рекурсивные и общерекурсивные функции | 2 | 1 | 3 |
| 6 | Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов | 2 | 1 | 3 |
| 7 | Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса. | 2 | 1 | 3 |
| 8 | Программа машины Джонса как структура данных | 2 | 1 | 3 |
| 9 | Разрешимые и неразрешимые множества. Перечислимые и неперечислимые множества | 2 | 1 | 3 |
| 10 | Элементарные по Кальмару функции | 2 | 1 | 3 |
| 11 | Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности | 2 | 1 | 3 |
| 12 | Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи | 2 | 1 | 3 |
| 13 | On-line - вычисления, вычисления в реальное время | 2 | 1 | 3 |
| 14 | Автоматные вычисления. Регулярные множества | 2 | 1 | 3 |
| 15 | Регулярность автоматных и автоматность регулярных множеств | 2 | 1 | 3 |
| 16 | Связь логики и вычислимости | 2 | 1 | 3 |
| 17 | Доказательства как программы | 1 | 1 | |
| 18 | Нетрадиционные конструктивные теории | 1 | | 1 |