МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

Алгоритмы и анализ сложности

рабочая программа дисциплины
Закреплена за кафедройКафедра информатики
Направление подготовки02.03.02. Фундаментальная информатика и информационные технологии
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план02_03_02_ФИиИТ-4-2020
Часов по учебному плану 108
в том числе:
аудиторные занятия 42
самостоятельная работа 66
Виды контроля по семестрам
зачеты: 5

Распределение часов по семестрам

Курс (семестр) 3 (5) Итого
Недель 19
Вид занятий УПРПДУПРПД
Лекции 18 18 18 18
Лабораторные 24 24 24 24
Сам. работа 66 66 66 66
Итого 108 108 108 108

Программу составил(и):
к.ф.-м.н., доцент, Козлов Д.Ю.

Рецензент(ы):
к.ф.-м.н., доцент, Пономарев И.В.

Рабочая программа дисциплины
Алгоритмы и анализ сложности

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 02.03.02 Фундаментальная информатика и информационные технологии (уровень бакалавриата) (приказ Минобрнауки России от 12.03.2015г. №224)

составлена на основании учебного плана:
02.03.02 Фундаментальная информатика и информационные технологии
утвержденного учёным советом вуза от 30.06.2020 протокол № 3.

Рабочая программа одобрена на заседании кафедры
Кафедра информатики

Протокол от 31.08.2020 г. № 1
Срок действия программы: 2020-2021 уч. г.

Заведующий кафедрой
к.ф.-м.н., доцент Козлов Д.Ю.


Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2020-2021 учебном году на заседании кафедры

Кафедра информатики

Протокол от 31.08.2020 г. № 1
Заведующий кафедрой к.ф.-м.н., доцент Козлов Д.Ю.


1. Цели освоения дисциплины

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

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.В

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

ОПК-1 способностью использовать базовые знания естественных наук, математики и информатики, основные факты, концепции, принципы теорий, связанных с фундаментальной информатикой и информационными технологиями
ПК-7 способностью разрабатывать и реализовывать процессы жизненного цикла информационных систем, программного обеспечения, сервисов систем информационных технологий, а также методы и механизмы оценки и анализа функционирования средств и систем информационных технологий
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.о различных парадигмах программирования и современном уровне развития языков и технологий программирования;
о сложности программных систем и методах ее преодоления;
методы анализа сложности алгоритмов;
синтаксис и базовые конструкции языка C,С++;
назначение, устройство и свойства основных структур данных: список, очередь, стэк, дерево, граф;
эффективные алгоритмы для работы с различными структурами данных;
методы вычисления сложности алгоритмов;
алгоритмы обработки динамических структур данных;
основные парадигмы программирования;
особенности языков программирования Си и С++.
3.2.Уметь:
3.2.1.использовать эффективные алгоритмы поиска и обработки сложных структур данных;
использовать для разработки и отладки программ современные интегрированные среды разработки;
реализовывать алгоритмы обработки динамических структур данных;
вычислять сложность алгоритмов;
использовать для разработки и отладки программ современные интегрированные среды разработки языка программирования Си и С++;
использовать эффективные алгоритмы поиска и обработки сложных структур данных;
использовать для разработки и отладки программ современные интегрированные среды разработки.
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.навыками написания и отладки программ на высокоуровневом языке программирования в интегрированной среде разработки;
навыками использования алгоритмов обработки динамических структур данных при решении конкретных задач на практике;
техникой подчсета сложности алгоритмов любых видов;
навыками написания и отладки программ на языках программирования Си и С++ в интегрированной среде разработки;
навыками написания и отладки программ на высокоуровневом языке программирования в интегрированной среде разработки.

