Общие комбинаторные алгоритмы Общие комбинаторные алгоритмы




НазваниеОбщие комбинаторные алгоритмы Общие комбинаторные алгоритмы
Дата конвертации23.07.2013
Размер444 b.
ТипИсследование



Общие комбинаторные алгоритмы

  • Общие комбинаторные алгоритмы

  • Алгоритмы сортировки и поиска

  • Алгоритмы на строках

  • Лабораторные работы:

  • Исследование алгоритмов сортировки

  • Исследование алгоритмов поиска



Лекции – 17 ч.

  • Лекции – 17 ч.

  • Лабораторные работы – 17 ч.

    • Лаб № 1 (Сортировка) – 20-33 б.
    • Лаб № 2 (Поиск) – 16–25 б.
  • Домашнее задание – 6-10 б.

  • Рубежный контроль – (6-10 б. в каждом модуле)

  • Личностные качества (3-5 б. в каждом модуле)

  • Зачет – при успешном выполнении всех видов контроля



а) основная литература:

  • а) основная литература:

    • Кукушкин Б.А. Описания комбинаторных алгоритмов (эл. вид).
    • Кнут Д. Искусство программирования, т.3. Сортировка и поиск. — М.: Вильямс, 2011. — 824 с.
    • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: Вильямс, 2011. — 1296 с.
    • Макконнелл Дж. Основы современных алгоритмов. — М. : Техносфера, 2004. — 368с. 
  • б) дополнительная литература:

    • Вирт Н. Алгоритмы и структуры данных. — М., ДМК_Пресс, 2011. — 272 с.
    • Ахо А., Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы. — М., : Вильямс, 2010. — 384 с.
    • Левитин А.В. Алгоритмы: введение в разработку и анализ. : Пер. с англ. — М. : Издательский дом "Вильямс", 2006. — 576 с.


Седжвик Р. Фундаментальные алгоритмы на C++. ч. 1-5. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», 2003.- 688 с.

    • Седжвик Р. Фундаментальные алгоритмы на C++. ч. 1-5. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», 2003.- 688 с.
    • Окулов С. М. Программирование в алгоритмах. — М.: БИНОМ, Лаборатория знаний, 2002. — 341 с.
    • Гудман С., С. Хидетниеми. Введение в разработку и анализ алгоритмов. М., Мир, 1981.
    • Рейнгольд Э., Ю.Нивергельт, М.Део. Комбинаторные алгоритмы – теория и практика. М, Мир, 1980.
    • Липский В. Комбинаторика для программистов. М., Мир. 1988.
  • Электронные версии большинства учебников – на сайте



www.intuit.ru/department/algorithms/algocombi/ - Комбинаторные алгоритмы для программистов – учебный курс.

    • www.intuit.ru/department/algorithms/algocombi/ - Комбинаторные алгоритмы для программистов – учебный курс.
    • pta-ipm.narod.ru — презентации лекций, задания, учебники, ссылки.
    • rain.ifmo.ru/cat/view.php/vis — визуализаторы алгоритмов
    • neerc.ifmo.ru/mediawiki — определения, материалы
    • alglib.sources.ru - описание аппроксимации МНК
    • ips.ifmo.ru/courses/coursesinfo/index.html - курс С. Е. Столяра «Введение в алгоритмику»


Цель работы:

  • Цель работы:

  • Реализация алгоритмов сортировки и исследование их характеристик:

    • быстродействие
    • требуемый объем памяти
    • естественность поведения
    • устойчивость
    • область применимости


Реализовать алгоритмы сортировки, заданные в варианте задания. Отладить их на последовательности, приведенной в методичке (этап 1: 7-11 баллов).

  • Реализовать алгоритмы сортировки, заданные в варианте задания. Отладить их на последовательности, приведенной в методичке (этап 1: 7-11 баллов).

  • Изучить средства измерения интервалов времени.

  • Измерить время сортировки для всех файлов из каталога F_SORT.

    • Файлы (около 80) имеют разную длину и степень упорядоченности. Имена файлов сформированы так:
    • 4-значное число - длина файла в байтах
    • символ подчеркивания
    • 3-значное число, задающее процент инверсий.
    • Расширение файла (1,2,3) определяет случайный вариант файла с одними и теми же параметрами
    • Например, файл 0256_075.2 соответствует последовательности из 256 чисел с количеством инверсий I=75%=24384 от максимального, вариант 2.


Построить аппроксимирующие графики зависимостей времени сортировки от длины файла (этап 2: 10-17 баллов).

  • Построить аппроксимирующие графики зависимостей времени сортировки от длины файла (этап 2: 10-17 баллов).



Титульный лист (фамилия, группа, дисциплина, название задания, текст конкретного варианта, дата).

  • Титульный лист (фамилия, группа, дисциплина, название задания, текст конкретного варианта, дата).

  • Описание алгоритма (словесная форма, схема алгоритма).

    • // Методичку и учебники не копировать. Описать своими словами.
  • Текст программы.

  • Таблицы результатов замеров времени.

  • Графики зависимостей с коэффициентами аппроксимирующих функций.

    • // Графики должны наглядно представлять исследуемые зависимости и сравнение алгоритмов.
    • Аппроксимирующие коэффициенты выводятся для 2-3 графиков
  • Выводы по работе (словесное описание исследованных характеристик каждого алгоритма, сравнение алгоритмов по этим характеристикам, достоинства, недостатки и области применимости).



Похожие:

Общие комбинаторные алгоритмы Общие комбинаторные алгоритмы iconПриближенные алгоритмы Комбинаторные алгоритмы

Общие комбинаторные алгоритмы Общие комбинаторные алгоритмы iconОткрытые задачи (пока, оценочные)
Паскаль (основные типы данных и операторы, понятие сложности алгоритмов, процедуры и функции, рекурсия, арифметические и комбинаторные...
Общие комбинаторные алгоритмы Общие комбинаторные алгоритмы iconКомбинаторные задачи Комбинаторные задачи
Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами
Общие комбинаторные алгоритмы Общие комбинаторные алгоритмы iconКомбинаторные задачи Комбинаторные задачи
Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами
Общие комбинаторные алгоритмы Общие комбинаторные алгоритмы iconАлгоритмы обработки информации алгоритмы обработки информации
В области скоростных информационно-телекоммуникационных систем и массово используемых мобильных коммуникаций сложилось
Общие комбинаторные алгоритмы Общие комбинаторные алгоритмы iconКомбинаторные задачи 6 класс

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

Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница