Образовательный комплекс «Анализ и разработка алгоритмов»

Образовательный комплекс
«Анализ и разработка алгоритмов»

Техническое задание

Лист регистрации изменений

Дата	Автор изменения	Номер версии	Комментарии
29.05.03		1.0	Создание документа
30.05.03		1.1	Техническая правка

Авторский коллектив

- к. ф.-м. н., доц.

- д. ф.-м. н., проф.

- аспирант.

Корепов - студент ф-та ВМК, 4 курс.

Содержание

Цели и задачи образовательного комплекса. 5

Области применения и возможности использования. 5

Планируемые результаты... 5

Обоснование необходимости разработки образовательного комплекса. 6

Характеристика состояния области. 6

Имеющийся задел коллектива. 7

Новизна предлагаемого комплекса. 7

Технические требования. 7

Требования к учебнику. 7

Требования к программной лаборатории. 8

Требования к презентации. 8

Условия эксплуатации. 8

Среда разработки. 8

Сроки и этапы работы... 8

Краткая программа курса. 9

План лабораторного практикума. 11

Примеры тем для лабораторных работ: 11

Требования к описанию лабораторных работ. 11

Требования к оформлению отчета. 12

Литература. 12

Цели и задачи образовательного комплекса

·  Изложение в едином комплексе наиболее важных теоретических и прикладных вопросов теории алгоритмов, методов анализа сложности алгоритмов и приемов и методов их эффективизации.

·  Знакомство с основными теоретическими моделями вычислений - словарными, числовыми, логическими.

·  Изучение структур данных общего назначения, методов их реализации в адресуемой памяти компьютера.

·  Анализ сложности основных операций со структурами данных общего назначения, включая математические результаты, полученные в мире в последние годы и не вошедшие в учебную литературу.

·  Знакомство с методами решения широко используемых математических задач, решаемых на основе теории графов

Области применения и возможности использования

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

Планируемые результаты

В комплект поставки образовательного комплекса входят:

·  учебная монография по анализу и разработке алгоритмов,

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

·  описание лабораторных работ отдельной брошюрой и в электронной форме,

·  техническое задание на разработку программной системы предназначенной для изучения структурных и метрических свойств графов.

·  презентация образовательного комплекса.

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

Обоснование необходимости разработки образовательного комплекса

Характеристика состояния области

В настоящее время наблюдается существенный разрыв между теоретическими знаниями в области прикладной математики и информатики и технологиями использования вычислительных автоматов. Причина такого разрыва представляется в том ускоренном темпе, в котором развивается вычислительная техника. У многих возникает желание объяснить разрыв отставанием в области теории. С этим трудно согласиться. Массовое образование в области технологий оставляет на обочине фундаментальные знания, при этом говорится, что «старые» знания не годятся в новых условиях.

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

Не забывая, что основной, реалистичной моделью вычислительного устройства на сегодняшний день является модель RAM - равнодоступная адресная машина с косвенной адресацией, мы уделяем внимание и таким моделям как АБАК, машина Тьюринга, словарные и логические модели. Не можем обойти вниманием и проблему P=NP? Вопрос можно ли недетерминированные полиномиальные алгоритмы заменить детерминированными, тоже полиномиальными, важен, поскольку подразумевает важную технику сведения одних задач к другим. И хотя этот вопрос на сегодняшний день открыт, те исследования, которые ведутся вокруг него, наверняка будут иметь прикладное значение и в будущем.

Важным элементом образования считаем приобретение опыта разработки алгоритмов в простейших моделях вычислений, таких как машина Тьюринга и Абак. Использование таких моделей позволяет на простейшем материале столкнуться с проблемой доказательства правильности алгоритма, и ощутить разницу между статическим представлением алгоритма и динамическим характером его функционирования.

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

Важным считаем изучение структурных и метрических свойств графов, их использование при описании отношений между объектами и знакомство с алгоритмами решения структурных и метрических задач на графах.

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

Имеющийся задел коллектива

Разрабатываемый комплекс основан на курсах лекций и лабораторных практикумах, на протяжении трех лет проводимых членами творческого коллектива на факультете ВМК Нижегородского госуниверситета и по программе EEP в INNL. Творческий коллектив состоит из специалистов в области дискретной математики, Имеются конспекты лекций, написанные и частично содержащие планируемый учебный материал и примеры описания ряда лабораторных работ, подготовленные и

Новизна предлагаемого комплекса

Разрабатываемый комплекс предназначен, прежде всего, для будущих разработчиков программного обеспечения современных компьютерных технологий. Поэтому учебный материал содержит теорию сложности алгоритмов и описания структур данных, общего назначения. Особое внимание уделяется сложности операций над этими структурами. Методам решения классов задач, работы с графами.

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

Замысел проекта соответствует требованиям учебного плана новой специальности «Информационные технологии», разрабатываемого в настоящее время по заказу министерства образования.

Технические требования

