Ничего кроме правды

Ничего кроме правды

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

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

Вот пример. Рассмотрим для приведенной выше спецификации АТД STACK следующее выражение stackexp:

item (remove (put (remove (put (put (

remove (put (put (put (new, x1), x2), x3)),

item (remove (put (put (new, x4), x5)))), x6)), x7)))

По-видимому, выражение stackexp будет проще понять, если мы представим его как последовательность вспомогательных выражений:

s1 = new

s2 = put (put (put (s1, x1), x2), x3)

s3 = remove (s2)

s4 = new

s5 = put (put (s4, x4), x5)

s6 = remove (s5)

y1 = item (s6)

s7 = put (s3, y1)

s8 = put (s7, x6)

s9 = remove (s8)

s10 = put (s9, x7)

s11 = remove (s10)

stackexp = item (s11)

Какой бы вариант определения вы ни выбрали, по нему несложно восстановить вычисление, математической моделью которого является stackexp: создать новый стек; втолкнуть в него элементы x1, x2, x3 (в указанном порядке); удалить верхний элемент (x3), назвав получившийся стек s3; создать другой пустой стек и т. д. Этот процесс графически представлен на рис. 6.5.

Можно легко найти значение такого АТД выражения, нарисовав последовательно несколько таких рисунков. (Здесь найдено x4). Но теория позволяет нам получить этот результат формально, не обращаясь к рисункам, а только последовательно применяя аксиомы для упрощения выражения, до тех пор, пока дальнейшее упрощение станет невозможным. Например:

[x]. Применить A2 для упрощения s3 - т. е. заменить remove(put (put (put (s1, x1), x2), x3)) на выражение put (put (s1, x1), x2)). (Согласно A2 всякую пару remove-put можно выбросить).

Рис. 6.5.  Манипуляции со стеком

[x]. По той же аксиоме s6 равно put(s4, x4) . Затем можно применить аксиому A1 и вывести, что y1, т. е. item(put(s4, x4)) на самом деле равно x4, установив тем самым (как указано стрелкой на рисунке), что s7 получается в результате вталкивания x4 на верщину стека s3.

И так далее. Последовательность таких упрощений, выполненная механически так же легко и как последовательность упрощений в элементарной арифметике, приведет к значению выражения stackexp, которое действительно равно x4 (попробуйте проверить это сами, аккуратно проведя весь процесс упрощения).

Этот пример позволяет отметить одну из важнейших теоретических ролей абстрактных типов данных: они предоставляют формальную модель для понятий программы и выполнения программы. Эта модель чисто математическая: в ней нет императивных понятий состояния программы, переменных с изменяемыми во времени значениями, последовательности выполняемых действий. Она основана на обычных математических методах преобразования выражений.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Ещё одна «ничего не стоящая» информация

Из книги Искусство обмана автора Митник Кевин

Ещё одна «ничего не стоящая» информация Помимо номера расчётного центра и внутренних номеров, какая еще, по-видимому, бесполезная информация может быть чрезвычайно ценной для вашего врага?Телефонный звонок Питера Абеля«Привет», сказал человек на другом конце линии.


Ничего никому не скажу?

Из книги Журнал «Компьютерра» №36 от 04 октября 2005 года автора Журнал «Компьютерра»

Ничего никому не скажу? Первым нагнулся к уху головы сам дон Антоньо; он спросил ее тихо, но так, однако же, что все его услышали: - Заклинаю тебя, голова, волшебною силою, в тебе заключенною: скажи мне, какие у меня сейчас мысли? И голова, не разжимая губ, ясно и отчетливо, так,


Здесь нет ничего сложного!

Из книги Давайте создадим компилятор! автора Креншоу Джек

Здесь нет ничего сложного! Затем я думал, что причина в том, что мы не генерировали очень хороший объектный код. Те из вас, кто следовали этой серии и пытались компилировать примеры, знают, что хотя код работает и достаточно отказоустойчив, его эффективность довольно


ПИСЬМОНОСЕЦ: Если уж совсем ничего не получается…

Из книги Журнал «Компьютерра» № 29 от 14 августа 2007 года автора Журнал «Компьютерра»

ПИСЬМОНОСЕЦ: Если уж совсем ничего не получается… Автор: Илья ЩуровУважаемая редакция, читаю журнал с запозданием, поэтому, возможно, моя реплика и несвоевременна. В "КТ" #20 Евгений Козловский жалуется на проблемы с GPRS-роумингом у МТС, которые довели автора до смены


(7.15) Ничего не получается с hackmon.inf, чего делать?

Из книги Win2K FAQ (v. 6.0) автора Шашков Алексей