4. Структура и содержание дисциплины

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Динамические структуры данных
1.1. Сбалансированные деревья. AVL-деревья. Основные операции. Реализация. Лекции 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.2. Программная реализация AVL-дерева. Лабораторные 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.3. Программная реализация AVL-дерева. Сам. работа 5 10 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.4. Красно-черные деревья. Вращение. Добавление и удаление вершин. Дерево промежутков. Лекции 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.5. Программная реализация красно-черных деревьев. Лабораторные 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.6. Программная реализация красно-черных деревьев. Сам. работа 5 10 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.7. SPLAY-деревья.Основные операции Лекции 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.8. Программная реализация SPLAY-деревьев. Лабораторные 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.9. Программная реализация SPLAY-деревьев. Сам. работа 5 8 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.10. Б-деревья. Вращение. Добавление и удаление вершин. Применение. Лекции 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.11. Программная реализация Б-деревьев. Лабораторные 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.12. Программная реализация Б-деревьев. Сам. работа 5 10 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.13. Биномиальные деревья и кучи. Основные операции. Лекции 5 1 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.14. Программная реализация операций над биномиальными деревьями. Лабораторные 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
1.15. Программная реализация операций над биномиальными деревьями. Сам. работа 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
Раздел 2. Сложные структуры данных
2.1. Графы. Описание. Основные понятия и виды графов. Задачи на графах. Лекции 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.2. Задачи на графах. Лабораторные 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.3. Задачи на графах. Сам. работа 5 10 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.4. Системы непересекающихся множеств. Основные свойства и операции. Лекции 5 1 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.5. Реализация с использованием списков. Лабораторные 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.6. Реализация с использованием списков. Сам. работа 5 4 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.7. Алгоритмы на графах. Поиск в ширину. Поиск в глубину. Минимальные покрывающие деревья. Лекции 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.8. Программная реализация алгоритмов на графах. Лабораторные 5 2 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2
2.9. Программная реализация алгоритмов на графах. Сам. работа 5 10 ОПК-1, ПК-7 Л1.1, Л2.1, Л1.3, Л1.4, Л1.2

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины
в приложении
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.)
в приложении
5.3. Фонд оценочных средств для проведения промежуточной аттестации
в приложении

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Хиценко В.П. Структуры данных и алгоритмы: учебное пособие Издательство НГТУ, 2016 www.studentlibrary.ru
Л1.2 Мейер Б. Инструменты, алгоритмы и структуры данных: Учебная литература для ВУЗов Национальный Открытый Университет «ИНТУИТ», 2016 biblioclub.ru
Л1.3 Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона: Учебные пособия Издательство "ДМК Пресс", 2010 e.lanbook.com
Л1.4 Алексеев В. Е., Таланов А. В. Графы и алгоритмы: Учебная литература для ВУЗов Национальный Открытый Университет «ИНТУИТ», 2016 biblioclub.ru
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Ландовский В.В. Структуры данных: учебное пособие Издательство НГТУ, 2016 www.studentlibrary.ru
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Алгоритмы. Методы. Исходнинки algolist.manual.ru
Э2 Курс в Moodle "Алгоритмы и анализ сложности" portal.edu.asu.ru
6.3. Перечень программного обеспечения
Среда разработки Мicrosoft visual studio С++ (версия не ниже 2008)
Microsoft Windows
Microsoft Office
7-Zip
AcrobatReader
6.4. Перечень информационных справочных систем
1. Образовательный портал АлтГУ http://portal.edu.asu.ru/
2. Электронный каталог НБ АлтГУ «Книги»: http://www.lib.asu.ru/app/elecat/elecat=index1?base=book
3. Издательство «Лань» [Электронный ресурс]: электронно-библиотечная система. – URL: http://e.lanbook.com/
4. Издательство «Юрайт» [Электронный ресурс]: электронно-библиотечная система. – URL: http://biblio-online.ru
5. ЭБС «Университетская библиотека online»: https://biblioclub.ru/
6. ЭБС АлтГУ: http://elibrary.asu.ru/
7. Электронная база данных ZBMATH: https://zbmath.org/

7. Материально-техническое обеспечение дисциплины

Аудитория Назначение Оборудование
Помещение для самостоятельной работы помещение для самостоятельной работы обучающихся Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)
106Л помещение для хранения и профилактического обслуживания учебного оборудования Стеллажи – 3 шт. осциллограф, паяльная станция, источник тока, переносные ноутбуки
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)
519М электронный читальный зал с доступом к ресурсам «ПРЕЗИДЕНТСКОЙ БИБЛИОТЕКИ имени Б.Н. Ельцина» - помещение для самостоятельной работы Учебная мебель на 46 посадочных мест; 1 Флипчарт; компьютеры; ноутбуки с подключением к информационно-телекоммуникационной сети "Интернет" и доступом в электронную информационно-образовательную среду; стационарный проектор: марка Panasonic, модель PT-ST10E; стационарный экран: марка Projecta, модель 10200123; система видеоконференцсвязи Cisco Telepresence C20; конгресс система Bosch DCN Next Generation; 8 ЖК-панелей
107Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 18 посадочных мест; компьютеры: марка HP, модель ProOne 400 - 18 единиц; проектор: марка SMART, модель UF70 - 1 единица; интерактивная доска: марка SMART Board модель SMB680 - 1 единица
108М лаборатория информационных технологий - компьютерный класс – учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 13 посадочных мест; рабочее место преподавателя; доска магнитно-маркерная; интерактивная доска: SMART Board – 1 ед.; персональные компьютеры: NAIO Corp Z520 – 13 ед.
109М лаборатория информационных технологий - компьютерный класс – учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 13 посадочных мест; рабочее место преподавателя; доска магнитно-маркерная 1 шт.; компьютеры: марка NAIO Corp Z520 - 13 ед.
202Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка HP - 14 единиц; мониторы: марка ASUS модель VS197DE - 14 единиц
205Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 9 посадочных мест; компьютеры: марка КламаС Офис, мониторы: марка ACER модель V223HQL - 8 единиц; доска интерактивная Triumph MULTI TOUCH 78 + проектор NEC UM280X в комплекте
204Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260 - 14 единиц; Интерактивная доска Smart board 680 IV со встроенным проектором v25
203Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка ASUS модель i5-6500 - 14 единиц
207Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260, мониторы: марка Philips модель 227E3LHSU - 14 единиц

8. Методические указания для обучающихся по освоению дисциплины

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