Требования к учебнику

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

Учебник должен быть подготовлен в формате Microsoft Word, PDF, HTML. Учебник должен содержать иллюстрации и гиперссылки, позволяющие легко перемещаться по тексту.

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

Требования к программной лаборатории

Программная лаборатория должна содержать описания лабораторных работ, выполнение которых требует активного программирования и использования пакетов профессиональных прикладных программ.

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

Требования к презентации

Данный документ представляет собой презентацию Microsoft PowerPoint и содержит в иллюстративной форме общее описание учебного материала его краткую характеристику и способы его освоения.

Условия эксплуатации

Может использоваться как учебное пособие по лекционному курсу (или по лекционным курсам), в том числе при дистанционной форме обучения. Выполнение практических заданий и лабораторных работ предполагает использование персональной вычислительной техники типа IBM PC с процессором класса не ниже Pentium., работающей под управлением операционных систем Windows 9х или Windows NT и выше.

Среда разработки

Учебник, описание алгоритмов, пользовательская документация	Microsoft Word, Maple, Acrobat Reader
Программная лаборатория	Любая система программирования
Презентация	Microsoft PowerPoint

Сроки и этапы работы

№	Этап	Результаты	Срок
1.	Анализ требований	Пояснительная записка Техническое задание Краткая программа курса План лабораторного практикума Презентация	30.05.2003
2.	Разработка эскизного проекта	Эскизные варианты: электронного учебника, программной лаборатории, презентации курса	15.09.2003
3.	Подготовка рабочего проекта	Рабочие варианты: электронного учебника, программной лаборатории, презентации курса, руководства пользователя, справочного руководства	15.12.2003
4.	Апробация курса	Предложения по развитию и совершенствованию курса	31.12.2001

Краткая программа курса

Теоретические модели вычислений

1.  Словарный и числовой подходы к формированию моделей вычислений. Частично-рекурсивные функции, абак, машины Тьюринга и Поста, алгорифмы Маркова, МНР – машина с неограниченными регистрами, РАМ – равнодоступная адресная машина с косвенной адресацией, РАСП – равнодоступная адресная машина с хранимой программой, логическое программирование. Тезис Тьюринга-Черча. Основные черты теоретических моделей вычислений, встречающихся в реальных системах программирования (прямая и косвенная адресация, рекурсия и др.). Примеры алгоритмически неразрешимых задач и невычислимых функций: проблема самоприменимости алгоритмов (на примере машин Тьюринга), проблема остановки. [1, гл.1],[13, гл.4], [14, гл.3-8], [20], [21], [22].

2.  Теоремы о полиномиальной зависимости сложности алгоритмов в различных моделях вычислений. Понятие частичной корректности программ. Методика Флойда для доказательства частичной корректности программ. Приемы и примеры доказательства полной корректности алгоритмов. [13, гл.4, 16]

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

1.  Понятие частичной корректности программ. Методика Флойда доказательства частичной корректности программ. Приемы и примеры доказательства полной корректности алгоритмов. [13, гл.4, 16]

2.  Примеры алгоритмически неразрешимых задач и невычислимых функций: проблема самоприменимости алгоритмов (на примере машин Тьюринга), проблема остановки, проблема “усердного бобра”.

3.  Основные элементы теории сложности задач и алгоритмов, определение классов P и NP и NP-полных задач. Теорема Кука.

Амортизационный анализ и разделенные множества

1.  Основные классы функций, используемые, для оценки сложности алгоритмов. Методы амортизационного анализа.

2.  Разделенные множества. Методы реализации разобщенных множеств. Оценки трудоемкости операций при различных способах реализации. Примеры применения. [7, 15]

Приоритетные очереди

1.  Определение приоритетной очереди.

2.  Методы реализации приоритетных очередей в адресуемой памяти компьютера с помощью кучеобразных структур (D-кучи, левосторонние кучи, биномиальные кучи и их модификации).

3.  Оценки трудоемкости выполнения основных операций. Примеры применения приоритетных очередей [1, 7, 15]

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

1.  Реализация приоритетных очередей с помощью самоорганизующейся кучи, оценки трудоемкости основных операций.

2.  Реализация приоритетных очередей с помощью фибоначчиевой кучи, оценки трудоемкости основных операций. Применение фибоначчиевых куч при решении задач дискретной математики, теоретический и практический аспекты. [3, 15]

Словари и поисковые деревья

1.  Двоичные поисковые деревья, общие сведения об устройстве и трудоемкости основных операций.

2.  Случайные поисковые деревья.

3.  Красно-черные деревья, АВЛ-балансировка, комбинаторные свойства красно-черных и АВЛ-деревьев.

4.  Б-деревья.[1, 15]

Формальные языки и регулярные множества

1.  Основные понятия и обозначения. Операции над формальными языками. Способы задания формальных языков. Классификация Хомского.

2.  Регулярные выражения, системы линейных уравнений с регулярными коэффициентами.

