УТВЕРЖДАЮ
Проректор-директор ИК
________________
“___”___________________ 2011 г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
АЛГОРИТМЫ И АНАЛИЗ СЛОЖНОСТИ
НАПРАВЛЕНИЕ ООП 130100 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»
ПРОФИЛИ ПОДГОТОВКИ Вычислительные машины, комплексы, системы и сети, Системы автоматизированного проектирования, Технологии разработки программного обеспечения, Программное обеспечение средств вычислительной техники и автоматизированных систем.
КВАЛИФИКАЦИЯ БАКАЛАВР
БАЗОВЫЙ УЧЕБНЫЙ План ПРИЕМА
КУРС 2 СЕМЕСТР 3/4
КОЛИЧЕСТВО КРЕДИТОВ 6/2
ПРЕРЕКВИЗИТЫ –
КОРЕКВИЗИТЫ МАТЕМАТИКА, ФИЗИКА, ЛОГИКА
ВИДЫ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ И ВРЕМЕННОЙ РЕСУРС:
ЛЕКЦИИ 28
ЛАБОРАТОРНЫЕ РАБОТЫ 28
АУДИТОРНЫЕ ЗАНЯТИЯ
САМОСТОЯТЕЛЬНАЯ РАБОТА 28
ИТОГО 84
ФОРМА ОБУЧЕНИЯ ОЧНАЯ
ВИД ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ 3 СЕМЕСТР - ЗАЧЕТ
ОБЕСПЕЧИВАЮЩЕЕ ПОДРАЗДЕЛЕНИЕ: КАФЕДРА ИНФОРМАТИКИ И ПРОЕКТИРОВАНИЯ СИСТЕМ
ЗАВ. КАФЕДРОЙ ИПС М. А. СОНЬКИН
РУКОВОДИТЕЛЬ ООП РЕЙЗЛИН В. И.
ПРЕПОДАВАТЕЛИ: Ю. Н. ШАЛАЕВ
2011 г.
1. Цели освоения дисциплины
Цель дисциплины “Алгоритмы и анализ сложности” - ознакомление студентов с фундаментальными алгоритмами обработки данных, а также с современными методами исследования алгоритмов и оценки их алгоритмической сложности.
Целями освоения дисциплины в области обучения, воспитания и развития являются требования ФГОС ООП, способствующие формированию у студента следующих
общекультурных компетенций (ОК – 2,3,9):
· быть готовым к категориальному видению мира, уметь дифференцировать различные формы его освоения (ОК-2);
· логически верно, аргументированно и ясно строить устную и письменную речь (ОК-3);
· стремиться к саморазвитию, повышению своей квалификации и мастерства (ОК-9);
профессиональных компетенций (ПК – 1,2,4):
· самостоятельно приобретать новые знания, используя современные образовательные и информационные технологии (ПК-1);
· использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ПК-2);
· владеть основными методами, способами и средствами получения, хранения, переработки информации, работать с компьютером, как средством управления информацией (ПК-4);
2. Место дисциплины в структуре ООП
Дисциплина «Алгоритмы и анализ сложности» относится к математическому и естесственно-научному циклу дисциплин. Для изучения дисциплины необходимо знание обязательного минимума содержания среднего (полного) образования по математике, математической логике и информатике, утвержденного приказом Минобразования № 56 от 30.06.99. Прериквизитов нет. Кореквизиты – математика, физика, математическая логика м теория алгоритмов. Дисциплина «Алгоритмы и анализ сложности» является пререкизитом для всех дисциплин профессионального цикла.
3. Результаты освоения дисциплины
После изучения дисциплины в соответствии с ФГОС ООП студент должен:
знать:
основные сведения о методах и способах построения алгоритмов для различных технических задач.
уметь:
производить анализ сложности алгоритма и находить пути упрощения полученных алгоритмов.
владеть:
методами построения алгоритмов для решения различных технических задач.
Вариативная часть результатов освоения дисциплины:
Производить анализ сложности алгоритмов и находить пути их упрощения.
4. Структура и содержание дисциплины
Таблица 1. Структура и содержание дисциплины. Семестр 1
Разделы | Лекц. (час.) | Лб. раб. (час.) | Сам. раб. (час.) | Итого (час.) | |
1. | Введение. Основы анализа алгоритмов | 8 | 12 | 24 | 28 |
2. | Стратегии алгоритмов | 8 | 16 | 28 | 36 |
3. | Основные алгоритмы обработки информации | 13 | 24 | 32 | 44 |
4. | Распределенные алгоритмы | 8 | 10 | 26 | 32 |
5. | Основы теории вычислимости | 8 | 10 | 16 | 32 |
Итог | 45 | 72 | 126 | 72 |
Содержание разделов дисциплины в семестре
1. Введение.
2. Основы анализа алгоритмов
Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов.
2. Стратегии алгоритмов
Полный перебор; метод “разделяй и властвуй”; “жадные” алгоритмы; бэктрекинг (перебор с возвратами); метод ветвей и границ; эвристический поиск; поиск по образцу, алгоритмы обработки строк; алгоритмы аппроксимации числовых функций.
3. Основные алгоритмы обработки информации
Основные алгоритмы над числами; алгоритмы последовательного и бинарного поиска; алгоритмы сортировки; хеш-функции и методы исключения коллизий; деревья бинарного поиска; представление графов (списки и матрицы смежности); поиск в глубину и поиск в ширину; алгоритмы поиска кратчайших путей (алгоритмы Дейкстры и Флойда); транзитивное замыкание (алгоритм Флойда); алгоритмы построения минимального покрывающего дерева (алгоритмы Прима и Крускала); топологическая сортировка.
4. Распределенные алгоритмы
Модель параллельного выполнения программы с общей памятью и модель передачи сообщений: организация параллельных вычислений на принципе консенсуса и на основе выбора; методы определения завершения параллельных вычислений.
5. Основы теории вычислимости
Конечные автоматы; контекстно-свободные грамматики; разрешимые и неразрешимые проблемы; невычислимые функции; проблема останова; применение невычислимости.
5. Образовательные технологии
При освоении разделов дисциплины используется сочетание видов образовательной деятельности (ОД) – лекция, самостоятельная работа – с различными методами ее активизации (табл. 3).
Таблица 3. Сочетание видов ОД с различными методами ее активизации
Метод акт. ОД \ Вид ОД | Лекц. | Прак. зан. | Сам. раб | К. пр. |
IT-методы | + | + | + | + |
Работа в команде | + | + | ||
Case-study | + | |||
Игра | + | |||
Проблемное обучение | + | + | + | |
Контекстное обучение | + | + | ||
Обучение на основе опыта | + | + | ||
Индивидуальное обучение | + | |||
Междисциплинарное обучение | + | + | + | |
Опережающая самостоятельная работа | + |
От общего количества аудиторных занятий доля лекционных учебных занятий составляет 50%.
6. Организация и учебно-методическое обеспечение самостоятельной работы студентов
Особенности организации самостоятельной работы студентов при освоении различных разделов дисциплины состоят в привязке этих разделов к будущей профессиональной деятельности, что повышает мотивацию студентов для выполнения самостоятельных работ. Включение самостоятельной работы в рейтинг-план также способствует повышению мотивации студентов для ее выполнения.
7. Средства (ФОС) текущей и итоговой оценки качества освоения дисциплины
Фонд оценочных средств дисциплины (ФОС) состоит из средств входного контроля знаний по школьной информатике, текущего контроля выполнения заданий и средств для промежуточной аттестации (зачета в 4-ом семестре). Эти средства содержат перечень вопросов, ответы на которые дают возможность студенту продемонстрировать, а преподавателю оценить степень усвоения теоретических и фактических знаний на уровне знакомства; заданий, позволяющих оценить приобретенные студентами практические умения на репродуктивном уровне; задач для оценки приобретенных студентами когнитивных умений на продуктивном уровне; проблем, позволяющих оценить профессиональные и универсальные (общекультурные) компетенции студентов.
Входной и выходной контроль знаний осуществляется в форме контрольных работ.
8. Рейтинг качества освоения дисциплины
В соответствии с рейтинговой системой текущий контроль производится ежемесячно в течение семестра путем балльной оценки качества усвоения теоретического материала (ответы на вопросы) и результатов практической деятельности (решение задач, выполнение заданий, решение проблем).
Промежуточная аттестация (зачет) производится в конце семестра также путем балльной оценки. Итоговый рейтинг определяется суммированием баллов текущей оценки в течение семестра (80 баллов максимум) и баллов промежуточной аттестации в конце семестра по результатам экзамена или зачета (20 баллов максимум). Максимальный итоговый рейтинг соответствует 100 баллам (текущая оценка в семестре + промежуточная аттестация в конце семестра = 80 + 20).
9.Учебно - методическое и информационное обеспечение модуля (дисциплины)
Основная литература:
1. Абрамов о сложности алгоритмов.- М.: МЦНЬО, 2009.- 256 с.
2. Алгоритмы и структуры данных. Новая версия для Оберона + CD / Никлаус Вирт; пер. с англ. под ред. . — Москва: ДМК Пресс, 2010. — 272 с.
испр. и доп.. — М.: Вильямс, 2011, Т. 1: Основные алгоритмы. — 2011. — 720 с.
4. Искусство программирования: учебное пособиепер. с англ. / . — 3-е изд., испр. и доп.. — М.: Вильямс, 2011, Т. 3: Сортировка и программирование. — 2-е изд.. — 2011. — 832 с.
5. Алгоритмы: построение и анализ. – М.:
МЦНМО, 2007. – 960 с.
Дополнительная литература:
1. , , Ульман данных и алгоритмы.- М.: Вильямс, 2007.- 382 с.
2. Мозговой, программирования: алгоритмы, языки, автоматы, компиляторы : практический подход / . — СПб.: Наука и техника, 2006. — 320 с.
3. Гашков, Сергей БорисовичАрифметика. Алгоритмы. Сложность вычислений: учебное пособие / , ; Московский государственный университет им. (МГУ). — 3-е изд., испр.. — Москва: Дрофа, 2005. — 320 с.
4. Древс, Юрий ГеоргиевичОрганизация ЭВМ и вычислительных систем : учебник для вузов / . — Москва: Высшая школа, 2006. — 501 с.
Программа составлена на основе Стандарта ООП ТПУ в соответствии с требованиями ФГОС по направлению и профилю подготовки 230100 «Информатика и вычислительная техника».
Программа одобрена на заседании кафедры ИПС
(протокол № __8__ от «_11__» __11_____ 2011 г.).
Автор:
Рецензент: .
