rpd000006138 (1010413)
Текст из файла
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Московский авиационный институт
(национальный исследовательский университет)
УТВЕРЖДАЮ
Проректор по учебной работе
______________Куприков М.Ю.
“____“ ___________20__
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (000006138)
Структуры и алгоритмы обработки данных
(указывается наименование дисциплины по учебному плану)
| Направление подготовки | Программная инженерия | |||||
| Квалификация (степень) выпускника | Бакалавр | |||||
| Профиль подготовки | Программно-информационные системы | |||||
| Форма обучения | очная | |||||
| (очная, очно-заочная и др.) | ||||||
| Выпускающая кафедра | 304 | |||||
| Обеспечивающая кафедра | 304 | |||||
| Кафедра-разработчик рабочей программы | 304 | |||||
| Семестр | Трудоем-кость, час. | Лек-ций, час. | Практич. занятий, час. | Лаборат. работ, час. | СРС, час. | Экзаменов, час. | Форма промежуточного контроля |
| 4 | 144 | 32 | 0 | 36 | 49 | 27 | Э |
| Итого | 144 | 32 | 0 | 36 | 49 | 27 |
Москва
2011 г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Разделы рабочей программы
-
Цели освоения дисциплины
-
Структура и содержание дисциплины
-
Учебно-методическое и информационное обеспечение дисциплины
-
Материально-техническое обеспечение дисциплины
Приложения к рабочей программе дисциплины
Приложение 1. Аннотация рабочей программы
Приложение 2. Cодержание учебных занятий
Приложение 3. Прикрепленные файлы
Программа составлена в соответствии с требованиями ФГОС ВПО по направлению подготовки 231000 Программная инженерия
Авторы программы :
| Силаев А.В. | _________________________ |
| Заведующий обеспечивающей кафедрой 304 | _________________________ |
Программа одобрена:
| Заведующий выпускающей кафедрой 304 _________________________ | Декан выпускающего факультета 3 _________________________ |
-
ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Целью освоения дисциплины Структуры и алгоритмы обработки данных является достижение следующих результатов образования (РО):
| N | Шифр | Результат освоения |
| 1 | Знания: на уровне представлений: основных методов, алгоритмов и структур данных, используемых в современных операционных системах компьютеров | |
| 2 | Знания: на уровне воспроизведения: основных операций, выполняемых над структурами данных, и основных алгоритмов обработки данных | |
| 3 | Знания: на уровне понимания: программной организации основных структур данных, а также алгоритмов их обработки | |
| 4 | Умения: теоретические: разрабатывать алгоритмы обработки основных структур данных для решения практических задач | |
| 5 | Умения: практические: создавать и исполнять программы на языке высокого уровня | |
| 6 | Навыки: использования алгоритмических языков программирования на персональном компьютере, разработки и отладки программ |
Перечисленные РО являются основой для формирования следующих компетенций: (в соответствии с ФГОС ВПО и требованиями к результатам освоения основной образовательной программы (ООП))
| N | Шифр | Компетенция |
| 1 | ПК-2 | Способность к формализации в своей предметной области с учетом ограничений используемых методов исследования |
| 2 | ПК-3 | Готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности |
| 3 | ПК-10 | Умение применять основы информатики и программирования к проектированию, конструированию и тестированию программных продуктов |
| 4 | ПК-12 | Навыки моделирования, анализа и использования формальных методов конструирования программного обеспечения |
-
СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Общая трудоемкость дисциплины составляет 4 зачетных(ые) единиц(ы), 144 часа(ов).
| Модуль | Раздел | Лекции | Практич. занятия | Лаборат. работы | СРС | Всего часов | Всего с экзаменами и курсовыми |
| Структуры и алгоритмы обработки данных | Основные понятия и определения | 6 | 0 | 0 | 5 | 11 | 144 |
| Алгоритмы поиска | 4 | 0 | 8 | 4 | 16 | ||
| Линейные структуры данных | 16 | 0 | 20 | 16 | 52 | ||
| Хеширование | 6 | 0 | 8 | 6 | 20 | ||
| Всего | 32 | 0 | 36 | 31 | 99 | 144 | |
-
Содержание (дидактика) дисциплины
В разделе приводится полный перечень дидактических единиц, подлежащих усвоению при изучении данной дисциплины.
1. Основные понятия и определения
- 1.1. Алгоритм. Свойства алгоритма. Основные этапы подготовки задачи к решению на компьютере.
- 1.2. Типы данных. Абстрактный тип данных.
- 1.3. Структуры данных. Классификация структур данных.
- 1.4. Структуры хранения данных: вектор, список, сеть.
2. Алгоритмы поиска
- 2.1. Поиск в таблице. Виды таблиц.
- 2.2. Алгоритмы последовательного поиска: простой последовательный поиск, быстрый последовательный поиск, последовательный поиск в упорядоченной таблице.
- 2.3. Прямой поиск в упорядоченной таблице: бинарный поиск, поиск Фибоначчи.
- 2.4. Оценка временной сложности алгоритмов с использованием О-символики.
3. Линейные структуры данных
3.1. Массивы
- 3.1.1. Структура данных «массив».
- 3.1.2. Структура хранения массива.
- 3.2. Линейные списки и их разновидности.
3.3. Стеки.
- 3.3.1. Векторная и списковая структуры хранения стека.
- 3.3.2. Операции над стеками.
3.4. Очереди.
- 3.4.1. Структуры хранения очереди.
- 3.4.2. Операции над очередями.
- 3.4.3. Реализация очередей с помощью циклических массивов.
- 3.4.4. Очереди с приоритетами.
- 3.5. Деки, их разновидности и операции над деками.
- 3.6. Реализация списков посредством массивов.
- 3.7. Сравнение реализаций списков на основе массивов и указателей.
4. Хеширование
- 4.1. Постановка задачи хеширования.
- 4.2. Виды хеш-функций.
- 4.3. Открытое хеширование. Оценка эффективности открытого хеширования.
- 4.4. Закрытое хеширование. Оценка эффективности закрытого хеширования.
-
Лекции
| № п/п | Раздел дисциплины | Объем, часов | Тема лекции | Дидакт. единицы |
| 1 | 1.1.Основные понятия и определения | 2 | Понятие алгоритма. Свойства алгоритма. Типы данных. Абстрактный тип данных. Структуры данных. Классификация структур данных | 1.1, 1.2, 1.3 |
| 2 | 1.1.Основные понятия и определения | 2 | Структуры хранения данных. Возможности представления структур данных в оперативной памяти компьютера. | 1.4 |
| 3 | 1.1.Основные понятия и определения | 2 | Основные структуры хранения данных | 1.4 |
| 4 | 1.2.Алгоритмы поиска | 2 | Поиск в таблице. Виды таблиц. Алгоритмы последовательного поиска | 2.1, 2.2 |
| 5 | 1.2.Алгоритмы поиска | 2 | Алгоритмы прямого поиска в упорядоченной таблице: бинарный поиск, поиск Фибоначчи. Оценка временной сложности алгоритмов с использованием О-символики | 2.3, 2.4 |
| 6 | 1.3.Линейные структуры данных | 2 | Структура данных «массив». Структура хранения массива | 3.1.1, 3.1.2 |
| 7 | 1.3.Линейные структуры данных | 2 | Линейные списки и их разновидности | 3.2 |
| 8 | 1.3.Линейные структуры данных | 2 | Стеки. Векторная и списковая структуры хранения стека. Операции над стеками | 3.3.1, 3.3.2 |
| 9 | 1.3.Линейные структуры данных | 2 | Очереди. Структуры хранения очереди. Операции над очередями | 3.4.1, 3.4.2 |
| 10 | 1.3.Линейные структуры данных | 2 | Реализация очередей с помощью циклических массивов. Очереди с приоритетами | 3.4.3, 3.4.4 |
| 11 | 1.3.Линейные структуры данных | 2 | Деки и их разновидности. Структуры хранения деков | 3.5 |
| 12 | 1.3.Линейные структуры данных | 2 | Операции над деками | 3.5 |
| 13 | 1.3.Линейные структуры данных | 2 | Реализация списков посредством массивов. Сравнение реализаций списков на основе массивов и указателей | 3.6, 3.7 |
| 14 | 1.4.Хеширование | 2 | Постановка задачи хеширования. Виды хеш-функций | 4.1, 4.2 |
| 15 | 1.4.Хеширование | 2 | Открытое хеширование. Оценка эффективности открытого хеширования | 4.3 |
| 16 | 1.4.Хеширование | 2 | Закрытое хеширование. Оценка эффективности закрытого хеширования | 4.4 |
| Итого: | 32 | |||
-
Практические занятия
| № п/п | Раздел дисциплины | Объем, часов | Тема практического занятия | Дидакт. единицы |
| Итого: | ||||
-
Лабораторные работы
| № п/п | Раздел дисциплины | Наименование лабораторной работы | Наименование лаборатории | Объем, часов | Дидакт. единицы |
| 1 | 1.2.Алгоритмы поиска | Алгоритмы последовательного поиска | Компьютерный класс кафедры 304 | 4 | 2.2 |
| 2 | 1.2.Алгоритмы поиска | Алгоритмы прямого поиска в упорядоченной таблице | Компьютерный класс кафедры 304 | 4 | 2.3 |
| 3 | 1.3.Линейные структуры данных | Линейные списки | Компьютерный класс кафедры 304 | 8 | 3.2 |
| 4 | 1.3.Линейные структуры данных | Стеки | Компьютерный класс кафедры 304 | 4 | 3.3.1, 3.3.2 |
| 5 | 1.3.Линейные структуры данных | Очереди с приоритетами | Компьютерный класс кафедры 304 | 4 | 3.4.1, 3.4.2, 3.4.3, 3.4.4 |
| 6 | 1.3.Линейные структуры данных | Деки | Компьютерный класс кафедры 304 | 4 | 3.5 |
| 7 | 1.4.Хеширование | Открытое хеширование | Компьютерный класс кафедры 304 | 4 | 4.3 |
| 8 | 1.4.Хеширование | Закрытое хеширование | Компьютерный класс кафедры 304 | 4 | 4.4 |
| Итого: | 36 | ||||
-
Типовые задания
| № п/п | Раздел дисциплины | Объем, часов | Наименование типового задания |
| Итого: | |||
-
Курсовые работы и проекты по дисциплине
1.1. Линейные списки
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
