Учебник_Информатика. Стандарт третьего поколениян. В. Макарова, В. Б. Волков

• Название: Стандарт третьего поколениян. В. Макарова, В. Б. Волков
• Анкор: Учебник_Информатика.pdf
• Дата: 26.04.2017
• Размер: 14.49 Mb.
• Имя файла: Учебник_Информатика.pdf
• Тип: Документы; #5919
• страница: 38 из 48

1 В определенных конкретных случаях может потребоваться представления и в других формах,
также пригодных к обработке на компьютере: в виде матриц инцидентности или матриц смежно­
сти, а также других структур для представления «веса» и «цвета» связей, пометок вершин и т. д.

422
Глава 14. Основы теории алгоритмов
Матрица примыканий ConMat графа G = ( V,E) с числом вершин | V| = N запи­
сывается в виде двухмерного массива размером N х
ЛГ. В каждой ячейке [у] этого массива записано значение 0 за исключением лишь тех случаев, когда из вершины
Vi в вершину Vj ведет ребро, и тогда в ячейке записано значение 1:
I
I, если{^г;;}е
Е
для всех
i
и
j
от 1 до
N.
О,
если\г){о^ё Е
На рис. 14.28 изображены матрицы примыканий для графа и орграфа, изобра­
женных на рис. 14.26 и 14.27.
1 2 3 4 5 1 2 3 4 5 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 2 0 0 0 1 0 1 1 0 0 1 3 0 1 0 0 0 0 1 0 0 1 4 0 0 1 0 0
.0 0 1 1
0
5 .0 1 0 1 0
Рис. 14.28. Матрицы примыканий графа и орграфа
Список примыканий ConList графа G = (V, Е) с числом вершин | V| = АТ записыва­
ется в виде одномерного массива длины N, каждый элемент которого представляет собой ссылку на список. Такой список приписан каждой вершине графа и содержит по одному элементу на каждую вершину графа, соседнюю с данной.
На рис. 14.29 изображен список примыканий для орграфа, изображенного на рис. 14.27. На этом рисунке буквами L VN обозначены вершины графа, а буквами
vN — те вершины, к которым направлены выходящие из данной вершины ребра.
L V\. v2, v3\
Ly2- Vfo
Lv3* v2\
Lva
•
Ly5* v2>
V4,
Рис. 14.29. Список примыканий для орграфа
При работе с графами часто приходится выполнять некоторое действие по од­
ному разу с каждой из вершин графа, например, когда некоторую порцию инфор­
мации следует передать каждому из компьютеров в сети. При этом нерационально посещать какой-либо компьютер дважды. Аналогичная ситуация возникает, если нужно собирать, а не распространять информацию.
Подобный обход можно совершать двумя способами. При обходе в глубину проход по выбранному пути осуществляется настолько глубоко, насколько это возможно, а при обходе по уровням происходит равномерное движение вдоль всех возможных направлений.

14.4. Представление и обработка данных разного типа
423
Обход в глубину
При обходе в глубину происходит посещение первого узла, а затем передвиже­
ние вдоль ребер графа, пока не будет достигнут тупик. Узел неориентированного графа является тупиком, если уже посещены все примыкающие к нему узлы.
В ориентированном графе тупиком также оказывается узел, из которого нет вы­
ходящих ребер.
После попадания в тупик следует вернуться назад вдоль пройденного пути, пока не будет обнаружена вершина, у которой есть еще не посещенный сосед, а затем двигаться в новом направлении. Процесс оказывается завершенным после того, как произошел возврат в отправную точку, а все примыкающие к ней вершины уже посещены (рис. 14.30).
При реализации алгоритма обхода в глубину используется рекурсивный вызов процедуры.
Входные данные:
G — граф v — текущий раздел
Посетить текущий узел и выполнить необходимые действия над хранящимися в нем данными
Пометить текущий узел как посещенный
(например, занести его идентификатор в массив посещенных узлов)
Q Процедура DepthFirstTraversal(G, v )^ )--
Nv — число ребер, выходящих из узла v
/ — переменная цикла
-
Проход по каждому ребру х = узел на /-м ребре, исходящим из узла v
/ = / + 1
Если узел помечен как посещенный, его не посещаем
Г
Для каждого непосещенного узла

|_ рекурсивно вызываем
DepthFirstTraversal
Возврат из процедуры
Рис. 14.30. Рекурсивная процедура обхода графа в глубину
Обход по уровням
При обходе графа по уровням после посещения первого узла происходит об­
ход всех соседних с ним вершин. При втором проходе посещаются все вершины

