1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 11
Текст из файла (страница 11)
[.8 с фактическими параметрами ! и АИ, используя сначала вызов по наименованию, а затем вызов по ссылке. Будут ли результаты одинаковы? Лроблел!а для исследования 1.22. Можно ли улучшить верхнюю оценку 0(Тз(п)) времени моделирования РАМ машиной Тьюринга, как в теореме [.8? Замечании по литературе РАМ н РАСП получили формальную трактовку у Шепердсона, Стерджнса [1963], Элгота, Робинсона [1964[ и Хартманиса [1971]. В изложении большей части результатов о РАМ и РАСП в этой главе мы следуем работе Кука, Рекхау [1973]. Идея машины Тьюринга принадлежит Тьюрингу [1936]. Более подробное изложение этого понятия можно найти у Минского [196?] и Хопкрофта, Ульмаиа [1969]; это же касается и ответа к упр.
1.3. Изучение временной сложностн ма. шии Тьюринга было начато Хартманисом, Стирнзом [1965[, а емкостной слож. ности — Хартманисом, Льюисом, Стиризом [!965] и Льюисом, Стиризом, Харт. манисом [1965[ '). Начиная с работы Блюма [1967), делалнсь попытии трактовать вычислительную сложность с гораздо более абстрактной точки зрения.
Обзоры можно найти у Хартманиса, Хопкрофта [1971] и Бородина [1973а). Рабин [1972) предложил одно интересное обобщение понятия дерева решений. ') В СССР первые работы, в которых изучались временная и емкостная сложности (для моделей, отличных от рассматриваемых в гл. 1), были выполнены в 1956 г. Г. С.
Цейтнныи (см. С. А. Яновская.Математическая логика и основания математики. Математика в СССР за 40 лет, т. 1, М., Физматгнэ, 1959, 44 — 45) н Трахтенбротом [1956!. — Прим. перез. 2 РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ Эта глава преследует двойную цель. Во.первых, мы вводим некоторые из основных структур данных, которые полезны при разработке эффективных алгоритмов для обширных классов задач.
Во-вторых, описываем некоторую технику "программирования", такую, как рекурсия и динамическое программирование, которая применяется во многих эффективных алгоритмах. В гл. 1 мы рассмотрели основные модели вычислений. Хотя нашей простейшей моделью является РАМ, мы не хотим, как правило, описывать алгоритмы в терминах подобного устройства. Поэтому мы ввели Упрощенный Алгол (разд. 1,8). Но даже этот язык оказывается слишком примитивным, если не ввести в рассмотрение структуры данных, более сложные, чем массивы. В этой главе мы познакомим читателя с такими элементарными структурами данных, как списки и стеки; они часто используются в эффективных алгоритмах.
Мы покажем, что с помощью этих структур можно представлять множества, графы и деревья. Наше изложение по необходимости будет кратким, и читателю, не знакомому с обработкой списков, следует обратиться к одному из более полных источников, указанных в конце данной главы, или уделить особое внимание упражнениям. Мы включили также раздел о рекурсии. Один из важных аспектов рекурсии — облегчить понимание алгоритмов.
Хотя примеры, приводимые в этой главе, слишком просты, чтобы полностью подтвердить это заявление, но в последующих главах рекурсия очень поможет в учете организации информации при точном изложении сравнительно сложных алгоритмов. Рекурсия сама по себе не приводит к более эффективным алгоритмам. Но в сочетании с другой техникой, такой, как балансировка, прием "разделяй и властвуй", алгебраические упрощения, она, как мы увидим, часто дает алгоритмы, одновременно и эффективные, и элегантные. гл з, ехзелноткд эооективнзях длгоеитмоп 2.1.
СТРУКТУРЫ ДАННЫХ: СПИСКИ, ОЧЕРЕДИ И СТЕКИ А!ы считаем, что читатель знаком с элементарными понятиями математики (такимп, как множества и отношения) и основными типами данных — целыми числами, цепочками (словами) и массивами. В этом разделе мы дадим краткий обзор основных операций над списками.
С математической точки зрениясписок — это конечная последо. аательность элементов, взятых из некоторого подходящего множества. Описание алгоритма часто будет включать в себя некоторый список, к которому добавляются и из которого удаляются элементы. В частности мы можем захотеть добавить или удалить элемент где-то в середине списка, По этой причине нам надо разработать структуры данных, позволяющие реализовать списки, в которых разрешается удалять и добавлять новые элементы так, как нам захочется. рассмотрим список Элем 1, Элем 2, Элем 3, Элем 4.
(2.1) Простейшей его реализацией будет структура последовательно связанных компонент, изображенная на рис. 2.1. Каждая кампонента в этой структуре состоит из двух ячеек памяти. Первая ячейка содержит сам элемент '), вторая — указатель следующего элемента. Это можно реализовать в виде двух массивов, которые на рис. 2.2 названы ИМЯ и СЛЕДУЮЩАЯ ').
Если КОМПОНЕНТА— индекс в рассматриваемом массиве, то ИМЯ(КОМПОНЕНТА!— сам элемент, хранящийся там, а СЛЕДУЮЩАЯ! КОМПОНЕНТА!— индекс следующего элемента в списке (если такой элемент существует). Если КОМПОНЕНТА — индекс последнего элемента в этом списке, то СЛЕДУЮЩАЯ!КОМПОНЕНТА)=0. На рис. 2.2 СЛЕДУЮЩАЯ(0! означает постоянный указатель на первую компоненту в списке. Заметим, что порядок элементов в ПЕРВЫ Рнс. 2,1. Спнсок со связями.
') Если. этот элемент сам является сложной структурой, то первая ячейка может содержать указатель ее местоположения. з) другая (н экннналентная) точка зрения такова: имеется «клетка» для ка.кдой компоненты. Каждая «клетка» обладает адресом, который представляет собой номер первого (аозможно, единственного) регистра памяти а группе регнстрон, зарезервированных для этой компоненты. Внутри каждой нлеткн находится одно нлн более «полей». У нас полями служат ИМЯ н СЛЕ»)УЮЩАЯ, а ИМЯ(КОМ.
ПОНЕНТА) н СЛЕ»«УЮЩАЯ(КОМПОНЕНТА! играют роль имен этих полей а клетке с адресом КОМПОНЕНТА. стииктииы данных: списки, очереди и с~еки ИМЯ СЛЕД1ИОХ(ЛЯ Рис. 2.2. Представдеиие списка из четырех зпеиеитов. л1ассиве ИМЯ не совпадает с их порядком в списке. Тем не менее рис. 2.2 дает верное представление списка, изображенного на рис. 2.1, так как массив СЛЕДУЮЩАЯ располагает элементы в том же порядке, в каком они расположены в списке (2.1). Опишем процедуру, вставляющую новую компоненту в список.
В ней предполагается, что СВОБОДНАЯ вЂ” номер незанятой ячейки в массивах ИМЯ и СЛЕДУЮЩАЯ, а ПОЗИЦИЯ вЂ” индекс той компоненты в списке, после которой надлежит вставить ЭЛЕМЕНТ: ргоседнге ВСТАВИТЬ(ЭЛЕМЕНТ, СВОБОДНАЯ, ПОЗИЦИЯ): Ьеи(п ИМЯ(СВОБОДНАЯ1 — ЭЛЕМЕНТ; СЛЕДУЮЩАЯ(СВОБОДНАЯ~ — СЛЕДУЮЩАЯ1ПОЗИЦИЯ1; СЛЕДУЮЩАЯ (ПОЗИЦИЯ1 СВОБОДНАЯ ецио Любой разумный перевод в команды РАЛЬ приведет к тому, что время выполнения процедуры ВСТАВИТЬ не будет зависеть от размера списка. Пример 2.1. Допустим, что мы хотим вставить в список (2.1) элемент Новэлем после Элем 2 и получить список Элем 1, Элем 2, Новэлем, Элем 3, Элем 4.
Если пятая ячейка в каждом массиве иа рис. 2.2 пуста, можно вставить Новэлем после Элем 2 (позиция 3), вызвав ВСТАВИТЬ(Новэлем, 5, 3). В результате выполнения трех операторов в процедуре ВСТАВИТЬ получим: ИМЯ[51: —.Новэлем, гл. к нмтнлно~кл эфмнктиниых ллггн итмон имя следумшяя рнс. 2.З. Список со нстенленным элементом Нонэлем. СЛЕДУЮШАЯ!5)=4 и СЛЕДУЮЩАЯ [3]=5; тем самым создадутся массивы, показанные иа рис. 2.3. С) Для того чтобы удалить компоненту, следующую за компонентой н ячейке 1, можно положить СЛЕДУЮЩАЯ! П =СЛЕДУЮШАЯ !СЛЕДУЮШАЯ(т')).
При желании индекс удаленной компоненты можно поместить в список незанятых ячеек памяти. Часто в один и тот же массив вкладываются несколько списков Обычно один из этих списков состоит из незанятых ячеек; мы будем называть его свободным списком. Для добавления элемента к списку А можно так изменить процедуру ВСТАВИТЬ, чтобы незанятая ячейка получалась путем удаления первой ячейки в свободном списке. При удалении элемента из списка А соответствующая ячей.
ка возвращается в свободный список для будущего употребления. Этот метод организации памяти — не единственный прием, которым обычно пользуются, но он приведен здесь для того, чтобы показать, что операции добавления и удаления элементов списка можно выполнить за ограниченное число шагов, если определено местоположение элемента, который мы хотим добавить или удалить Еще две основные операции над списками — конкатенация (сцепление) двух списков, в результате которой образуется единственный список, и обратная к ней операция расцепления списка, стоящего после некоторого элемента, результатом которой будут двп списка.
Конкатенацию можно выполнить за ограниченное (постоянной величиной) число шагов, включив в представление списка еще один указатель. Этот указатель дает индекс последней компоненты списка и тем самым позволяет обойтись без просмотра всего списка для определения его последнего элемента. Расцепление мож- ас стииктииы данных~ списки очьииди н с|сии имя ВЕРШИНД- 2 Рис. 2.4. Реализации стека, но сделать за ограниченное (постоянной величиной) время, если известен индекс компоненты, непосредственно предшествующей месту расцепления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
