АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ Лекции для студентов-заочников 2 курса, специальность 230700.62 (Прикладная информатика) - презентация

1 АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ Лекции для студентов-заочников 2 курса, специальность (Прикладная информатика)

2 Содержание лекции 1 Свойства алгоритма Базовые канонические структуры алгоритмов Анализ функции сложности по программе Теоретическая и практическая функции сложности

3 Свойства алгоритма АЛГОРИТМОМ называется система формальных правил, чётко и однозначно определяющая процесс решения поставленной задачи в виде конечной последовательности действий или операций. Свойства, которыми должен обладать алгоритм : Конечность ( финитность ) алгоритма Определённость ( детерминированность) Результативность Массовость Эффективность.

4 ПОЛНОЕ ПОСТРОЕНИЕ АЛГОРИТМА Полное построение алгоритма предусматривает последовательное выполнение следующих этапов : Постановка задачи. Построение модели. Разработка алгоритма. Проверка правильности алгоритма. Реализация, т.е. программирование алгоритма. Анализ алгоритма и его сложности. Проверка (отладка) программы. Составление документации.

5 БАЗОВЫЕ КАНОНИЧЕСКИЕ СТРУКТУРЫ АЛГОРИТМА Алгоритмы подразделяются на : Механические Вероятностные (стохастические) Эвристические Для реализации алгоритмов на ПЭВМ используется алгоритмический язык. Любую программу можно написать, используя комбинацию трёх базовых структур : Следования, или последовательности операторов Ветвления, или условного оператора Повторения, или оператора цикла Программа, составленная из канонических структур, называется регулярной.

6 ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ФУНКЦИИ СЛОЖНОСТИ АЛГОРИТМА Для оценки эффективности алгоритма используется функция сложности алгоритма, которая обозначается заглавной буквой О, в круглых скобках записывается аргумент. Она определяет количество сравнений, перестановок, а также временные и ресурсные затраты на реализацию алгоритма. Поскольку для функции сложности алгоритма большее значение имеет не столько вид функции, сколько порядок её роста, то функцию f(n) определяют как О(g(n)), если предел отношения f(n)/g(n) стремится к константе, отличной от нуля, при n стремящемся к бесконечности, где f(n) и g(n) экспериментальная и теоретическая функции сложности. Например, для f(n) =2n 5 + 6n имеем f(n) = O(n 5 ).

7 Содержание лекции 2 Основные понятия структур данных Классификация структур данных Методы сортировки Метод поиска

8 Основные понятия структур данных Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. Различают следующие виды структур данных : Простые структуры данных, которые не могут быть расчленены на составные части Интегрированные структуры данных, составными частями которых являются другие структуры данных простые или, в свою очередь, интегрированные.

9 Классификация структур данных Важный признак структуры данных характер упорядоченности её элементов. По этому признаку структуры можно делить на Линейные Прямоугольные Строчные Списковые Нелинейные Древовидные Графовые Сплетения Примеры прямоугольных структур это матрицы, вектора, множества элементов. Строчные структуры одномерные, динамически изменяемые структуры данных, различающиеся способом включения и исключения элементов. Сюда относятся стеки, очереди, деки. Нелинейные структуры данных это те структуры у которых связи между элементами зависят от выполнения определённого условия. Примеры нелинейных структур деревья, графы, многосвязные списки.

10 Методы сортировки Упорядочение элементов множества в возрастающем или убывающем порядке называется сортировкой. Рассмотрим алгоритмы сортировки в линейных структурах : Выборка Вставка Обмен Сортировка выбором состоит в том, что сначала в неупорядоченном списке выбирается и отделяется от остальных наименьший элемент, то же самое происходит с оставшимся списком и т. д. Очевидно, что выбранные элементы образуют упорядоченный список. Сортировка вставкой. В этом методе из неупорядоченной последовательности элементов выбирается поочерёдно каждый элемент, сравнивается с предыдущим, уже упорядоченным, и помещается на соответствующее место. При сортировке обменом элементы списка последовательно сравниваются между собой и меняются местами в том случае, если предшествующий элемент больше последующего. Процесс сортировки продолжается до тех пор, пока в ходе сортировки при сравнении элементов не будет сделано ни одной перестановки.

11 Метод поиска Элемент множества называется ключом и обозначается латинской буквой K i c индексом, указывающим номер элемента. Задача поиска. Пусть задано множество ключей, в котором нужно отыскать заданный ключ. Рассмотрим следующие алгоритмы поиска : Последовательный Бинарный В последовательном поиске исходное множество не упорядочено и отыскиваемый ключ последовательно сравнивается со всеми элементами множества. При этом поиск заканчивается досрочно, если ключ найден. В бинарном поиске исходящее множество должно быть упорядочено по возрастанию. Отыскиваемый ключ сравнивается с центральным элементом множества, если он меньше центрального, то поиск продолжается в левом подмножестве, в противном случае в правом.