424
Глава 14. Основы теории алгоритмов на расстоянии «двух ребер» от начальной. При каждом новом проходе обходятся вершины, расстояние от которых до начальной на единицу больше предыдущего.
В графе могут быть циклы, поэтому не исключено, что одну и ту же вершину мож­
но соединить с начальной двумя различными путями. При обходе этой вершины впервые проходится самый короткий до нее путь, и посещать ее второй раз нет необходимости. Поэтому, чтобы предупредить повторное посещение, приходится либо вести список посещенных вершин, либо сопоставить каждой вершине флажок, указывающий, посещена она или нет.
Входные данные:
G — граф v — текущий раздел
Посетить текущий раздел и выполнить необходимые действия над хранящимися в нем данными
Пометить текущий узел как посещенный
(например, занести его идентификатор в массив посещенных узлов)
-
Поместить текущий узел в конец очереди
Извлечь из начала очереди узел х
-
Проход по каждому ребру
) посещаем
Для каждого непосещенного узла: посещение и обработка; пометка как посещенного; помещение в конец очереди
Рис. 14.31. Обход графа по уровням

14.5. Алгоритмы сортировки и поиска
425
Алгоритм обхода вершин графа по уровням приведен на рис. 14.31. В отличие от обхода в глубину, этот алгоритм реализован с использованием очереди. Очередь — это специальный программный механизм, предназначенный для упорядоченного хранения и извлечения данных. При помощи процедуры Enqueue заданный объект помещается в конец очереди, а процедура Dequeue извлекает из начала очереди размещенный там объект. Таким образом, пока идет обработка данных в узлах те­
кущего уровня, узлы следующего уровня, связанные ребрами с текущими узлами, помещаются в очередь.
При анализе графов и применении их для решения различных информационных задач используют стандартные алгоритмы поиска минимального пути, поиска пути
с минимальным (максимальным) весом ребер, анализа компонентов двусвязности.
14.5. Алгоритмы сортировки и поиска
14.5.1. Сортировка
Сортировка (то есть упорядочение по возрастанию или убыванию значений в списках, массивах, записях и других последовательностях элементов) является одной из наиболее важных алгоритмических задач, непосредственно связанных с проблемами эффективного управления, поиска и извлечения информации.
Известны следующие распространенные методы сортировки:
□ сортировка вставками;
□ пузырьковая сортировка;
□ сортировка Шелла;
□ корневая сортировка;
□ пирамидальная сортировка;
□ сортировка слиянием;
□ быстрая сортировка.
Сортировка вставками
Основная идея сортировки вставками состоит в том, что при добавлении ново­
го элемента в уже отсортированный список его сразу вставляют в нужное место вместо того, чтобы вставлять его в произвольное место, а затем заново сортировать весь список. При сортировке вставками первый элемент любого списка считается отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одно­
элементного списка, содержащего первый элемент. После этого можно вставить третий элемент исходного списка в отсортированный двухэлементный список. Этот процесс повторяется до тех пор, пока все элементы исходного списка не окажутся в расширяющейся отсортированной части списка.
Пузырьковая сортировка
Основной принцип пузырьковой сортировки состоит в выталкивании меньших значений на вершину списка, в то время как большие значения опускаются вниз.

426
Глава 14. Основы теории алгоритмов
Алгоритм пузырьковой сортировки приведен на рис. 14.32. У пузырьковой со­
ртировки есть много различных вариантов. В алгоритме пузырьковой сортировки совершается несколько проходов по списку. При каждом проходе происходит срав­
нение соседних элементов. Если порядок соседних элементов неправильный, то они меняются местами. Каждый проход начинается с начала списка. Сперва сравнива­
ются первый и второй элементы, затем — второй и третий, потом — третий и чет­
вертый, и т. д.; элементы с неправильным порядком в паре переставляются. При обнаружении на первом проходе наибольшего элемента списка он переставляется со всеми последующими элементами, пока не дойдет до конца списка. Поэтому при втором проходе нет необходимости производить сравнение с последним элементом.
Рис. 14.32. Алгоритм пузырьковой сортировки
При втором проходе второй по величине элемент списка опускается во вторую’ позицию с конца. При продолжении процесса на каждом проходе по крайней мере