3.  Синтез, детерминизация, анализ конечных автоматов.

4.  Применение конечных автоматов в программировании. Задачи поиска образцов в текстах.[1, 15]

Основы логического программирования

1.  Обзор теоретических основ логического программирования. Элементы исчисления предикатов. Префиксная, сколемовская и клаузальная формы предложений. Метод резолюций и стратегии его применения.

2.  Элементы языка ПРОЛОГ.

Нетрадиционные системы счисления

1.  Исторические сведения.

2.  Позиционная система счисления. Сокращенная система счисления. Алгоритмы перевода с разных оснований, в сокращенную систему счисления и обратно.

3.  Алгоритм Евклида Верхняя оценка числа итераций алгоритма Евклида. Расширенный алгоритм Евклида.

4.  Рациональная арифметика. Аналоги китайской теоремы об остатках для рациональной арифметики.

5.  Избыточные системы счисления. Распараллеливание операции сложения.

6.  Алгоритмы восстановления целого числа по остаткам. Верхние оценки трудоемкости. Алгоритмы восстановления рациональных чисел по остаткам.

Переборные алгоритмы

1.  Генерирование комбинаторных объектов, рационализация перебора.

Задачи, имеющие эффективные алгоритмы решения.

1.  Основные сведения о матроидах и градиентных алгоритмах для оптимизационной задачи общего типа.

2.  Теорема Радо-Эдмондса. Задача о взвешенном паросочетании.

Методы обхода графов.

1.  Примеры решения прикладных задач на графах методом обхода графа в глубину, ширину и их комбинацией.

Динамическое программирование.
Потоковые алгоритмы.

1.  Примеры эффективного приближенного решения дискретных задач при отсутствии точных полиномиальных алгоритмов.

2.  Примеры задач, не имеющих эффективных приближенных алгоритмов. Примеры эвристических алгоритмов.

План лабораторного практикума

Примеры тем для лабораторных работ

–  Нахождение кратчайших путей в графе с неотрицательными весами ребер.

–  Нахождение кратчайших путей в графе методом Форда, Беллмана.

–  Построение остовного дерева в графе.

–  Пирамидальная сортировка

Требования к описанию лабораторных работ

Описание лабораторных работ должно содержать:

–  Математическую постановку задачи.

–  Ссылки на теоретический материал, необходимый для решения поставленной задачи.

–  Ссылки на необходимый инструментарий.

–  Требования к предоставляемому отчету.

–  Требования к тестированию созданного во время выполнения работы программному обеспечению.

–  Рекомендации по проведению экспериментов и исследований.

–  Требования к описанию выполненных экспериментальных и исследовательских работ.

–  При работе со сложными исходными объектами необходимо указывать источники исходных данных или способы их генерирования

Замечание. Работу могут выполнять несколько человек, разделяя между собой работу по программированию различных вариантов алгоритма. Структуры хранения графа во всех вариантах алгоритма должны быть согласованы.

Требования к оформлению отчета

В отчете должно быть указано

программное обеспечение, разработанное в процессе выполнения лабораторной работы, использованные библиотеки, проведенные эксперименты, использованное при проведении экспериментов оборудование, выводы – рекомендации, которые можно сделать по результатам экспериментов. По каждому проведенному эксперименту должно быть указано цель эксперимента (какие зависимости предполагалось исследовать?), способ генерации исходных данных, алгоритм, который исследовался в эксперименте, способ представления исходных данных, структуры данных, использовавшиеся при реализации алгоритма, суть эксперимента – параметры исходных данных, расход памяти, времени, исследуемые зависимости, оборудование, использовавшееся при проведении экспериментов, результаты эксперимента в наглядной форме (таблиц, графиков и т. д.), выводы – рекомендации.

Литература

1.  А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

2.  Н. Вирт. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

3.  Dr. Dobb's Journal, Essential Books on Algorithms and Data Structures, CD-ROM (8 книг в электронном виде).

4.  Э. Дейкстра. Дисциплина программирования, – М.: Мир, 1978.

5.  Д. Кнут. Искусство программирования. – Т. 3. Сортировка и поиск. – М.: Мир, 1976.

6.  В. Липский. Комбинаторика для программистов. – М.: Мир, 1988.

7.  Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные Алгоритмы. – М.: Мир, 1980.

8.  R. E. Tarjan, Data Structures and Network Algorithms, Bell Laboratories, Murray Hill, New Jersey, Society for Industrial and Applied Mathematics, 1983.

9.  П. Холл. Вычислительные структуры. Введение в нечисленное программирование. – М.: Мир, 1978.

10.  R. Tamassia, Brian Cantril, Data Strutures, Departament of computer science, Brown University, 115, Watterman Street Providence, RI {rt, bmc}@cs. brown. edu, January 27, 1996.

11.  , , . Лекции по теории графов. – М.: Наука, Гл. ред. физ.-мат. лит., 1990.