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

Структура и алгоритмы обработки данных

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

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

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

Программу составил(и):
к.ф.-м.н., доцент, Жариков А.В.

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

Рабочая программа дисциплины
Структура и алгоритмы обработки данных

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

составлена на основании учебного плана:
09.03.03 Прикладная информатика
утвержденного учёным советом вуза от 25.06.2019 протокол № 9.

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

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

Заведующий кафедрой
к.ф.-м.н., доцент Жариков А.В.


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

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

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

Протокол от 22.06.2018 г. № 8
Заведующий кафедрой к.ф.-м.н., доцент Жариков А.В.


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

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

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

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

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

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

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

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Введение
1.1. Алгоритмы. Анализ сложности алгоритма. Алгоритмы сортировки. Рекурсивные алгоритмы. Лекции 4 2 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
1.2. Анализ сложности и эффективности алгоритма. Составление эффективного программного кода. Лабораторные 4 2 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
1.3. Язык Си и С++. Массивы. Указатели. Связь указателей и массивов. Динамические массивы. Указатели и параметры функций. Лабораторные 4 2 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
1.4. Язык С++. Массивы. Указатели. Связь указателей и массивов. Динамические массивы. Указатели и параметры функций. Сам. работа 4 10 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
Раздел 2. Динамические структуры данных
2.1. Абстрактные типы данных(АТД). Примеры. Создание АТД. Списки. Основные операции. Односвязный список. Реализация односвязных списков на основе массивов. Лекции 4 2 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.2. Создание и демонстрация работы АТД. Лабораторные 4 2 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.3. Создание и демонстрация работы АТД. Сам. работа 4 2 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.4. Реализация задачи "Word Count"(алфавитно-частотный словарь). Работа с файлами. Сам. работа 4 16 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.5. Списки. Односвязный список с динамическим распределением памяти. Двусвязный список. Задача "Word Count"(алфавитно-частотный словарь). Лекции 4 4 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.6. Реализация задачи "Word Count"(алфавитно-частотный словарь). Работа с файлами. Лабораторные 4 4 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.7. Стек. Очередь. Дек. Куча. Реализация. Лекции 4 2 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.8. Реализация дека с помощью двусвязный списка. Примеры использования. Лабораторные 4 6 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.9. Реализация дека с помощью двусвязный списка. Примеры использования. Сам. работа 4 10 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.10. Хэширование. Прямая адресация. Хэш-таблицы. Хэш-функции. Виды хэширования. Лекции 4 4 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.11. Реализация алгоритмов хэширования. Лабораторные 4 4 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.12. Реализация алгоритмов хэширования. Сам. работа 4 14 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.13. Деревья. Терминолония. Виды деревьев. Рекурсивное определение дерева. Обходы дерева. Реализации класса «бинарное дерево поиска». Бинарные деревья поиска. Очереди с приоритетом. Лекции 4 4 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.14. Реализации класса «бинарное дерево поиска». Бинарные деревья поиска. Лабораторные 4 4 ПК-21 Л1.1, Л2.1, Л1.3, Л1.2
2.15. Реализации класса «бинарное дерево поиска». Бинарные деревья поиска. Сам. работа 4 14 ПК-21 Л1.1, Л2.1, Л1.3, Л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
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Ландовский В.В. Структуры данных: учебное пособие Издательство НГТУ, 2016 www.studentlibrary.ru
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
6.3. Перечень программного обеспечения
Среда разработки Мicrosoft visual studio С++ (версия не ниже 2008)
Редактор Audacity http://www.audacityteam.org/
Microsoft Windows
Microsoft Office
7-Zip
AcrobatReader
6.4. Перечень информационных справочных систем
1. Visual C++ в Visual Studio 2015 - https://msdn.microsoft.com/ru-ru/library/60k1461a.aspx.
2. Cообщество людей, занятых в индустрии высоких технологий - https://habrahabr.ru.
1. Электронная база данных «Scopus» (http://www.scopus.com);
2. Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/);
3. Научная электронная библиотекаelibrary(http://elibrary.ru)

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

Аудитория Назначение Оборудование
519М электронный читальный зал с доступом к ресурсам «ПРЕЗИДЕНТСКОЙ БИБЛИОТЕКИ имени Б.Н. Ельцина» - помещение для самостоятельной работы Учебная мебель на 46 посадочных мест; 1 Флипчарт; компьютеры; ноутбуки с подключением к информационно-телекоммуникационной сети "Интернет" и доступом в электронную информационно-образовательную среду; стационарный проектор: марка Panasonic, модель PT-ST10E; стационарный экран: марка Projecta, модель 10200123; система видеоконференцсвязи Cisco Telepresence C20; конгресс система Bosch DCN Next Generation; 8 ЖК-панелей
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 в комплекте
204Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка DEPO модель Neos 260 - 14 единиц; Интерактивная доска Smart board 680 IV со встроенным проектором v25
203Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка ASUS модель i5-6500 - 14 единиц
202Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 14 посадочных мест; компьютеры: марка HP - 14 единиц; мониторы: марка ASUS модель VS197DE - 14 единиц

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

На лекционных занятиях необходимо конспектировать изучаемый материал.
- Для систематизации лекционного материала, который будет полезен при подготовке к итоговому контролю знаний, записывайте на каждой лекции тему, вопросы для изучения, рекомендуемую литературу.
- В каждом вопросе выделяйте главное, обязательно запишите ключевые моменты (определение, факты, законы, правила и т.д.), подчеркните их.
- Если по содержанию материала возникают вопросы, не нужно выкрикивать, запишите их и задайте по окончании лекции .
- Перед следующей лекцией обязательно прочитайте предыдущую, чтобы актуализировать знания и осознанно приступить к освоению нового содержания
Лабораторные работы, где студенты максимально активно участвуют в практическом приложении изучаемого материала дисциплины.
- Самостоятельную подготовку к занятию необходимо начинать с изучения понятийного аппарата темы. Рекомендуем использовать справочную литературу (словари, справочники, энциклопедии), целесообразно создать и вести свой словарь терминов.
- Важно запомнить, что любой источник должен нести достоверную информацию, особенно это относится к Internet-ресурсам. При использовании Internet - ресурсов в процессе подготовки не нужно их автоматически «скачивать», они должны быть проанализированы. Не нужно «скачивать» готовые рефераты, так как их однообразие преподаватель сразу выявляет, кроме того, они могут быть сомнительного качества.
- В процессе изучения темы анализируйте несколько источников. Используйте периодическую печать - специальные журналы.
- Полезным будет работа с электронными учебниками и учебными пособиями в Internet-библиотеках. Зарегистрируйтесь в них: университетская библиотека Онлайн (http://www.biblioclub.ru/) и электронно-библиотечная система «Лань» (http://e.lanbook.com/).
- В процессе подготовки и построения решения, поставленных задач, не просто читайте текст учебника, но и выражайте свою личностно-профессиональную оценку прочитанного.
- Задания практического характера: продумайте план их выполнения или решения .
- При возникновении трудностей в процессе работы взаимодействуйте с преподавателем, консультируйтесь по самостоятельному изучению темы.

Самостоятельная работа.
- При изучении дисциплины не все вопросы рассматриваются на занятиях, часть вопросов рекомендуется преподавателем для самостоятельного изучения.
- Поиск ответов на вопросы и выполнение заданий для самостоятельной работы позволит вам расширить и углубить свои знания по курсу, применить теоретические знания в решении задач практического содержания, закрепить изученное ранее.
- Эти задания следует выполнять не «наскоком», а постепенно, планомерно, следуя порядку изучения тем курса.
- При возникновении вопросов обратитесь к преподавателю в день консультаций на кафедру.
- Выполнив их, проанализируйте качество их выполнения. Это поможет вам развивать умения самоконтроля и оценочные компетенции.
Итоговый контроль.
- Для подготовки к зачету возьмите перечень примерных вопросов у преподавателя.
- В списке вопросов выделите те, которые были рассмотрены на занятиях. Обратитесь к своим записям, выделите существенное. Для более детального изучения изучите рекомендуемую литературу.
- Если в списке вопросов есть те, которые не рассматривались на занятии, изучите их самостоятельно.

Для освоения курса необходимо выполнить все лабораторные работы. Каждая лабораторная защищается студентом.