14.5. Алгоритмы сортировки и поиска
427
одно из следующих по величине значений встает на свое место. При этом меньшие значения тоже собираются наверху. Если при каком-то проходе не происходит ни одной перестановки элементов, это означает, что все они стоят в нужном порядке, и исполнение алгоритма можно прекратить. Стоит заметить, что при каждом про­
ходе ближе к своему месту продвигается сразу несколько элементов, хотя гаран­
тированно занимает окончательное положение лишь один.
Сортировка Шелла
Суть сортировки Шелла состоит в том, что весь список рассматривается как совокупность перемешанных подсписков. На первом шаге эти подсписки представ­
ляют собой просто пары элементов. На втором шаге в каждой группе оказывается по четыре элемента. При повторении процесса количество элементов в каждом подсписке увеличивается, а количество подсписков, соответственно, падает.
Корневая сортировка
При корневой сортировке упорядочивание списка происходит без непосред­
ственного сравнения ключевых значений между собой. При этом создается набор
«стопок», а элементы распределяются по стопкам в зависимости от значений клю­
чей. Собрав значения обратно и повторив всю процедуру для последовательных частей ключа, можно получить отсортированный список. Чтобы такая процедура работала, распределение по стопкам и последующую сборку следует выполнять очень аккуратно.
Пирамидальная сортировка
В основе пирамидальной сортировки лежит специальный тип бинарного дерева, называемый пирамидой; значение корня в любом поддереве такого дерева больше, чем значение каждого из его потомков. Непосредственные потомки каждого узла не упорядочены, поэтому иногда левый непосредственный потомок оказывается больше правого, а иногда наоборот. Пирамида представляет собой полное дерево, в котором заполнение нового уровня начинается только после того, как преды­
дущий уровень оказывается заполненным целиком, а все узлы на одном уровне заполняются слева направо.
Сортировка начинается с построения пирамиды. При этом максимальный элемент списка оказывается в вершине дерева: ведь потомки вершины обяза­
тельно должны быть меньше. Затем корень записывается последним элементом списка, а пирамида с удаленным максимальным элементом переформировывает­
ся. В результате в корне оказывается второй по величине элемент, он копируется в список, и процедура повторяется, пока все элементы не окажутся возвращенными в список.
Сортировка слиянием
Сортировка слиянием — один из распространенных алгоритмов рекурсивной сортировки. В ее основе лежит замечание, согласно которому слияние двух от­

428
Глава 14. Основы теории алгоритмов сортированных списков выполняется быстро. Список из одного элемента уже отсортирован, поэтому при сортировке слиянием список разбивается на одноэле­
ментные куски, которые затем постепенно сливаются. Поэтому вся деятельность заключается в слиянии двух списков.
Быстрая сортировка
Быстрая сортировка — один из наиболее популярных алгоритмов рекурсивной сортировки. При быстрой сортировке после выбора в списке элемента список с его помощью делится на две части. В первую часть попадают все элементы, меньшие выбранного, во вторую — большие выбранного. В среднем такая сортировка эффек­
тивна, однако в наихудшем случае ее эффективность такая же, как у сортировки вставками и у пузырьковой сортировки.
При быстрой сортировке в списке выбирается элемент, называемый осевым, а затем список переупорядочивается таким образом, что все элементы, меньшие осевого, оказываются перед ним, а большие элементы — за ним. В каждой из ча­
стей списка элементы не упорядочиваются. Если п — окончательное положение осевого элемента, то нам известно лишь, что все значения в позициях с первой по
п - 1 меньше осевого, а значения с номерами от п + 1 до N — больше осевого. Далее алгоритм вызывается рекурсивно на каждой из двух частей.
14.5.2. Поиск
Под алгоритмами поиска понимается процесс просмотра списка в поисках некоторого конкретного элемента, называемого целевым. При последовательном поиске всегда предполагается, что список не отсортирован, поскольку некоторые алгоритмы на отсортированных списках показывают лучшую производительность.
Обычно поиск производится не просто для проверки того, что нужный элемент в списке имеется, а и для того, чтобы получить данные, относящиеся к этому зна­
чению ключа. Например, ключевое значение может быть номером сотрудника, порядковым номером или любым другим уникальным идентификатором. После того как нужный ключ найден, программа может, например, частично изменить связанные с ним данные или просто вывести всю запись. Во всяком случае, перед алгоритмом поиска стоит важная задача определения местонахождения ключа.
Поэтому алгоритмы поиска возвращают индекс записи, содержащей нужный ключ.
Если ключевое значение не найдено, то алгоритм поиска обычно возвращает зна­
чение индекса, превышающее верхнюю границу массива. Положим, что элементы списка имеют номера от 1 до N. Это позволит возвращать 0 в случае, если целевой элемент отсутствует в списке. Для простоты предполагаем, что ключевые значения не повторяются.
Последовательный поиск
В алгоритме последовательного поиска последовательно просматривается по одному элементу списка, начиная с первого, до тех пор, пока не будет найден це­
левой элемент. Очевидно, что чем дальше в списке находится конкретное значение

