Тема 7. Некоторые алгоритмы обработки данных 58

Цели и задачи изучения темы 58

7.1.Алгоритмы поиска 58

7.1.1.Поиск элемента в неупорядоченном массиве 59

7.1.2.Поиск элемента в упорядоченном массиве. 59

7.1.3.Фонетический поиск 60

7.2.Алгоритмы сортировки 61

7.2.1.Сортировка методом пузырька. 62

7.2.2.Сортировка вставками 63

7.2.3.Сортировка выбором 64

7.2.4.Пирамидальная сортировка 65

7.2.5.Быстрая сортировка 69

7.2.6.Сортировка слиянием 71

7.3.Поиск на графах 73

7.3.1.Поиск в глубину 73

7.3.2.Поиск в ширину 75

7.4.Топологическая сортировка графа 77

7.5.Сетевое планирование 79

7.5.1.Алгоритм расчета наиболее ранних сроков наступления событий 80

7.5.2.Алгоритм расчета наиболее поздних сроков наступления событий 81

7.5.3.Алгоритм расчета резервов времени 84

Вопросы для повторения 84

Резюме по теме 85

Литература 85

Рекомендуемая основная литература 85

Рекомендуемая дополнительная литература 85

Тема 1. Алгоритмы и программы Цели и задачи изучения темы

В данной теме рассматриваются понятие алгоритма, программы, способы записи алгоритмов, критерии качества программ, типы языков программирования и принципы структурного программирования.

1.1.Понятие алгоритма. Понятие программы. Способы записи алгоритмов.

Понятие алгоритма - одно из основных понятий программирования и математики. Алгоритм - это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу.

Алгоритм записывается на формальном языке, исключающем неоднозначность толкования. Исполнитель - это человек, компьютер, автоматическое устройство и т.п. Он должен уметь выполнять все команды, составляющие алгоритм.

Алгоритмы можно описывать на естественном языке. Но при использовании некоторого формального языка исчезает неоднозначность, появляются краткость и ясность изложения.

К формальным языкам относятся все языки программирования. Язык программирования это формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и действия, которые выполнит вычислительное устройство (исполнитель) под ее управлением.

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

Другими словами алгоритм - это метод или схема решения задачи, а программа - это конкретная реализация алгоритма, которая может быть выполнена на компьютере. Алгоритм, в свою очередь, является реализацией идеи решения. Это можно проиллюстрировать следующей схемой:

Идея решения → Алгоритм → Программа.

Стрелка означает переход к следующему этапу решения задачи с повышением уровня детализации.

Большинство языков программирования имеют общие черты. Поэтому не всегда целесообразно пользоваться каким-либо конкретным языком программирования и загромождать изложение несущественными деталями. Здесь мы будем использовать язык блок-схем.