алгоритм обработки данных. Учебнометодический комплекс по дисциплине " структуры и алгоритмы обработки данных" Для специальности "информатика и вычислительная техника"
 Скачать 27.24 Kb.
|
|
TEXTARCHIVE.RU Правообладателям Написать нам Главная > Учебно-методический комплекс “СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ” 12следующая → Смотреть полностью Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Армавирская государственная педагогическая академия» Институт прикладной информатики, математики и физики Факультет прикладной информатики и информационных технологий Кафедра информатики и информационных технологий обучения Утверждено на заседании кафедры информатики и ИТО Протокол № __ от ”____” ____________ 2012г. Зав. Кафедрой___________________ УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС По дисциплине “СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ” Для специальности: “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” 2 курс, 3 семестр – зачет, 4 семестр – экзамен. Составители: доц. Козырева Г.Ф., ст. преп. Лапшин Н.А. Армавир, 2012 г. 1. ЦЕЛИ И ЗАДАЧИ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ Методы и алгоритмы решения задач в программировании способствуют эффективной организации вычислительного процесса, повышают эффективность решаемой задачи. К наиболее важным задачам, возникающим при организации вычислительного процесса, следует отнести сегментацию программ, оптимальное размещение отдельных блоков программ, определение порядка решения задач с общими страницами в памяти ЭВМ, оптимальное размещение информации, контроль записей и т.п. Изучение курса «Структуры и алгоритмы обработки данных в ЭВМ» опирается на знания, умения и навыки, которые студенты должны получить при изучении дисциплин: «Математический анализ», «Информатика», «Программирование», «Дискретная математика». Целью изучения курса «Структуры и алгоритмы обработки данных в ЭВМ» является глубокое освоение студентами методов представления данных в памяти ЭВМ и основных алгоритмов, оперирующих с ними. Студент должен иметь представление: об основных структурах представления данных в ЭВМ; об алгоритмах, оперирующих со структурами; об использовании структур представления данных для решения возникающих задач; знать и уметь использовать: основные понятия алгоритмических структур для построения алгоритмов и задач по их математическим моделям; должен приобрести навыки: грамотной постановки задач, возникающих в практической деятельности для их решения с помощью ЭВМ; разработки оптимальных алгоритмов для решения поставленных задач; формализованного описания поставленных задач. Для достижения целей при совместной и индивидуальной познавательной деятельности студентов в части овладения теоретическими знаниями и практическими умениями используется полный набор методического материала: лекции, методические разработки к проведению лабораторных работ, тесты и контрольные задания для проверки знаний студентов, методические разработки к самостоятельной работе студентов по отдельным темам. Неотъемлемой частью курса является лабораторный практикум, при прохождении которого студентами приобретаются навыки программирования в интегрированной среде Borland Delphi 7 2. ТЕМАТИЧЕСКИЙ ПЛАН УЧЕБНОЙ ДИСЦИПЛИНЫ
3. СОДЕРЖАНИЕ УЧЕБНОГО МАТЕРИАЛА 3.1. Краткое содержание лекций 3 семестр Лекция 1. Основные типы данных Основные типы данных в языке программирования Turbo Pascal. Размерность и ограничения типов данных. Формы представления данных. Лекция 2. Указатели. Динамическая память Указательный тип данных. Типизированные и не типизированные указатели. Динамическая память. Принципы выделения памяти под данные. Понятие «кучи», «администратора кучи». Основные процедуры и функции работы с динамическими переменными. Лекция 3. Рекурсия Понятие рекурсии. Формы рекурсивных алгоритмов. Понятие глубины рекурсии. Преимущества и недостатки использования рекурсии. Лекция 4.Основные структуры данных. Стандартные массивы Способы описания стандартных массивов. Расположение массивов в памяти. Преимущества и недостатки использования стандартных массивов. Лекция 5. Основные структуры данных. Динамические массивы Способы описания динамических массивов. Расположение массивов в памяти. Основные принципы работы с динамическими массивами. Преимущества и недостатки использования динамических массивов. Лекция 6. Основные структуры данных. Записи. Множества Тип данных запись. Организация данных в форме записи. Основные принципы работы с записями. Тип данных множества. Основные процедуры и функции работы с множествами. Преимущества и недостатки работы с множествами. Лекция 7. Основные структуры данных. Списки. Односвязные списки: узлы связного списка; создание односвязного списка; вставка и удаление элементов в односвязном списке; прохождение связного списка. Лекция 8. Основные структуры данных. Списки Двухсвязные списки: класс двухсвязного списка; вставка и удаление элементов в двухсвязном списке; достоинства и недостатки связных списков. Лекция 9. Основные структуры данных. Стеки Стеки на основе односвязных списков. Стеки на основе массивов. Примеры использования стеков. Лекция 10. Основные структуры данных. Очереди Очереди на основе односвязных списков. Очереди на основе массивов. Примеры использования очередей. Лекция 11. Алгоритмы поиска данных Понятие поиска. Процедуры сравнения данных. Обзор алгоритмов поиска данных. Лекция 12. Алгоритмы поиска данных Последовательный поиск в сортированных и несортированных массивах. Последовательный поиск в связных списках. Лекция 13. Алгоритмы поиска данных Бинарный поиск в сортированных массивах. Бинарный поиск в связных списках. Лекция 14. Алгоритмы сортировки данных Задача сортировки (внешней и внутренней). Сортировка вставками, обменами, выбором. Лекция 15. Алгоритмы сортировки данных Быстрая сортировка. Процедура разделения. Рекурсивный и не рекурсивный алгоритмы быстрой сортировки. Анализ сложности. Оптимизация программы (неполная сортировка). Лекция 16. Алгоритмы сортировки данных Сравнение алгоритмов и программ внутренней сортировки. Нижняя граница сложности задачи сортировки. Оптимальная сортировка. 4 семестр Лекция 17. Хеширование Функции хеширования: простая функция хеширования для строк; функции хеширования PJW. Разрешение конфликтов посредством линейного зондирования. Лекция 18. Хеш-таблицы Класс хеш-таблиц с линейным зондированием. Класс связных хеш-таблиц. Хеш-таблицы на диске. Лекция 19. Рандомизированные алгоритмы. Генерация случайных чисел Критерий Хи-квадрат. Метод средних квадратов. Линейный конгруэнтный метод. Лекция 20. Рандомизированные алгоритмы. Генерация случайных чисел Тестирование: тест на однородность; тест на пропуски. Комбинирование генераторов. Аддитивные генераторы. Тасующие генераторы. Лекция 21. Рандомизированные алгоритмы. Списки с пропусками Поиск в списке с пропусками. Вставка в список с пропусками. Удаление из списка с пропусками. Лекция 22. Деревья и леса Определение дерева, леса, бинарного дерева. Графическое и текстовое (скобочное) представление леса. Спецификация дерева, леса, бинарного дерева: базовые функции и аксиомы. Естественное соответствие бинарного дерева и леса. Обходы бинарных деревьев: рекурсивные и не рекурсивные алгоритмы. Обходы дерева или леса. Лекция 23. Бинарные деревья Представления и реализации бинарных деревьев: ссылочная реализация в связанной памяти, ссылочная реализация ограниченного бинарного дерева на базе вектора. Прошитые бинарные деревья: представление, обход, включение. Лекция 24. Бинарные деревья Пример использования бинарных деревьев в задаче упаковки сообщений: префиксные коды и бинарные деревья, метод кодирования Фано-Шеннона, критерий оптимальности кода, алгоритм кодирования (сжатия) информации по Хаффману (построение дерева, кодирование и декодирование), доказательство оптимальности кода Хаффмана, неравенство Крафта, теорема кодирования в отсутствие шума (энтропийная оценка средней длины кода). Динамическое кодирование по Хаффману. Лекция 25. Ориентированные графы Графы: определения и примеры. Упорядоченный граф. Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности). Преобразования представлений. Лекция 26. Ориентированные графы Остовные деревья графа. Минимальное остовное дерево. Теорема ";о минимальном ребре";. Жадный алгоритм (Краскал). Алгоритм ";ближайшего соседа"; (Прим, Дейкстра). Лекция 27. Алгоритмы на графах Поиск в графе: алгоритм пометок. Поиск в ширину. Поиск в глубину. Связные компоненты. Алгоритм сложности О(m*log n) построения минимального остова. Построение и свойства остовных деревьев при поиске в глубину и в ширину. Поиск в глубину и топологическая сортировка. Нахождение компонент двусвязности: точки сочленения графа и их свойства в глубинном остовном дереве. Алгоритм нахождения компонент двусвязности. Лекция 28. Алгоритмы на графах Сильная связность. Поиск в глубину в орграфе. Алгоритм нахождения сильно связных компонент. Клики. Алгоритм порождения клик графа. Лекция 29. Алгоритмы на графах Кратчайшие пути в графе. Кратчайшие пути от фиксированной вершины. Случай неотрицательных весов: алгоритм Дейкстры. Алгоритм Форда-Беллмана. Кратчайшие пути в бесконтурном графе. Лекция 30. NP-полные и труднорешаемые задачи Массовая и индивидуальная задачи. Сложность алгоритма и кодирование входных и выходных данных. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP. Различные формы постановки задач комбинаторной оптимизации: оптимизационная, вычислительная, форма распознавания. Примеры. Лекция 31. NP-полные и труднорешаемые задачи Полиномиальная преобразуемость задач. NP-трудные и NP-полные задачи. Задача о выполнимости булева выражения, представленного в конъюнктивной нормальной форме. Доказательство NP-полноты задачи о выполнимости. Преобразуемость задачи о выполнимости в задачу о 3-выполнимости. Полиномиальность задачи о 2-выполнимости. Задача о клике графа. Преобразуемость задачи о 3-выполнимости в задачу о клике. Лекция 32. NP-полные и труднорешаемые задачи Задача о многопроцессорном расписании (МПР). Преобразуемость задачи о клике в задачу о МПР. Задача о 0-1-рюкзаке и криптография. Практическое решение NP-полных задач. 12следующая → Смотреть полностью Скачать документ Похожие документы: Структуры и алгоритмы обработки данных литература Литература Структуры и алгоритмыобработкиданных Лектор: Колинько Павел Георгиевич, кафедра ... Н. Алгоритмы и структурыданных. – СПб., 2001 (и более ранние издания). Ахо Дж., Хопкрофт А., Ульман Дж. Структурыданных и алгоритмы ... “СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ” Рабочая программа ... “СТРУКТУРЫ И АЛГОРИТМЫОБРАБОТКИДАННЫХ” Для ... Структуры и алгоритмыобработкиданных» является изучение применяемых в программировании (и информатике) структурданных, их спецификации и реализации, алгоритмовобработкиданных и анализа этих алгоритмов ... “СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ” (3) Рабочая программа ... “СТРУКТУРЫ И АЛГОРИТМЫОБРАБОТКИДАННЫХ” Для ... Структуры и алгоритмыобработкиданных» является изучение применяемых в программировании (и информатике) структурданных, их спецификации и реализации, алгоритмовобработкиданных и анализа этих алгоритмов ... “СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ” (4) Учебно-методический комплекс ... УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС По дисциплине “СТРУКТУРЫ И АЛГОРИТМЫОБРАБОТКИДАННЫХ” Для специальности: “ИНФОРМАТИКА И ... Дискретная математика». Целью изучения курса «Структуры и алгоритмыобработкиданных в ЭВМ» является глубокое освоение студентами ... «структуры и алгоритмы обработки данных» Методические указания ... дисциплине «Структуры и алгоритмыобработкиданных» для студентов специальности 220400 Часть 1 Базовые структурыданных и алгоритмы Одобрено ... навыков использования основных структурданных и алгоритмов их обработки. Лабораторные работы ориентированы ... Другие похожие документы.. textarchive.ru 2011 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||