Вопросы для самопроверки
429
ключа, тем больше времени уйдет на его поиск. Это следует помнить при анализе алгоритма последовательного поиска.
Полный алгоритм последовательного поиска показан на рис. 14.33.
Рис. 14.33. Алгоритм последовательного поиска
Двоичный поиск
При сравнении целевого значения со средним элементом отсортированного списка возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях можно отбросить половину списка. Когда целевое значение меньше среднего элемента, известно, что если оно имеется в списке, то находится перед этим средним элементом. Ког­
да же оно больше среднего элемента, известно, что если оно имеется в списке, то находится после этого среднего элемента. Этой информации достаточно, чтобы стало возможно одним сравнением отбросить половину списка. При повторении этой процедуры можно отбросить половину оставшейся части списка. Очевидно, что такой алгоритм будет работать только на предварительно отсортированном списке.
Вопросы для самопроверки
1. Откуда произошел термин «алгоритм»?
2. Чем численный алгоритм отличается от логического?
3. Из каких разделов состоит современная теория алгоритмов?
4. Дайте определение алгоритма по Маркову.
5. Дайте определение алгоритма по Колмогорову.

430
Глава 14. Основы теории алгоритмов
6. Каким требованиям должен отвечать алгоритм?
7. Что собой представляет машина Поста?
8. Что собой представляет машина Тьюринга?
9. Какие способы записи алгоритмов вам известны?
10. Каковы недостатки словесного способа записи алгоритма?
11. Каковы достоинства и недостатки представления алгоритма в виде блок-схемы?
12. Приведите пример простейшего алгоритма, представленного при помощи диа­
граммы Нэсси—Шнейдермана.
13. Что такое «псевдокоды»?
14. На какие группы можно подразделить языки программирования высокого уровня?
15. Какие базовые алгоритмические конструкции вам известны?
16. Что такое «линейный алгоритм»?
17. Что такое «разветвляющийся алгоритм»? Чем обуславливается выбор пути при ветвлении?
18. Что такое «циклический алгоритм»? Чем отличается цикл с предусловием от цикла с постусловием?
19. Дайте определение данным. Чем данные отличаются от переменных и кон­
стант?
20. Какие базовые типы данных вам известны?
21. Что такое «массив»?
22. Что такое «запись»?
23. Что такое «связный список»? «Односвязньш список»? «Двусвязный список»?
24. Опишите в словесной форме алгоритм удаления элемента односвязного списка.
25. Опишите в форме псевдокода алгоритм удаления элемента двусвязного списка.
26. Что такое «деревья»?
27. Что такое «корневое дерево»? Что такое «корень дерева»?
28. Что такое «бинарное дерево»?
29. Что такое «граф»?
30. Чем различаются ориентированный и не ориентированный графы?
31. В решении каких задач применяются графы?
32. Какие алгоритмы сортировки вам известны? Опишите особенности каждого из них.
33. Какие алгоритмы поиска вам известны?

Литература
431
Литература
1. Голицина О. Л.у Попов И. И. Основы алгоритмизации и программирования. М.:
Форум, 2008.
2. Давыдов В. Г. Программирование и основы алгоритмизации. М.: Высшая школа,
2003.
3. Кузюрин Н. Н., Фомин С. А . Эффективные алгоритмы и сложность вычислений.
Электронное издание, http://discopal.ispras.ru/ru.book-advanced-algorithms.htm
4. Мозговой М. В. Классика программирования: алгоритмы, языки, автоматы, ком­
пиляторы. Практический подход. СПб.: Наука и техника, 2006.

