1. Цели освоения дисциплины
| 1.1. | Цель освоения учебной дисциплины «Алгоритмы и структуры данных» - Формирование важнейших представлений о структурах данных и алгоритмах их обработки в информационных системах. Задачами освоения учебной дисциплины «Алгоритмы и структуры данных» являются: передача студентам теоретических знаний и освоение ими умений и навыков по алгоритмам обработки информации, включая вопросы поиска, сортировки, сжатия, решения прикладных задач оптимизации и других с учетом развития информационных технологий и систем. |
|---|
2. Место дисциплины в структуре ООП
| Цикл (раздел) ООП: Б1.О.05 |
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
| ПК-3 | Способен разрабатывать и применять математические методы, системное и прикладное программное обеспечение, автоматизированные систем вычислительных комплексов, сервисы, операционные системы и распределенные базы данных для решения задач производственно-технологический деятельности |
| В результате освоения дисциплины обучающийся должен | |
| 3.1. | Знать: |
|---|---|
| 3.1.1. | основные структуры данных, основные алгоритмы сортировки, алгоритмы решения задач на графах, основные алгоритмы поиска, алгоритмы обработки текстов. |
| 3.2. | Уметь: |
| 3.2.1. | составлять программы по блок-схемам, разрабатывать основные алгоритмы обработки, оценивать трудоемкость алгоритмов, решать стандартные задачи, решать задачи с помощью комбинации базовых алгоритмов, решать нестандартные задачи. |
| 3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
| 3.3.1. | навыками программной реализации алгоритмов, навыками самостоятельной разработки алгоритмов, навыками оценивания сложности алгоритмов, навыками разработки программ, навыками использования программных модулей, навыками объединения разнородных программных модулей. |
4. Структура и содержание дисциплины
| Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
|---|---|---|---|---|---|---|
| Раздел 1. Алгоритмы сортировки | ||||||
| 1.1. | Задача сортировки массивов. Простые методы сортировки. Оценки сложности алгоритма. | Лекции | 6 | 4 | ПК-3 | Л2.1, Л1.1 |
| 1.2. | Усовершенствованные алгоритмы сортировки. Сортировка Шелла. | Лекции | 6 | 2 | ПК-3 | Л2.2, Л1.1 |
| 1.3. | Быстрая сортировка методом разделения Хоара. | Лекции | 6 | 2 | ПК-3 | Л2.1, Л1.1 |
| 1.4. | Лабораторная работа № 1 «Изучение простых алгоритмов сортировки». Программная реализация метода пузырька, метода простого выбора, метода простых включений. | Лабораторные | 6 | 8 | ПК-3 | Л2.1, Л1.1 |
| 1.5. | Лабораторная работа № 2 «Изучение усовершенствованных алгоритмов сортировки». Программная реализация шейкерной сортировки, сортировки Шелла, бинарной сортировки и быстрой сортировки методом разделения. | Лабораторные | 6 | 10 | ПК-3 | Л2.1, Л1.1 |
| 1.6. | Изучение литературы по темам раздела 1 | Сам. работа | 6 | 20 | ПК-3 | Л2.1, Л1.1 |
| Раздел 2. Алгоритмы обработки текстов | ||||||
| 2.1. | Поиск вхождения слова в текст. Алгоритм Боуэра-Мура. | Лекции | 6 | 2 | ПК-3 | Л2.1, Л1.1 |
| 2.2. | Лабораторная работа № 3 «Изучение алгоритмов поиска вхождения слова в текст» Программная реализация алгоритмов Боуэра-Мура, Кнута-Мориса Пратта и наивного. | Лабораторные | 6 | 10 | ПК-3 | Л2.1, Л1.1 |
| 2.3. | Лабораторная работа № 4 «Изучение алгоритмов поиска длиннейшей общей подпоследовательности двух строк" Программная реализация алгоритмов динамического программирования. | Лабораторные | 6 | 8 | ПК-3 | Л2.1, Л1.1 |
| 2.4. | Изучение литературы по темам раздела 2 | Сам. работа | 6 | 15 | ПК-3 | Л2.1, Л1.1 |
| Раздел 3. Алгоритмы решения задач на графах | ||||||
| 3.1. | Задачи на графах. Алгоритм построения минимального остовного дерева. | Лекции | 6 | 2 | ПК-3 | Л2.2, Л1.1 |
| 3.2. | Алгоритм поиска кратчайшего пути. | Лекции | 6 | 2 | ПК-3 | Л2.2, Л1.1 |
| 3.3. | Изучение литературы по темам раздела 3 | Сам. работа | 6 | 15 | ПК-3 | Л2.2, Л1.1 |
| Раздел 4. Новые направления | ||||||
| 4.1. | Алгоритмы сжатия данных | Лекции | 6 | 2 | ПК-3 | Л2.2, Л1.1 |
| 4.2. | Изучение литературы по темам раздела 4 | Сам. работа | 6 | 11 | ПК-3 | Л2.2, Л1.1 |
| 4.3. | Алгоритмы распознавания образов на основе функций расстояния | Лекции | 6 | 2 | ПК-3 | Л2.2, Л1.1 |
| 4.4. | Генетические, муравьиные и параллельные алгоритмы | Лекции | 6 | 2 | ПК-3 | Л2.2, Л1.1 |
5. Фонд оценочных средств
| 5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
| 3.1 Перечень вопросов к защите лабораторных работ 1. Анализ алгоритмов. Какие существуют виды сложности алгоритма? 2. На какие 2 класса можно разбить все алгоритмы? 3. Анализ алгоритмов с повторением. 4. Анализ рекурсивных алгоритмов. 5. Классы входных данных. 6. Анализ наилучшего, наихудшего и среднего случая. 7. Что подразумевает рост сложности алгоритма? 8. Классификация скорости роста сложности алгоритма. 9. Алгоритм пузырьковой сортировки массива и его модификации. Сложность алгоритма. 10. Алгоритм сортировки массива вставками. Сложность алгоритма. 11. Алгоритм корневой сортировки массива. Сложность алгоритма. 12. Алгоритм сортировки Шелла. Влияние шага на эффективность. Сложность алгоритма. 13. Алгоритм быстрой сортировки массива и его модификации. Сложность алгоритма. 14. Алгоритм сортировки массива слиянием. Сложность алгоритма. 15. Алгоритм пирамидальной сортировки массива. Сложность алгоритма. 16. Алгоритм сортировки последовательностей прямым слиянием. 17. Алгоритм сортировки последовательностей естественным слиянием. 18. Алгоритм сортировки последовательностей сбалансированным многопутьевым слиянием. 19. Алгоритм многофазной сортировки последовательностей. 20. Алгоритмы генерации случайных чисел. 21. Алгоритм последовательного поиска. Его временная сложность. 22. Алгоритм бинарного поиска. Его временная сложность. 23. Алгоритм поиска К-го минимального элемента. 24. Алгоритм Кнута-Морриса-Пратта. 25. Алгоритм Бойера-Мура. 26. Структуры данных, используемые для представления графов. 27. Алгоритм обхода графа в глубину. 28. Алгоритм обхода графа в ширину. 29. Алгоритм построения минимального остовного дерева методом Дейкстры-Прима. 30. Алгоритм построения минимального остовного дерева методом Крускала. 31. Алгоритм разбиения множеств на непересекающиеся подмножества. 32. Алгоритм поиска кратчайшего пути методом Дейкстры. 33. Алгоритм определения компонент двусвязности графа. 3.2 Перечень теоретических вопросов к зачету (для оценки знаний) Раздел 1. Алгоритмы сортировки 1. Понятие и цель сортировки 2. Что такое сортировка? Чем отличаются внешняя и внутренняя сортировка? 3. Что такое практическая и теоретическая сложности? Можно ли из практической сложности вывести теоретическую? Можно ли из теоретической сложности вывести практическую? 4. Что такое максимальная, средняя и минимальная сложности? 5. Принцип работы метода пузырька 6. Принцип работы метода простого выбора 7. Принцип работы метода простых включений. 8. Принцип работы метода шейкерной сортировки 9. Принцип работы метода сортировки Шелла 10. Принцип работы метода бинарной сортировки 11. Принцип работы метода быстрой сортировки методом разделения 12. Оценка алгоритмов сортировки Раздел 2. Алгоритмы обработки текстов 1. Принцип алгоритма Боуэра-Мура 2. Принцип алгоритма Кнута-Мориса-Пратта 3. Принцип наивного алгоритма 4. Алгоритмы динамического программирования Раздел 3. Алгоритмы решения задач на графах. 1. Процедура поиска в ширину 2. Процедура поиска в глубину Раздел 4. Новые направления 1. Алгоритмы сжатия данных 2. Алгоритмы распознавания образов на основе функций расстояния 3. Генетические, муравьиные и параллельные алгоритмы 3.3 Перечень типовых простых практических заданий к зачету (для оценки умений) 1. Доказать, что метод Шелла действительно сортирует массив. 2. Доказать, что древесная сортировка действительно сортирует массив. 3. Доказать, что сортировка слиянием действительно сортирует массив. 4. Доказать, что сортировка распределением действительно сортирует массив. 3.9 Перечень типовых практических заданий к зачету (для оценки навыков и (или) опыта деятельности) Раздел 1. Алгоритмы сортировки Во всех задачах надо обязательно показать, почему Ваш алгоритм обеспечивает заданную временную сложность. Задача 1. Найти количество различных чисел среди элементов данного массива. Обеспечить число действий порядка n*log n. Указание. Отсортировать числа, а затем посчитать количество различных, просматривая элементы массива по порядку. Задача 2. Найти k-ое по порядку число среди элементов данного массива. Обеспечить число действий порядка n*log n. Указание. Отсортировать массив, а затем взять число, хранящееся в элементе массива с индексом k. Задача 3. Дано n отрезков [A[i], B[i]] на прямой (i=1..n), где A[i] – одномерная координата начала отрезка, а B[i] – конца отрезка. Найти максимальное k, для которого существует точка прямой, покрытая k отрезками ("максимальное число слоев"). Обеспечить число действий - порядка n*log n. Указание. Упорядочим все левые и правые концы отрезков вместе (при этом левый конец считается меньше правого конца, расположенного в той же точке прямой). Далее двигаемся слева направо, считая число слоев. Встреченный левый конец увеличивает число слоев на 1, правый - уменьшает. Отметим, что примыкающие друг к другу отрезки обрабатываются правильно: сначала идет левый конец (правого отрезка), а затем - правый (левого отрезка). Задача 4. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Обеспечить число действий порядка n*log n. Указание. Упорядочим точки по x-координате, а при равных x-координатах - по yкоординате. В таком порядке и можно проводить ломаную. Задача 5. Та же задача, если ломаная должна быть замкнутой. Указание. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи, а точки на одном луче поместим в порядке увеличения расстояния от начала луча. Задача 6. Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Форму выпуклой оболочки примет резиновое колечко, если его натянуть на гвозди, вбитые в точках.) Обеспечить число операций порядка n*log n. Указание. Упорядочим точки - годится любой из порядков, использованных в двух предыдущих задачах. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек. (Для хранения выпуклой оболочки полезно использовать дек – смотрите главу «Стеки, очереди, деки») Задача 7. Дан массив, состоящий из чисел 0, 1 и 2. Переместить все 0 в начало массива, а 2 – в конец. Обеспечить число действий порядка n. Указание. Воспользоваться вырожденной сортировкой распределением. Задача 8. В неупорядоченном массиве А могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один, удалив остальные и «поджав» массив к его началу. Обеспечить число операций порядка n*log n. Указание. Можно сначала отсортировать массив, а затем произвести его «поджатие» с удалением повторяющихся. При удалении очередного повтора не надо сразу сдвигать весь массив (это может привести к сложности T(n2)) – достаточно, рассматривая массив поэлементно и помня последний рассмотренный элемент, либо пропускать очередной, либо приписывать его к уже просмотренной части. Задача 9. Турнирная таблица соревнований представлена квадратной матрицей A, каждый элемент которой aij есть число голов, забитых i-ой командой в ворота j-ой команды. По диагонали расположить место каждой команды (по числу побед за вычетом числа поражений; в случае равенства – по разности забитых и пропущенных голов). Задача 10. В целочисленном массиве найти наибольшее число одинаковых элементов. Указание. Удобно предварительно отсортировать массив. |
| 5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
| Не предусматривается. |
| 5.3. Фонд оценочных средств для проведения промежуточной аттестации |
| Защита лабораторной работы (ЛР) . Собеседование . |
| Приложения |
6. Учебно-методическое и информационное обеспечение дисциплины
| 6.1. Рекомендуемая литература | ||||
| 6.1.1. Основная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л1.1 | Седжвик Р. | Алгоритмы на С++: Учебная литература для ВУЗов | Национальный Открытый Университет «ИНТУИТ», 2016 | biblioclub.ru |
| 6.1.2. Дополнительная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л2.1 | Мейер Б. | Инструменты, алгоритмы и структуры данных: Учебная литература для ВУЗов | Национальный Открытый Университет «ИНТУИТ», 2016 | biblioclub.ru |
| Л2.2 | Алексеев В. Е., Таланов В. А. | Структуры данных. Модели вычислений: Учебная литература для ВУЗов | Национальный Открытый Университет «ИНТУИТ», 2016 | biblioclub.ru |
| 6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет" | ||||
| 6.3. Перечень программного обеспечения | ||||
| Microsoft Windows Microsoft Office браузер Google Chrome Интегрированная среда разработки Компилятор С/С++Microsoft Office 2010 (Office 2010 Professional, № 4065231 от 08.12.2010), (бессрочно); Microsoft Windows 7 (Windows 7 Professional, № 61834699 от 22.04.2013), (бессрочно); Chrome (http://www.chromium.org/chromium-os/licenses), (бессрочно); 7-Zip (http://www.7-zip.org/license.txt), (бессрочно); AcrobatReader (http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf), (бессрочно); ASTRA LINUX SPECIAL EDITION (https://astralinux.ru/products/astra-linux-special-edition/), (бессрочно); LibreOffice (https://ru.libreoffice.org/), (бессрочно); Веб-браузер Chromium (https://www.chromium.org/Home/), (бессрочно); Антивирус Касперский (https://www.kaspersky.ru/), (до 23 июня 2024); Архиватор Ark (https://apps.kde.org/ark/), (бессрочно); Okular (https://okular.kde.org/ru/download/), (бессрочно); Редактор изображений Gimp (https://www.gimp.org/), (бессрочно) | ||||
| 6.4. Перечень информационных справочных систем | ||||
| Консультант+ consultant.ru | ||||
7. Материально-техническое обеспечение дисциплины
| Аудитория | Назначение | Оборудование |
|---|---|---|
| 202Л | кабинет информатики (компьютерный класс) - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 14 посадочных мест; компьютеры: марка HP - 14 единиц; мониторы: марка ASUS модель VS197DE - 14 единиц |
| 204Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260 - 14 единиц; Интерактивная доска Smart board 680 IV со встроенным проектором v25 |
| 206Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260, мониторы: марка Philips модель 227E3LHSU - 14 единиц |
| Учебная аудитория | для проведения занятий всех видов (дисциплинарной, междисциплинарной и модульной подготовки), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проекта (работы), проведения практики | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска, мультимедийное оборудование стационарное или переносное) |
8. Методические указания для обучающихся по освоению дисциплины
| 1. Для успешного освоения содержания дисциплины необходимо посещать лекции, принимать активное участие в работе на практическом занятии, а также выполнять задания, предлагаемые преподавателем для самостоятельного изучения. 2. Лекция. -На лекцию приходите не опаздывая, так как это неэтично. - На лекционных занятиях необходимо конспектировать изучаемый материал. - Для систематизации лекционного материала, который будет полезен при подготовке к итоговому контролю знаний, записывайте на каждой лекции тему, вопросы для изучения, рекомендуемую литературу. - В каждом вопросе выделяйте главное, обязательно запишите ключевые моменты (определение, факты, законы, правила и т.д.), подчеркните их. - Если по содержанию материала возникают вопросы, не нужно выкрикивать, запишите их и задайте по окончании лекции или на семинарском занятии. - Перед следующей лекцией обязательно прочитайте предыдущую, чтобы актуализировать знания и осознанно приступить к освоению нового содержания. 3.Практическое занятие – это форма работы, где студенты максимально активно участвуют в обсуждении темы. - Для подготовки к практическому занятию необходимо взять план занятия (у преподавателя). - Самостоятельную подготовку к занятию необходимо начинать с изучения понятийного аппарата темы. Рекомендуем использовать справочную литературу, учебники. - Важно запомнить, что любой источник должен нести достоверную информацию, особенно это относится к Internet-ресурсам. При использовании Internet - ресурсов в процессе подготовки не нужно их автоматически «скачивать», они должны быть проанализированы. Не нужно «скачивать» готовые рефераты, так как их однообразие преподаватель сразу выявляет, кроме того, они могут быть сомнительного качества. - В процессе изучения темы анализируйте несколько источников. Используйте научные специальные журналы. - Полезным будет работа с электронными учебниками и учебными пособиями в Internet-библиотеках. Зарегистрируйтесь в них: университетская библиотека Онлайн (http://www.biblioclub.ru/) и электронно-библиотечная система «Лань» (http://e.lanbook.com/). - При возникновении трудностей в процессе подготовки взаимодействуйте с преподавателем, консультируйтесь по самостоятельному изучению темы. 4. Самостоятельная работа. - При изучении дисциплины не все вопросы рассматриваются на лекциях и практических занятиях, часть вопросов рекомендуется преподавателем для самостоятельного изучения. - Поиск ответов на вопросы и выполнение заданий для самостоятельной работы позволит вам расширить и углубить свои знания по курсу, применить теоретические знания в решении задач практического содержания, закрепить изученное ранее. - Эти задания следует выполнять не «наскоком», а постепенно, планомерно, следуя порядку изучения тем курса. - При возникновении вопросов обратитесь к преподавателю в день консультаций на кафедру. - Выполнив их, проанализируйте качество их выполнения. Это поможет вам развивать умения самоконтроля и оценочные компетенции. 5. Итоговый контроль. - Для подготовки к зачету/экзамену возьмите перечень примерных вопросов у преподавателя. - В списке вопросов выделите те, которые были рассмотрены на лекции, практических занятиях. Обратитесь к своим записям, выделите существенное. Для более детального изучения изучите рекомендуемую литературу. - Если в списке вопросов есть те, которые не рассматривались на лекции, на практическом занятии, изучите их самостоятельно. Если есть сомнения, задайте вопросы на консультации перед экзаменом. - Продумайте свой ответ на экзамене, его логику. Помните, что ваш ответ украсит ссылка на источник литературы, иллюстрация практики применения теоретического знания, а также уверенность и наличие авторской аргументированной позиции как будущего субъекта профессиональной деятельности. |