Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика
жүктеу/скачать 3,71 Mb.
|
УМКАлгор и стр данн Инеттен (1)
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ СОЦИОКУЛЬТУРНЫХ КОММУНИКАЦИЙ КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ А. В. Овсянников, Ю.А. Пикман АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ Часть I УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДЛЯ СПЕЦИАЛЬНОСТИ 1-31 03 07 ПРИКЛАДНАЯ ИНФОРМАТИКА (по направлениям) Минск 2015 УДК004.421(075.8)+004.422.63(075.8) О-345
А в т о р ы: профессор кафедры информационных технологий факультета социокультурных коммуникаций Белорусского государственного университета к. т. н., доцент А. В. Овсянников, старший преподаватель кафедры информационных технологий факультета социокультурных коммуникаций Белорусского государственного университета Ю. А. Пикман
Рецензенты: заведующий кафедрой систем управления Белорусского государственного университета информатики и радиоэлектроники, к.т.н., доцент Марков А.В.,
кафедра информационных радиотехнологий Белорусского государственного университета информатики и радиоэлектроники, В. М. Козел, к. т. н., доцент; Решение о депонировании документа вынес Совет гуманитарного факультета БГУ 02.03.2015 г., протокол № 8 Овсянников, А. В. Алгоритмы и структуры данных : учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика (по направлениям)». Ч. 1 / А. В. Овсянников, Ю. А. Пикман ; БГУ, Фак. социокультурных коммуникаций, Каф. информационных технологий. – Минск : БГУ, 2015. – 124 с. : ил. – Библиогр.: с. 122 Учебно-методическийкомплекссодержитматериал,включающий фундаментальные понятия алгоритма, размерности задачи, трудоемкости алгоритмов, структур данных. Комплекс представлен теоретическим разделом с контрольными вопросами и лабораторным практикумом, а также учебной программой дисциплины. В теоретическом разделе рассматриваются общие вопросы методологии теории алгоритмов и структур данных, абстрактные вычислительные машины, анализ трудоемкости алгоритмов и введение в структуры данных. Лабораторный практикум содержит материал для самостоятельного выполнения и исследования организации работы линейных списков и бинарного дерева. Адресуется студентам специальности «Прикладная информатика» гуманитарного факультета БГУ. Может быть использован в процессе изучения методики анализа алгоритмов и основ программирования студентами других специальностей. УДК004.421(075.8)+ 004.422.63(075.8) © А.В. Овсянников, Ю.А. Пикман
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Учебно-методический комплекс включает: 1.Овсянников А.В. Учебная программа учреждения высшего образования по учебной дисциплине для специальности: 1-31 03 07-03Прикладная информатика Алгоритмы и структуры данных № УД-1499/р. Режим доступа: http://elib.bsu.by/handle/123456789/85554 2.Данное пособие «Алгоритмы и структуры данных (часть I)», содержание которого полностью соответствует учебной программе дисциплины и включает 9 учебных модулей по следующим разделам: 1) теоретическую часть: методологические основы теории алгоритмов и структур данных; абстрактные вычислительные машины; анализ алгоритмов; введение в структуры данных; 2) лабораторный практикум: организация и принципы работы с односвязным линейным списком; изучение принципов организации и работы абстрактной структуры данных стек; изучение принципов организации и работы абстрактной структурой данных очередь; изучение принципов организации и работы с абстрактной структурой данных двухсвязный линейный список; изучение принципов организации и работы с абстрактной структурой данных бинарное дерево. В каждом теоретическом модуле в достаточной мере изложен основной теоретический материал, который подкрепляется значительным количеством иллюстраций и примеров. Каждый модуль содержит: 1) теоретическую часть, представленную в виде краткого конспекта лекций; 2) систему контрольных вопросов и заданий для аудиторной и самостоятельной работы студентов. Учебно-методический комплекс предназначен для организации аудиторной и самостоятельной работы студентов информационных специальностей вузов в процессе изучения дисциплины «Алгоритмы и структуры данных». Сформированная система знаний, умений и навыков необходима студентам для осуществления профессиональной деятельности и развития сферы их научно-исследовательских интересов в области веб-программирования, освоения принципов программирования веб-сайтов и веб-интерфейсов. Methodical complex is designed to organize classroom and independent work of students of information professions schools in the process of studying the discipline "Algorithms and Data Structures." Formed a system of knowledge and skills necessary for students to carry out professional activities and development of the scope of their research interests in the field of web programming, mastering the principles of programming websites and web interfaces. 3 1. МЕТОДОЛГИЯ ТЕОРИИ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Хорезми Мухаммед бен-Муса (825 г н.э.). В явном виде понятие алгоритма сформировалось в начале XX века благодаря работам таких учёных, как Д. Гильберт, К. Гёдель, С. Клини, А.Чёрч, Э. Пост, А. Тьюринг, Н. Винер, А.А. Марков. Одним из старейших численных алгоритмов считается алгоритм Евклида (III век до н.э.) – нахождения наибольшего общего делителя двух чисел. Современная теория алгоритмов началась с работ немецкого математика Курта Гёделя (1931 год), в которых было показано существование задач, не разрешимых в рамках своей формальной, непротиворечивой системы аксиом. Первые фундаментальные работы по теории алгоритмов появились в 1936 году. Предложены машина Тьюринга, Поста и λ-исчисление Чёрча. Эти машины были эквивалентными формализациями алгоритма. «Алгоритм – это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность» (Д. Э. Кнут). «Алгоритм – это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи» (А. Колмогоров). «Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату» (А. Марков). «Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа» (Философский словарь под ред. М. М. Розенталя). В 1950-е годы вклад в теорию алгоритмов внесли работы Колмогорова и Маркова. К 1960-1970 годам оформились направления исследований в теории алгоритмов: Классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешимости, введение 4 сложностных классов, формулировка проблемы P=NP(?), открытие класса NP-полных задач и его исследование); Теория асимптотического анализа алгоритмов (понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения); Теория практического анализа вычислительных алгоритмов (получение явных функций трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов), основополагающей работой в этом направлении, можно считать фундаментальный труд Д. Кнута «Искусство программирования для ЭВМ» алгоритмов.
ЦЕЛИ И ЗАДАЧИ ТЕОРИИ АЛГОРИТМОВ Цели и задачи, решаемые в теории алгоритмов: формализация понятия «алгоритм» и исследование формальных алгоритмических систем; формальное доказательство алгоритмической неразрешимости задач; классификация задач, определение и исследование сложностных классов;
асимптотический анализ сложности алгоритмов; исследование и анализ рекурсивных алгоритмов; получение явных функций трудоемкости в целях сравнительного анализа алгоритмов; разработка критериев сравнительной оценки качества алгоритмов.
ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ ТЕОРИИ АЛГОРИТМОВ Теоретический аспект При исследовании некоторой задачи позволяет ответить на вопросы: 1) является задача в принципе алгоритмически разрешимой? В случае «ДА» возникает следующий вопрос: Принадлежит ли эта задача к классу NP–полных задач? При утвердительном ответе, анализируют временные затраты на получения точного решения для больших размерностей исходных данных.
5 2) для алгоритмически неразрешимых задач возможно ли их сведение к задаче останова машины Тьюринга? Практический аспект
Методы и методики теории алгоритмов позволяют осуществить: рациональный выбор из известного множества алгоритмов решения задачи с учетом особенностей их применения (например, при ограничениях на размерность исходных данных или объема дополнительной памяти); получение временных оценок решения сложных задач; получение достоверных оценок невозможности решения некоторой задачи за определенное время, что важно для криптографических методов;
разработку и совершенствование эффективных алгоритмов решения задач в области обработки информации на основе практического анализа.
ФОРМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОРИТМА Определение 1. Алгоритм – это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных. Пусть D – область (множество) исходных данных задачи, а R – множество возможных результатов, тогда алгоритм осуществляет отображение 𝐃 → 𝐑.Это отображение может быть не полным. Алгоритм называется частичным алгоритмом, если получен результат только для некоторых 𝑑 ∈ 𝐷 иполным алгоритмом, если алгоритм получает правильный результат для всех 𝑑 ∈ 𝐷. Определение 2. Алгоритм – точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.
Различные определения алгоритма в явной или неявной форме влекут за собой ряд требований: алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т.е. удовлетворять требованию конечности записи;
6 алгоритм должен выполнять конечное количество шагов при решении задачи, т.е. удовлетворять требованию конечности действий; алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности; алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности. ФОРМАЛЬНЫЕ СВОЙСТВА АЛГОРИТМОВ Дискретность— алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. Для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно. Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд. Завершаемость(конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. Вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0. Массовость — универсальность. Алгоритм должен быть применим к разным наборам исходных данных. Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе. Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных. Существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного. По виду входных и выходных данных можно выделить
Алгоритмы для решения численных задач (появились первыми); Нечисловые алгоритмы. 7 ПОНЯТИЕ СТРУКТУРЫ ДАННЫХ Структура данных — множество элементов данных и множество связей между ними. Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных с помощью вычислительной техники.
Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Структура данных является реализацией какого-либо абстрактного типа данных.
Для точного описания абстрактных структур данных и алгоритмов программ используются системы формальных обозначений – языки программирования, в которых смысл всякого предложения определяется точно и однозначно. Структура данных относится к "пространственным" понятиям: ее можно свести к схеме организации информации в памяти компьютера (рис.1).
Рис. 1. Схема организации информации в памяти компьютера Понятие "физическая структура данных" соответствует способу физического представления данных в памяти машины и называется ещё структурой хранения, внутренней структурой или структурой памяти.
Структуры данных, которая рассматривается без учета ее представления в машиннойпамятиназываетсяабстрактнойилилогической структурой(рис.2).
8 Рис.2. Способ представления структуры данных С понятием «структура данных» тесно связано понятие «тип данных». Например, натуральные и целые числа, вещественные числа (в виде приближенных десятичных дробей), символы алфавита, строки и т.п. – это типы данных. В языках программирования тип данных (констант и переменных) определяется компилятором автоматически или задается явно. Информация по каждому типу данных однозначно определяет: способ хранения данных указанного типа, т.е. выделение памяти и представление данных в ней и интерпретирование двоичного представления; множество допустимых значений, которые может принимать тот или иной объект указанного типа; множество допустимых операций, которые применимы к объекту указанного типа. КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ По сложности: Простые (базовые, примитивные); Интегрированные (композитные, сложные). По связи между элементами: Связные (связные списки); Несвязные (векторы, массивы, строки, очереди). Линейные структуры по расположению элементов в памяти: Последовательные (векторы, строки, массивы, стеки, очереди); Произвольные (односвязные, двусвязные списки). Нелинейные структуры Многосвязные списки, деревья, графы. 9 Рис.3. Классификация структур данных ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ Создание – выделение памяти для структуры данных. Уничтожение – противоположна по своему действию операции создания. Выбор – обеспечивает доступ к данным внутри самой структуры. Обновление – позволяет изменять значения данных в структуре и добавлять (удалять) выбранные данные. СТРУКТУРНОСТЬ ДАННЫХ И ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ Структуры данных позволяют организовать их хранение и обработку максимально эффективным образом, с точки зрения минимизации затрат памяти и процессорного времени; Правильный выбор структуры программного продукта дает возможность сосредоточиться на одной обозримой части программного продукта на каждом этапе разработки и обеспечить реализацию разных его частей одновременно;
10 Известно, что от 50 до 100% времени программиста тратится на исправление и модификацию программ. Поэтому современная индустрия программирования предлагает системные подходы к программированию, использование которых: уменьшает вероятность ошибок в программах; упрощает их понимание; облегчает модификацию; Структурное программирование – одна из популярных методик, фундаментом которой является теорема о структурировании.
Теорема. Как бы сложна ни была задача, блок-схема соответствующей программы (алгоритма) всегда может быть представлена с использованием ограниченного числа элементарных управляющих структур (последовательность, ветвление, цикл). Идея доказательства: преобразование каждой части алгоритма в одну из трех основных структур или их комбинацию; после достаточного числа таких преобразований оставшаяся неструктурированной часть либо исчезнет, либо станет ненужной; в результате получится алгоритм, эквивалентный исходному и использующий лишь 3 управляющие структуры. Цель структурного программирования – выбор структуры программы путем разложения исходной задачи на подзадачи (декомпозиция). Программы должны иметь простую структуру. Разработка алгоритма упрощается на каждом уровне шаг за шагом.
При этом используется метод пошагового уточнения (Рис.4): задача рассматривается в целом, выделяются наиболее крупные ее части, алгоритм, указывающий порядок выполнения этих частей, описывается в структурированной форме, не вдаваясь в мелкие детали; от общей структуры переходят к описанию отдельных частей и, таким образом, разработка алгоритма состоит из последовательности шагов в направлении уточнения алгоритма. 11 Рис.4. Метод пошагового уточнения ПРИНЦИП МОДУЛЬНОГО ПРОГРАММИРОВАНИЯ Модульное программирование позволяет ускорить процесс за счет привлечения к работе нескольких специалистов сразу. Модульное программирование предполагает использования разработанных стандартных программ (библиотек стандартных подпрограмм). Для проектирования алгоритма решения сложной задачи, состоящей из нескольких подзадач, можно использовать следующие подходы: Нисходящее проектирование вначале проектируются функции управляющей программы – драйвера; затем более подробно представляют каждую подзадачу и разрабатывают другие модули. При нисходящем проектировании на каждом шаге функционирование модуля описывается с помощью ссылок на последующие, более подробные шаги. Восходящее проектирование вначале проектируют программы низшего уровня, иногда в виде самостоятельных подпрограмм; затем на каждом шаге разрабатываются модули более высокого уровня. Для структурирования данных применяется технологический прием, называемый инкапсуляция. 12 Декомпозиция данных в сложных программах (рис.5): 1. Данные разбиваются на фрагменты одного типа (одной структуры). 2. С фрагментами связываются операции их обработки, формируются подзадачи. 3. Определяются необходимость пересылки данных. 4. Пересечение частей, на которые разбивается задача, должно быть сведено к минимуму. 5. Схема разбиения в дальнейшем может уточняться. 6. Если необходимо уменьшение числа обменов, допускается увеличение степени перекрытия подзадач. 7. Сначала анализируются структуры данных наибольшего размера, либо те, обращение к которым происходит чаще всего. На разных стадиях расчета могут использоваться разные структуры данных, поэтому могут использоваться как статические, так и динамические схемы декомпозиции этих структур. Рис. 5. Декомпозиция данных в сложных программах Контрольные вопросы 1. Чем, на Ваш взгляд, отличается современное понятие (определение) алгоритма от предшествующих определений? Чем можно объяснить историческую трансформацию этого определения? 2. Какие существуют направления исследований в теории алгоритмов? 3. В чем состоит суть практического применения результатов теории алгоритмов? 4. Раскройте смысл формальных свойств алгоритма на примерах. 5. Поясните сопоставление информационной, логической структуры данных с ее способом организации в компьютере. 6. Дайте развернутое определение физической и логической структуры данных на примерах 7. Каковы основные признаки классификации структур данных? 13 8. Какие структуры данных будут востребованы в будущем, а какие станут неэффективными? Можно ли предположить появление новых жүктеу/скачать 3,71 Mb. Достарыңызбен бөлісу:
|