Г лава 15
Классификация и тенденции развития программного обеспечения
15.1. Классификация программного обеспечения по степени взаимодействия с аппаратной частью компьютера
15.2. Классификация программного обеспечения по виду лицензирования
15.3. Прочие классификации
15.4. Промежуточное программное обеспечение
15.5. Программное обеспечение процесса разработки программного обе­
спечения
15.6. Области применения прикладного программного обеспечения
15.7. Перспективы развития программного обеспечения
По подсчетам специалистов, ежедневно в мире появляется до 200 новых про­
граммных продуктов, и темпы развития программного обеспечения только увели­
чиваются. Наверное, можно ожидать, что в не столь отдаленном будущем в ком­
пьютерной науке появится новый отдел, этимология и систематика компьютерных программ, в котором будут рассматриваться семейства, виды и классы программ­
ного обеспечения и обсуждаться причины исчезновения и появления тех или иных видов программного обеспечения (ПО), какова перспектива у видов ныне существующих. Такая наука более тщательно опишет общие признаки и различия программных продуктов. Многие из важных классов программного обеспечения, описание которых здесь сделано несколько поверхностно, будут раскрыты глубже в следующих главах книги.

15.1. Классификация программного обеспечения по степени взаимодействия
433 15.1. Классификация программного обеспечения по степени взаимодействия с аппаратной частью компьютера
Бурное развитие компьютерной техники во всем мире привело к столь же бурному развитию программных продуктов. Область программного обеспечения пережила эпоху «первичной свободы и хаоса», когда программ было крайне мало и они вообще не рассматривались как продукт, который можно было продавать, а поставлялись вместе с вычислительной техникой. Мало было и программистов, а практически рядом с каждым компьютером работало несколько человек, которые
«изобретали» собственные программы.
По мере распространения компьютеров и все большей зависимости работы этой техники от качества программного обеспечения, установленного на ней, програм­
мы начали приобретать собственные «вес» и стоимость. Чем больше появлялось компьютеров, тем больше становилось потенциальных покупателей программ.
Рынок мгновенно отреагировал на это созданием коммерческого программного обеспечения. Область торговли компьютерами разделилась на две большие части: по продаже «железа» (hardware — аппаратное обеспечение) и «софта» (software — программное обеспечение).
Несомненным достоинством коммерческого подхода на данном этапе развития программного обеспечения было резкое повышение качества и унификация про­
граммного обеспечения. Недавний хаос превратился в порядок, быстро приобретя хорошо узнаваемые имена производителей программного обеспечения: Microsoft,
Oracle, Sun, Borland. Программные продукты этих компаний пользуются большим спросом, а в отдельных областях полностью заняли рынок.
По мере все более глубокого проникновения компьютеров во все сферы жиз­
ни, в процессе все возрастающей мощи суперкомпьютеров и все уменьшающихся размеров микро-, супермикро- и встраиваемых ЭВМ, количество и разнообразие программных продуктов с каждым годом растет в геометрической прогрессии. Если совсем недавно программное обеспечение для первых компьютеров можно было разделять только по их маркам, то достаточно быстро возникло разделение на си­
стемное и пользовательское (прикладное) программное обеспечение. Со временем между этими двумя большими классами возник третий, промежуточный, слой, ко­
торый так и назвали — промежуточное программное обеспечение. Необходимость создания все новых программных продуктов привело к появлению еще одного класса программного обеспечения — систем программирования.
Так было заложено первое основание для классификации по степени взаимо­
действия с аппаратурой (физическим оборудованием) компьютера.
Если представить, что программное обеспечение слой за слоем накладывается на аппаратную часть компьютера, давая возможность пользователю взаимодей­
ствовать с «железом», то схематично эту структуру можно представить на рис. 15.1.
Прикладное программное обеспечение не взаимодействует напрямую с аппа­
ратным обеспечением компьютера. В качестве примера прикладного программ­
ного обеспечения можно привести текстовый процессор, графический редактор,

434
Глава 15. Классификация и тенденции развития программного обеспечения электронную таблицу, проигрыватель музыкальных файлов, программу для расчета надежности несущих конструкций, программу бухгалтерского учета и прочие про­
граммы, которые выполняют пользовательские задания.
J | u
Промежуточное ПО
Мвй
щ
Опз;лч^ы^ с^стемЛ* утшшы
^
ll г
Рис. 15.1. Классификация программного обеспечения по степени взаимодействия с аппаратной частью компьютера
—
/ г „
_
----------
- рт щ т р ш т ш Щ
выполнения пользовательских заданий и и У в ^щ Ш й р у'4" ^
Ф^^Щф^шьстй интерфейс.
,
\ '
'
Системное программное обеспечение составляют операционная система с на­
бором инструментов (утилит) администрирования и настройки, а также базовая система ввода-вывода (Basic Input O utput System, BIOS).