AOP_Tom1 (1021736), страница 133
Текст из файла (страница 133)
Однако для углубленного понимания полезно рассмотреть предмет с более абстрактной точки зрения, отделив идеи, которые могут быть изучены самостоятельно. Был разработан ряд достойных внимания подходов такого типа; особо могут быть рекомендованы для ознакомления следующие ранние работы: О. Меа!у, "АпосЬег 1оо1г аг баса", Ргос. АРЛРБ Ра)1 Ло1пг Сошригег Сопб 31 (1967), 525-534: Л. Еаг1еу, "Тошап1 ап шн)егэгапгйп8 ог" баса эсгиссигеэ", САСМ 14 (1971), 617 — 627; С.
А. Н. Ноаге, "ЫоСеэ оп <1ага эсгисГиг1пб", ш Ясгисгпгег1 Ргойгашш1пя Ъу О.-Л. 1УаЬ1, Е. %. Вц1сзсга, апб С. А. В.. Ноете (Асас1епнс Ргеэа, 1972), 83 — 174; НоЬегС Ъг'. Еп81еэ, "А гпгоНа1 оп с1ага-Ьаве огйап1забоп", Апанаса Неиек ш АиГошас1с Ргодгагптшй 7 (1972), 3 — 63. Материал этой главы не охватывает предмет информационных структур во всей полноте. Как минимум не рассматривались три важных вопроса.
а) Часто необходимо найти узел (или множество узлов, обладающих некоторым значением) в таблице. Такая операция нередко оказывает серьезное влияние на структуру таблицы. Этот вопрос детально описывается в главе 6. Ъ) В основном, нами рассматривалось внутреннее представление структур в компьютере; однако зто всего лишь одна часть темы, поскольку структуры должны быть также представлены как внешние входные или выходные данные. В простых случаях с внешними структурами можно работать, по сути, при помощи тех же технологий, которые были здесь рассмотрены. Однако очень важен процесс преобразования строк символов в более сложные структуры и обратно. Такие процессы анализируются в главах 9 и 10.
с) В основном, в главе обсуждалось представление структур данных в высокоскоростной памяти с произвольным доступом. При использовании медленных устройств, таких как диски и ленты, все структурные проблемы обостряются и все более важными становятся эффективные алгоритмы и эффективные схемы представления данных. Узлы, связанные один с другим, в этих случаях должны располагаться в близких областях памяти. Обычно эти проблемы трудно обсуждать в общем виде, так как они сильно зависят от характеристик конкретных машин. Простейшие примеры из этой главы должны помочь читателю подготовиться и решению сложных проблем, возникающих в связи с использованием менее идеальных устройств хранения информации. Некоторые из этих проблем детально обсуждаются в главах 5 и 6.
В чем же заключается смысл рассматриваемых в этой главе тему Видимо, наиболее важный вывод, который можно сделать, изучив предложенный материал, состоит в том, что рассмотренные идеи не ограничиваются компьютерным программированием; в целом, они вполне применимы в повседневной жизни. Коллекция узлов, содержащих поля, одни из которых указывают на другие узлы, представляется очень хорошей абстрактной моделью структурных отношений любого вида.
Такая модель показывает. каким образом можно построить сложные структуры из простых, а соответствующие алгоритмы для работы со структурами могут быть разработаны естественным образом. Поэтому представляется разумным продолжить разработку теории о связанных множествах узлов по сравнению с тем, что известно в настоящее время. Возможно, наиболее очевидный путь создания такой теории состоит в определении нового вида абстрактной машины или "автомата" для работы со связанными структурами. Например, подобное устройвтво может быть неформально определено следующим образом.
Имеются числа lс, 1, г и а, такие, что автомат обрабатывает узлы, содержащие А полей связи и т информационных полей. Он имеет 1 регистров связи и а информационных регистров. обеспечивающих управление выполняемыми процессами. Информационные поля и регистры могут содержать любые символы нч некоторого заданного набора информационных символов. Каждое из полей связи и регистров связи содержит либо Л, либо указатель на узел. Машина может (~) создавать новые узлы (помещая связи с узлом в регистр), (й) проверить равенство символов или значений связей и (ш) переносить информационные символы или значения связей между регистрами и узлами.
Непосредственно доступны только узлы, на которые указывают регистры связей, Соответствующие ограничения на поведение машины делают ее эквивалентом ряда других видов автоматов. Аналогичная модель вычислений была предложена А. Н. Колмогоровым в 1952 году. Его машина, по сути, работала с графом С, имеющим специально созданную стартовую вершину ее. Действия на каждом шаге зависят только от подграфа Гу', состоящего из всех вершин на расстоянии ( и от пе в О, и заключаются в замещении С' в 0 другим графом С" = 7(С'), где С" включает ее и вершины на расстоянии, в точности равном и от пэ, и, возможно, другие (вновь сеаданные) вершины. Остаток графа С является неизменным. Здесь и — фиксированное число, определяющееся отдельно для каждого конкретного алгоритма, которое может быть произвольно большим.
Каждой вершине назначается символ из некоторого конечного алфавита с тем ограничением, что у вершины не может быть двух соседних вершин с одинаковыми символами. (См. А. Н. Колмогоров, Успехи мат. наук 8,4 (1953), 175 — 176; Колмогоров и Успенский, Успехи мат. наук 13.4 (1958), 3 — 28; Атег. МаГЬ. 5ос. Тгапз1аг1опз, зепез 2, 29 (1963), 217 — 245.) Связывающие автоматы могут легко моделировать машины графов, используя ограниченное сверху количество шагов на один шаг работы графа. Напротив, маловероятно, чтобы машины графов могли моделировать произвольные связывающие автоматы без неограниченного увеличения времени работы, если не перейти от неориентированных графов к ориентированным, чтобы работать с вершинами с ограниченной степенью.
И, конечно, связывающая модель гораздо ближе к операциям, доступным программисту на реальной машине, в отличие от модели с использованием графа. Самыми интересными проблемами, которые предстоит решить для такого рода устройств, являются определение скорости решения поставленных ими задач, т. е. подсчет количества узлов, требуемых для решения той или иной задачи (например, для трансляции какого-либо формального языка). В то время, когда автор приступил к работе над настоящей главой, были получены интересные результаты такого рода (отметим работы Ю. Хартманиса (3. Наггшашв) и Р. Э. Стирнса (Н.
Е, 81еагпз)), но только для специальных классов машин Тьюринга с множеством лент и головок чтения/записи. Модель машины Тьюринга сравнительно нереальна, а потому полученные результаты имеют мало общего с решением практических задач. Следует признать, что при стремлении количества созданных связывающим автоматом узлов и к бесконечности неизвестно, как построить такое устройство фи- ЗВЧТСИИ, $6$епольну Л36ЛВТТНЗЬИО, ЧТТ3бм ОИВРВЗЕТП ЬЗВИЗНИМ ВЬ33ИТЧПВЛНСЬ ЗВ ОП)36 Н ТО лге Времи петависимо ог рвтмерв н, Еслй сеиль3наине нредспгвлеио с ислольтОВВипем ВДР63$$В В МЕНМНПМЗЙ НЗДЕПТИ, наобхолпмо ОИРедеднть ТРВН3нгу ден НОМечеетев уллов, посиоеьиу нолп глпвеЙ имевгт фписпргмлипмй релмер, )3$ноголепточпаи ммнипа ')'Ь$ОРЛИГВ ОЗМТОМУ ЩПЗЛСТВВЛПОТ СОЙОЙ 63В366 РежлнстпчнУ36 мОДЕль при стремлеипи В и б33смигечиости.
Пуидоммлпегси тпиме Обоснованной уверенность в том, что описанные вмнге свимеввиниие автомвтм приведут и отгдлинн3 болгм нриемле ИОЙ тн$рнн сммииости Вегоритмов, чем мвпгниа 7ь3орипгв„да$ие прп рассмотрепнп Вснмнтотпчесипл формул длл боеьгпнт и, мги иаи нтв тм3рни больгне подлодит дле праитпч33ских ъначеппй и, Кроме того, иогда и сигнгн3итсн болыие, чем Ы$6 нли Ололо того3 А4436 одполейточпвн $мниипа тьийгпигв не пвллетог реалиспФчнобг она ИНЗНИ'да ие будет иострое336. Припи)н$63 Вагигме реиггнй.
СО Времгми первого пвписаннп ангором большинства из примгдеиимл Вмгне иоммеггльрпее утнилО миОТО В3$нь$~ и можно $$:ра3$3тевтьси„что 6 тощ3пи снпт3466 В$3ннх ВВФФмагтгн (ОЙФАВВ ийзьгвлеьгь3х 4363иинелгн ф$$36663еле4 3регпгег гаесЛигсл)) д33сттггпут Опролнленньй пр3$тресс Ими„ИОиечио $66 и)$едстт3ВТ 3ян6 немало сделпхь В Втоп области. $6 )МЩМЗЮ. 6М СОГЛЛСНГВСЬ СО МНОЛ... ЧТО ЕСЛИ СО гтвл33пнеп Вде мм ВСГЛечТЕИЗЛ3 ГОЛЬЛО 66 ЕГЩЮЛ глееЕ, го лпееел гллеа ложюФВ Фьггь неемпос33но ллл33363д Ц)ЙВТ)ЮЗС $$ОЛМЬ (ВМЙ$3ЬОСП МООЛЕБ), АЛЛВЛ СТЛЛХЭ 3 3 ЛЕ ТЛЗМУ ОГ ПВЕГ) ($ЕВВ) ОТВЕТЫ К УПРАЖНЕНИЯМ 7вбе ответом угождать не должен! — шейлОк, Венецианский купец (акт !ч, сцена 1) ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ 1.
Средняя задача для читателя с математическими наклонностями. 4. См. ЪУ. 3. ЬеЧецпе, Тор!сэ т '74итЬег Тйеогу 2 (Неас)!пй, Мвзз.: А<Ы!воп-Ъев!еу, 1956), СЬарсег 3; Р. В)ЬепЬо)ш, 13 бес!агат оп РегтаРв Баас ТЛеогет (Хеи уогрс Брппйег-уег!ай, 1979); А. 1У))ач, Аппа)з оГ Магйетаг/св 141 (1995), 443 — 551. РАЗДЕЛ 1.1 1.
! < — а, а +- Ь, 5+ — с, с <- а, а ь- й 2. После первого случая выполнения шага Е1 значения переменных т и и — зто предыдущие значения п и г соответственно, а и > г. 3. Алгоритм Р (Алгорипьи Евклида). Даны два целых положительных числа т и и.
Найти их наибольший общий делитель. Р1. [Остаток от деления'т/и.[ Разделите т на и и пусть остатком будет гп. Р2. [Это нуль?) Если т = О, то работа алгоритма завершается и ответом будет и. РЗ. [Остаток от деления и/иь[ Разделите и ва т, и пусть остатком будет и. Р4. [Это нуль?[ Если и = О, то работа алгоритма завершается и ответом будет гп; в противном случае вернуться к шагу Р1.
3 4. С помощью алгоритма Е получаем: п = 6099, 2166, 1767, 399, 171, 57. Ответ: 57. 5. Не обладает свойствами конечности, определенности и эффективности и, пожалуй, не имеет выходных данных. Относительно формы записи: отсутствуют буквы перед номерами шагов, краткие описания шагов, а также символ "$". 6. Применяя алгоритм Е для о = 5 и т = 1, 2, 3, 4, 5, нахо~щм, что шаг Е1 выполняется 2, 3, 4, 3, 1 раз соответственно.
Таким образом, среднее равно 2,6 = Тж 7. Во всех случаях, за исключением конечного их числа, и > т. А если п > гп, то в ходе первой итерации алгоритма Е эти числа просто меняются местами; поэтому (/ = Т + 1. О. Пусть А = (а, Ь, с), аг = 5. Выполнение ЕШ1м,щ 1 в, О аЬ Фз ь, (Пустая строка) 1 а Ь 1 (Пустая строка) 2 а 3 с 4 Ь О 3 О О 3 4 Удалить одно а и одно 6 либо перейти к 2. Добавить с с левого края, перейти к О. Заменить все а на 6.
Заменить все с на а. Если Ь еще остались, повторить. алгоритма закончится, когда получим стро- 9. Например, можно сказать, что Сз представляет См если существуют функция д из Й в 1м Функция Л из Яз в Ям переводящая йз в йм и функция 2 из Оз в множество положительных целых чисел, удовлетворяющие следующим условиям.
а) Для любого элемента х из множества 1~ метод вычислений С~ дает выходное значение у для входного х тогда и только тогда, когда существует у' нз йю для которого Сз дает выходное значение у' для входа д(х) н Й(у~) = у. 6) Для любого д из Оз имеет место равенство ~~(6(д)) = 6(ззй ~ (д)), где 1зй ~ — это 1(д)-я итерация функции 1г. Например, пусть С~ — метод вычислений, определенный соотношениями (2), а Сз определяется соотношениями 1з = ((т, и)), йз = ((т, и Ы)), О, = 1з Ойз О ((т и а Ь 1)) 0 ((т, п,а 6г2)) 0 ((тп,а,ЬгЗ)) ц ((т, п,аЬ, г4)) 0 ((т, п,о,Ь,5)), Пусть 1з((т, и)) = (гп, и, т,, и, 1); 1 з ((т, и, И)) = (т, ц, И); Я(т, и, а, Ь, 1) ) = (т, п, а, Ь, а шод 6, 2); 1з ((т, и, а, Ь, г, 2) ) = (т, и, Ь), если г = О, в противном случае (т, в, а, Ь, г, 3); зз((гп, и, а, Ь, П 3) ) = (т, п,Ь,Ь, г,4); 1з((т,п> а,Ь, г,4)) = (т, и> о, г,5); 1з((т,п.а,Ь,5)) = 1з((т, п,а,Ь, 1)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
