1. Цели освоения дисциплины
| 1.1. | Данный курс направлен на ознакомление студентов с фундаментальными алгоритмами обработки данных, а также с современными методами исследования алгоритмов и оценки их алгоритмической сложности, с методикой анализа сложности алгоритмов и классификации существующих задач в зависимости от их сложности. |
|---|
2. Место дисциплины в структуре ООП
| Цикл (раздел) ООП: Б1.О.4 |
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
| ОПК-2 | Способен применять компьютерные/суперкомпьютерные методы, современное программное обеспечение, в том числе отечественного происхождения, для решения задач профессиональной деятельности |
| ОПК-3 | Способен к разработке алгоритмических и программных решений в области системного и прикладного программирования, математических, информационных и имитационных моделей, созданию информационных ресурсов глобальных сетей, образовательного контента, прикладных баз данных, тестов и средств тестирования систем и средств на соответствие стандартам и исходным требованиям |
| ПК-6 | Способность применять в профессиональной деятельности современные языки программирования и методы параллельной обработки данных, операционные системы, электронные библиотеки и пакеты программ, сетевые технологии |
| В результате освоения дисциплины обучающийся должен | |
| 3.1. | Знать: |
|---|---|
| 3.1.1. | о различных парадигмах программирования и современном уровне развития языков и технологий программирования; о сложности программных систем и методах ее преодоления; методы анализа сложности алгоритмов; синтаксис и базовые конструкции языка C,С++; назначение, устройство и свойства основных структур данных: список, очередь, стэк, дерево, граф; эффективные алгоритмы для работы с различными структурами данных; методы вычисления сложности алгоритмов; алгоритмы обработки динамических структур данных; основные парадигмы программирования; особенности стандартов языков программирования Си и С++. |
| 3.2. | Уметь: |
| 3.2.1. | использовать для разработки и отладки программ современные интегрированные среды разработки языка программирования Си и С++; использовать эффективные алгоритмы поиска и обработки сложных структур данных; использовать для разработки и отладки программ современные интегрированные среды разработки. |
| 3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
| 3.3.1. | написания, отладки программ и мониторинга качества программного кода на высокоуровневом языке программирования в интегрированной среде разработки. |
4. Структура и содержание дисциплины
| Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
|---|---|---|---|---|---|---|
| Раздел 1. Введение | ||||||
| 1.1. | Язык Си и С++. Массивы. Указатели. Связь указателей и массивов. Динамические массивы. Указатели и параметры функций. | Лабораторные | 3 | 2 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 1.2. | Анализ сложности и эффективности алгоритма. Составление эффективного программного кода. | Лабораторные | 3 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 1.3. | Язык С++. Массивы. Указатели. Связь указателей и массивов. Динамические массивы. Указатели и параметры функций. | Сам. работа | 3 | 6 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| Раздел 2. Динамические структуры данных | ||||||
| 2.1. | Абстрактные типы данных(АТД). Примеры. Создание АТД. Списки. Основные операции. Односвязный список. Реализация односвязных списков на основе массивов. | Лекции | 3 | 2 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.2. | Создание и демонстрация работы АТД. | Лабораторные | 3 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.3. | Создание и демонстрация работы АТД. | Сам. работа | 3 | 8 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.4. | Реализация задачи "Word Count"(алфавитно-частотный словарь). Работа с файлами. | Сам. работа | 3 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.5. | Реализация задачи "Word Count"(алфавитно-частотный словарь). Работа с файлами. | Лабораторные | 3 | 6 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.6. | Реализация дека с помощью двусвязный списка. Примеры использования. | Лабораторные | 3 | 6 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.7. | Реализация дека с помощью двусвязный списка. Примеры использования. | Сам. работа | 3 | 8 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.8. | Реализация алгоритмов хэширования. | Лабораторные | 3 | 6 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.9. | Реализация алгоритмов хэширования. | Сам. работа | 3 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.10. | Деревья. Терминолония. Виды деревьев. Рекурсивное определение дерева. Обходы дерева. Реализации класса «бинарное дерево поиска». Бинарные деревья поиска. Очереди с приоритетом. | Лекции | 3 | 2 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.11. | Реализации класса «бинарное дерево поиска». Бинарные деревья поиска. | Лабораторные | 3 | 6 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.12. | Реализации класса «бинарное дерево поиска». Бинарные деревья поиска. | Сам. работа | 3 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.13. | Программная реализация AVL-дерева. | Лабораторные | 4 | 6 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.14. | Программная реализация AVL-дерева. | Сам. работа | 4 | 7 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.15. | Программная реализация красно-черных деревьев. | Лабораторные | 4 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.16. | Программная реализация красно-черных деревьев. | Сам. работа | 4 | 8 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.17. | Программная реализация SPLAY-деревьев. | Лабораторные | 4 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.18. | Программная реализация SPLAY-деревьев. | Сам. работа | 4 | 8 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.19. | Программная реализация Б-деревьев. | Лабораторные | 4 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.20. | Программная реализация Б-деревьев. | Сам. работа | 4 | 8 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.21. | Программная реализация операций над биномиальными деревьями. | Лабораторные | 4 | 2 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 2.22. | Программная реализация операций над биномиальными деревьями. | Сам. работа | 4 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| Раздел 3. Сложные структуры данных | ||||||
| 3.1. | Задачи на графах. | Лабораторные | 4 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 3.2. | Задачи на графах. | Сам. работа | 4 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 3.3. | Реализация с использованием списков. | Лабораторные | 4 | 4 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 3.4. | Реализация с использованием списков. | Сам. работа | 4 | 3 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 3.5. | Программная реализация алгоритмов на графах. | Лабораторные | 4 | 6 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 3.6. | Программная реализация алгоритмов на графах. | Сам. работа | 4 | 5 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 |
| 3.7. | Экзамен | 4 | 27 | ОПК-2, ОПК-3, ПК-6 | Л1.1, Л2.1, Л1.3, Л1.2 | |
5. Фонд оценочных средств
| 5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
| в приложении |
| 5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
| в приложении |
| 5.3. Фонд оценочных средств для проведения промежуточной аттестации |
| в приложении |
| Приложения |
|
Приложение 1.
ФИиИТ_ФОС_1_СиАОД_19-20.docx
|
6. Учебно-методическое и информационное обеспечение дисциплины
| 6.1. Рекомендуемая литература | ||||
| 6.1.1. Основная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л1.1 | Хиценко В.П. | Структуры данных и алгоритмы: учебное пособие | Издательство НГТУ, 2016 | www.studentlibrary.ru |
| Л1.2 | Мейер Б. | Инструменты, алгоритмы и структуры данных: Учебная литература для ВУЗов | Национальный Открытый Университет «ИНТУИТ», 2016 | biblioclub.ru |
| Л1.3 | Вирт Н. | Алгоритмы и структуры данных. Новая версия для Оберона: Учебные пособия | Издательство "ДМК Пресс", 2010 | e.lanbook.com |
| 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 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. Перечень информационных справочных систем | ||||
| 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. Материально-техническое обеспечение дисциплины
| Аудитория | Назначение | Оборудование |
|---|---|---|
| Помещение для самостоятельной работы | помещение для самостоятельной работы обучающихся | Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ |
| Учебная аудитория | для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска) |
| 106Л | помещение для хранения и профилактического обслуживания учебного оборудования | Стеллажи – 3 шт. осциллограф, паяльная станция, источник тока, переносные ноутбуки |
| 207Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260, мониторы: марка Philips модель 227E3LHSU - 14 единиц |
| 206Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260, мониторы: марка Philips модель 227E3LHSU - 14 единиц |
| 205Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 9 посадочных мест; компьютеры: марка КламаС Офис, мониторы: марка ACER модель V223HQL - 8 единиц; доска интерактивная Triumph MULTI TOUCH 78 + проектор NEC UM280X в комплекте |
| 203Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 14 посадочных мест; компьютеры: марка ASUS модель i5-6500 - 14 единиц |
| 202Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 14 посадочных мест; компьютеры: марка HP - 14 единиц; мониторы: марка ASUS модель VS197DE - 14 единиц |
8. Методические указания для обучающихся по освоению дисциплины
| Изучение дисциплины завершается зачетом в 3 семестре и экзаменом в 4 семестре. Успешное изучение дисциплины требует посещения лекций, активной работы на лабораторных работах, выполнения всех практических заданий преподавателя, ознакомления с основной и дополнительной литературой. Во время лекции студент должен вести краткий конспект. При этом обучающийся должен стараться найти ответы на затруднительные вопросы, используя рекомендуемую литературу или общедоступные ресурсы. Если ему самостоятельно не удалось разобраться в материале, необходимо сформулировать вопросы и обратится за помощью к преподавателю на консультации или ближайшей лекции. Выполнение студентами практических заданий направлено на: - обобщение, систематизацию, углубление, закрепление полученных теоретических знаний по конкретным темам дисциплин; - формирование необходимых профессиональных умений и навыков. Помимо собственно выполнения практических заданий для каждого задания предусмотрена процедура защиты, в ходе которой преподаватель проводит устный или письменный опрос студентов для контроля понимания выполненных ими действий по теме занятия. При подготовке к зачету в дополнение к изучению конспектов лекций, учебно-методических материалов и слайдов, необходимо пользоваться учебной литературой, рекомендованной настоящей программой. При подготовке к зачету/экзамену нужно изучить определения всех понятий и теоретические подходы до состояния понимания материала, а также выполнить все практические задания в курсе. |