Определения, операции, свойства

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

 

МОДЕЛИ ВЫЧИСЛЕНИЙ

В данной главе рассмотрим различные способы представления вычислений (обработки данных) в виде моделей;эти способы связаны с различной природой вычислений.

Модель – математическая абстракция для класса объектов (процессов), в которой выделяются существенные свойства класса и отбрасываются несущественные; чем грубее модель, тем шире класс. Хорошо сформулированная модель обладает ясным физическим смыслом и адекватна (соответствует, отвечает требованиям точности) данному классу. Например, в планетарной модели небесные тела представляются в виде материальных точек, не имеющих размеров, но имеющих конкретную массу; эта модель позволяет достаточно точно предсказывать, например, лунные затмения.

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

Для вычислений в широком смысле построены разнообразные модели, учитывающие характер вычислений (численные, логические, символьные), разрядность чисел (битовые либо байтовые), постоянство длины обрабатываемых слов в ЭВМ и т. д.

Ниже рассматриваются 2 модели вычислений в узком смысле:

· ассоциативные исчисления;

· рекурсивные функции,

а также 2 модели дискретной переработки информации – автоматы и машины Тьюринга.

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

Численные алгоритмы сводят решение поставленной задачи к арифметическим действиям над числами. Пример — алгоритм Евклида для нахождения наибольшего общего делителя двух заданных положительных чисел. К численным алгоритмам сводится решение многих задач: вычисление корней алгебраических уравнений, решение систем уравнений, численное интегрирование и т. п. Моделью таких вычислений являются рекурсивные функции.

Очень широкий класс задач связан с дискретной переработкой информации (символов). Это, например, кодирование и декодирование сообщений. В качестве моделей таких преобразований используются конечные автоматы.

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

Ассоциативные исчисления

Определения, операции, свойства

Исчисление — определённый набор операций над совокупностью математически однородных объектов и правила преобразования этих объектов с использованием данных операций. Примером исчисления, которое широко используется в процессе синтеза логических схем, являются преобразования алгебры логики. Набор правил (аксиом, законов, тождеств) говорит лишь о том, как можно преобразовать исходное булево выражение, но ничего не говорит о том, как надо его преобразовывать (в какой последовательности и что делать на каждом шаге), чтобы, например, на заданном логическом базисе получить минимальную задержку схемы. Таким образом, исчисление, в отличие от алгоритма, не содержит указаний, куда нужно идти, чтобы получить результат, а содержит только список допустимых преобразований.

Расширение понятия алгоритма за счёт введения в рассмотрение объектов нечисловой природы связано с ассоциативным исчислением. Ассоциативное исчисление строится на множестве всех слов в данном алфавите с помощью определённой совокупности операций.

Алфавит — любая конечная совокупность различных символов, называемых буквами. Любая конечная совокупность n букв некоторого алфавита является словом длины n в этом алфавите.

Если, слово L является частью слова М, то говорят, что слово L входит в слово М. Например, в слове abcbcbad имеются два варианта вхождения слова bcb и одно вхождение слова bа.

В качестве операций ассоциативного исчисления определяется система допустимых подстановок, спомощью которых одни слова преобразуются в другие. Подстановка вида L — М, где L и М — слова в том же алфавите, означает: слово L заменяется на М и наоборот.

Например, пусть имеется алфавит А = { а, b, с }. Рассмотрим слово abcbcbab;к этому слову можно применить подстановку ab - bcb четырьмя способами. Заменяя вхождение ab дважды, получим: bcbcbcbbcb. В то же время к слову bacb эта подстановка не применима.

Рассмотрим особую подстановку B. Она означает, что из преобразуемого слова удаляется вхождение слова Р (оно заменяется пустым символом), а также, что между двумя какими-либо буквами преобразуемого слова, впереди него либо за ним, вставляется слово Р. Например, заданы слово dbcd и подстановка abc - #. В результате подстановки получаем: dabcbcd

Итак, ассоциативное исчисление (АИ) — это множество всех слов в некотором алфавите вместе с конечной системой допустимых подстановок.

Эквивалентность слов. Два слова называют эквивалентными, если, одно из них можно получить из другого последовательным применением допустимых подстановок.

Последовательность слов R1, R2, R3,..., Rn, когда каждое слово является результатом однократного применения допустимой подстановки к предыдущему слову, образует дедуктивную цепочку,причём соседние слова в этой цепочке называются смежными. Очевидно, что любые два слова в дедуктивной цепочке являются эквивалентными.

Эквивалентность слов (обозначается L ~ M)обладает всеми свойствами отношения эквивалентности — рефлексивностью, симметричностью и транзитивностью.

Если L ~ М, то при наличии в каком-либо слове R вхождения L в результате подстановки L - М получается слово R', эквивалентное R.

Например, используя эквивалентность acd ~ cad, из слова R = b acd c получаем эквивалентное ему слово R' = b cad c.

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

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

С помощью алгоритма перебора решается ограниченная проблема слов; требуется установить, можно ли одно из заданных слов преобразовать в другое применением допустимых подстановок не более чем К раз, где К — произвольное, но фиксированное целое число. Такое ограничение в случае лабиринта означает, что расстояние между рассматриваемыми площадками не превышает К коридоров.

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

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

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