|
2.Линейное программировании и представление полиномов в проектировании алгоритмов. Данный раздел посвящён ознакомлению задач максимизации и минимизации некой цели в условиях ограниченности ресурсов и наличия конкурирующих ограничений.
1. Стандартная и каноническая формы задачи линейного программирования
|
2
|
2. Симплекс алгоритм и двойственность
|
2
|
3. Представление полиномов.
|
2
|
4. Дискретное преобразование Фурье (ДПФ и БПФ).
|
2
|
5. Элементарные понятия теория чисел. Проверка простоты.
|
2
|
6. Целочисленное разложение.
|
2
|
7. Простейший алгоритм поиска подстрок
|
2
|
8. Поиск подстрок с помощью с конечных подстрок.
|
2
|
9. Свойства отрезков.
|
2
|
10. Поиск пары ближайших точек.
|
2
|
3.Алгоритмы с полиномиальным временем работы. Данный раздел посвящён ознакомлению и изучению входных данных с полиномиальным временем работы. Поиск в решении задач самых коротких и самых простых путей.
1.Полиномиальное время
|
2
|
2.NP-полнота и приводимость.
|
2
|
3.Приближённые алгоритмы. Задачи о вершинном покрытии.
|
2
|
4.Приближённые алгоритмы. Задачи о покрытии множества.
|
2
|
5.Суммы и их свойства.
|
2
|
6.Оценки сумм.
|
2
|
7.Множества и отношения в проекте.
|
2
|
8.Функции, графы, деревья в проекте.
|
2
|
9.Дискретные случайные величины.
|
2
|
10.Биномиальные распределения.
|
2
|
Самостоятельная работа:
№
|
Тематики блока
|
Часы
|
1.
|
Статические и динамические меры сложности. Временная и ёмкостная сложности.
|
6
|
2.
|
Оценки в худшем и среднем случаях.
|
6
|
3.
|
Модели вычислений. РАМ- и РАСП-машины.
|
6
|
4.
|
Равномерный и логарифмический весовые критерии при оценке временной и емкост-нойсложностей алгоритмов.
|
6
|
5.
|
Неветвящиеся программы, битовые вычисления, деревья решений.
|
6
|
6.
|
Представление последовательностей, множеств, деревьев, графов и т.п.
|
6
|
7.
|
Стеки, очереди, деки. Способы представления. Операции над ними.
|
6
|
8.
|
Обходы деревьев и графов в глубину и ширину.
|
6
|
9.
|
Копирование деревьев. Длина путей.
|
6
|
10.
|
Древовидные структуры для задачи ОБЪЕДИНИТЬ - НАЙТИ.
|
6
|
11.
|
Процедуры НАЙТИ и ОБЪЕДИНИТЬ и их модификации путем перестройки данных: сжатие пути и балансировка. Оценка сложности соответствующих алгоритмов.
|
6
|
12.
|
Внутренняя сортировка (массивов).
|
6
|
13.
|
1Нижние оценки сложности алгоритмов сортировки, основанных на сравнениях элементов.
|
6
|
14.
|
Элементарные методы сортировки: обмен, вставка, выбор.
|
4
|
15.
|
Улучшенные методы сортировки.
|
4
|
16.
|
Быстрая сортировка - упорядочение за среднее время О(n log n).
|
2
|
17.
|
Сортировка деревом - упорядочение за время О(n log n) в худшем случае.
|
2
|
Нагрузка
Деятельность
|
Часы
|
Лекция
|
30
|
Лаборатория
|
60
|
Практика
|
-
|
Самостоятельная работа
|
90
|
Общее
|
180
|
Стратегия обучения
Развитие курса происходит следующим образом: во время лекций, студент получает необходимые теоретические знания по курсу. один раз в течении семестра проводится промежуточный контроль. Во время лабораторных занятий, преподаватель демонстрирует практические применение теоретических знаний, полученных во время лекций. В конце каждого раздела для лабораторных работ, студент получает индивидуальное задание, для выполнения самостоятельных работ в целях дальнейшего укрепления тематики. В течении семестра, студент должен выполнить 5 лабораторных заданий.
Лабораторные задания.
1. Задачи с динамическим программированием
2. Жадные алгоритмы. Задача о выборе процессов.
3. Многопоточное программирование.
4. Алгоритм поиска подстрок.
5. Задачи класса NP.
Оценивание
Теоретическая часть курса состоит из двух промежуточных конролей.
Практическая часть состоит из 6 индивидуальных лабораторных заданий, основанных на каждых разделах:
Контрольная работа: 15%
Практические задания: 20% (4% за каждый)
Самостоятельная работа: 10% (5% за каждый)
Итоговый контроль: 50%
Основные направления оценивания: уровень уникальности текста, качество работы, актуальность и практический подход. Оценивание проводится по следующим критериям:
1) Промежуточная контроль. Контрольная работа состоит из трех заданий: два теоретических и одна практическая.
Задания оцениваются следующим образом:
А. 1-задание (теоретическое). За правильное выполнение 4%.
Б. 2-задание (теоретическое). За правильное выполнение 4%.
C. 3-задание (практическая задача). За правильное выполнение 7%.
Общий балл за промежуточную контроль: 15%.
2) Лабораторное задание. Лабораторное задание состоит из трех заданий.
Задания оцениваются следующим образом:
А. 1-задание (реализация шаблонного примера). За правильное выполнение 1%.
Б. 2-задание (выполнение индивидуального задания). За правильное выполнение 2%.
C. 3-задание (подготовка отчета работы и ее защита). За правильное выполнение 2%.
Общий балл за лабораторное задание: 5%.
2) Самостоятельная работа. Студент должен выбрать любую интересующую его тему, прошедшую во время курса, и представить отчет в форме презентации и рукописи.
Общий балл за самостоятельную работу: 10%.
Сроки оценки:
Для каждой лабораторной и самостоятельной работы устанавливается определенный срок (deadline). В случае несвоевременной сдачи задания оценка снижается.
Литература
Основная:
1. Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы. Построение и анализ», 2013 г.
Дополнительная:
Г.Шилтд Самоучитель С++. 5-е издание. “БХВ Петербург” 2010 г.
Колдаев Основы_алгоритмизации_и программирования. 2013 г.
Род Хаггарти «Дискретная математика для программистов» 2012 г.
Томас Х.Кормен «Алгоритмы. Вводный курс» 2014 г.
Г.Уоррен «Алгоритмические трюки для программистов», 2014 г.
Do'stlaringiz bilan baham: |