(7.15) Ничего не получается с hackmon.inf, чего делать? Если hackmon.inf у Вас по какой то причине не работает, то можно попробовать отредактировать соответствующие значения реестра вручную. Для этого заходите в HKEY_LOCAL_MACHINESYSTEMControlSetEnumDISPLAY, и дальше на две папки вглубь (их название зависит


6.5. Ничего не получается с hackmon.inf, чего делать?

Из книги WinXP FAQ (Часто задаваемые вопросы по ОС Windows XP) автора Шашков Алексей

6.5. Ничего не получается с hackmon.inf, чего делать? Если hackmon.inf у вас по какой то причине не работает, то можно попробовать отредактировать соответствующие значения реестра вручную. Для этого заходите в HKEY_LOCAL_MACHINE SYSTEM ControlSet Enum DISPLAY, и дальше на две папки вглубь (их название


Вы ничего не понимаете в компьютерах?

Из книги Очень хороший самоучитель пользователя компьютером. Как самому устранить 90% неисправностей в компьютере и увеличить его возможности автора Колисниченко Денис Николаевич

Вы ничего не понимаете в компьютерах? Чтобы устранять неисправности, вам нужно хотя бы ориентироваться в наименованиях и назначении комплектующих. Если вы не называете системный блок «процессором» или, что еще хуже, «железным ящиком» и можете отличить жесткий диск от


Нет ничего проще Герман Царев

Из книги Цифровой журнал «Компьютерра» № 22 [21.06.2010 — 27.06.2010] автора Журнал «Компьютерра»

Нет ничего проще Герман Царев Опубликовано 24 июня 2010 года Орфография и пунктуация автора сохранены. — прим. ред. Наверное, каждый человек, занимающийся разработкой программного обеспечения, когда-либо сталкивался с задачей обработки больших


Александр Амзин: Ничего не изменилось

Из книги Компьютерра PDA N134 (03.09.2011-09.09.2011) автора Журнал «Компьютерра»

Александр Амзин: Ничего не изменилось Автор: Александр АмзинОпубликовано 07 сентября 2011 годаКогда-нибудь мы полетим на Марс, освоим луны Юпитера и споём на два голоса с сиренами Титана. Космический корабль "Сид Мейер" устремится к Альфе Центавра; судно с замороженным


Сборка по принципу "все-или-ничего"

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Сборка по принципу "все-или-ничего" Когда нужно приводить в действие сборщик мусора?Классические сборщики мусора активизируются по требованию и работают до завершения. Другими словами, сборщик мусора не работает, пока остается память для работы приложения. Как только ее


41. Делайте данные-члены закрытыми (кроме случая агрегатов в стиле структур С)

Из книги Стандарты программирования на С++. 101 правило и рекомендация автора Александреску Андрей

41. Делайте данные-члены закрытыми (кроме случая агрегатов в стиле структур С) РезюмеДанные-члены должны быть закрыты. Только в случае простейших типов в стиле структур языка С, объединяющих в единое целое набор значений, не претендующих на инкапсуляцию и не


Еnergy harvesting: энергия из ничего Олег Нечай

Из книги Цифровой журнал «Компьютерра» № 17 (170) автора Журнал «Компьютерра»

Еnergy harvesting: энергия из ничего Олег Нечай Опубликовано 24 апреля 2013Мы все с интересом обсуждаем одежду со встроенными датчиками и пультами управления, кроссовки с шагомером, GPS и прочую носимую электронику. Однако стоит задаться вопросом: а от чего, собственно, должны


4.11.4. Правила "все кроме"

Из книги Linux глазами хакера автора Флёнов Михаил Евгеньевич

4.11.4. Правила "все кроме" Очень часто приходится задавать правила в виде "все кроме". Например, нужно запретить доступ к порту telnet всем пользователям, кроме компьютера с адресом 192.168.77.10. Лучше поступить следующим образом: сначала разрешить доступ для компьютера 192.168.77.10, а


Тот, кто ничего не знает, думает о Google

Из книги Антимозг [Цифровые технологии и мозг] автора Шпитцер Манфред

Тот, кто ничего не знает, думает о Google Идея этого теста проста: если кто-то, будучи занят определенным вопросом, не поддающимся немедленному решению, думает об Интернете или поисковой машине Google, то понятия «Google» или «Интернет» будут неизбежно мысленно активизированы. Эта


Контроль качества не должен ничего обнаружить

Из книги Идеальный программист. Как стать профессионалом разработки ПО автора Мартин Роберт С.

Контроль качества не должен ничего обнаружить Когда вы передаете окончательную версию продукта в службу контроля качества, вы должны рассчитывать на то, что контроль не выявит никаких проблем. Было бы в высшей степени непрофессионально передавать на контроль качества