Проблемы эквивалентности и распознавания принадлежности к некоторому классу алгоритмов в своей полной подстановке являются алгоритмически неразрешимыми проблемами. До сих пор их решали только для некоторых видов алгоритмических систем при довольно узком определении эквивалентности.Основные результаты относятся к операторным схемам.В качестве характерных черт операторных схем можно выделить следующие черты:-совокупность операторов, образующих схему алгоритма, изображается явно;-для каждого оператора явно указываются его приемники и предшественники по выполнению, а также его аргументы и результаты;-при построении реализации приемник оператора обычно выбирается без учета истории движения к этому оператору;-если в рассмотрение вовлекается некоторая величина, «вырабатывается» некоторым оператором, то она трактуется как независимая переменная, то есть считается, что после выполнения данного оператора она может принимать любое значение независимо от предыдущей истории;-если аргументом или результатом оператора оказывается компонента массива, указанная индексом, то значение индекса обычно игнорируется и считается, что аргументом и результатом оператора является весь массив.Первой работой, посвященной общей теории преобразования алгоритмов, явилась работа Ю.И. Янова «О логических схемах алгоритмов». В ней были сформулированы основные компоненты теории преобразования алгоритмов, а именно:-формализация понятия схемы алгоритма;-задание отношения эквивалентности;-определение алгоритма, распознающего эквивалентность схем;-построение системы преобразований, полной в том смысле, что любую пару эквивалентных алгоритмов можно трансформировать один в другой последовательным применением этих преобразований, сохраняющих эквивалентность.Всякий алгоритм при переработке конкретного объекта предписывает однозначно определенную последовательность элементарных действий. Такая последовательность, вообще говоря, различна для различных объектов, к которым данный алгоритм может быть применен. Однако всегда найдется конечное множество предикатов, характеризующих некоторые свойства перерабатываемых объектов, такое, что для данного алгоритма зависимость порядка выполнения элементарных действий от перерабатываемых объектов будет однозначной функцией этих предикатов.Такая функция может быть записана при конечной строки, составленной из символов элементарных действий А1,A2,…,An( называемых операторами), предикатов и некоторых вс символов: [i ; i] (i=1.2….), называемых соответственно левой и правой полускобками.Строка А1А2А3…Аs означает, что последовательно должны быть выполнены операторы А1 ,А2, А3, …,Аs.Строка А1 р[iA2…i]A3 ,где р - некоторый предикат, означает, что после выполнения оператора А1 в случае р=1 должен быть выполнен оператор А2 ,стоящий непосредственно правее р[i, а если р=0, то оператор А3, стоящий справа от полускобки i].Строки такого вида называются схемными записями алгоритмов. Один и тот же алгоритм при фиксированном множестве элементарных операций и предикатов может иметь различные логические схемы.
Человек стремится познать объекты окружающего мира, он взаимодействует с существующими объектами и создает новые объекты.Одним из методов познания объектов окружающего мира является моделирование, состоящее в создании и исследовании «заместителей» реальных объектов. «Объект-заместитель» принято называть моделью, а исходный объект - прототипом или оригиналом.Например, в разговоре мы замещаем реальные объекты их именами, оформители витрин используют манекен - модель человеческой фигуры, конструкторы строят модели самолетов и автомобилей, а архитекторы - макеты здании, мостов и парков. Моделью является любое наглядное пособие, используемое на уроках в школе: глобус, муляж, карта, схема, таблица и т. п.Модель важна не сама по себе, а как инструмент, облегчающий познание или наглядное представление объекта.
К созданию моделей прибегают, когда исследуемый объект слишком велик (модель Солнечной системы) или слишком мал (модель атома), когда процесс протекает очень быстро (модель двигателя внутреннего сгорания) или очень медленно (геологическая модель), когда исследование объекта может оказаться опасным для окружающих (модель атомного взрыва), привести к разрушению его самого (модель самолета) или создание реального объекта очень дорого (архитектурный макет города) и т. д. Во-первых, модель не является точной копией объекта-оригинала: она отражает только часть его свойств, отношений и особенностей поведения. Например, на манекен можно надеть костюм, но с ним нельзя поговорить. Модель автомобиля может быть без мотора, а макет дома — без электропроводки и водопровода. Во-вторых, поскольку любая модель всегда отражает только часть признаков оригинала, то можно создавать и использовать разные модели одного и того же объекта. Например: мяч может воспроизвести только одно свойство Земли — ее форму; обычный глобус отражает, кроме того, расположение материков; а глобус, входящий в состав действующей модели Солнечной системы, — еще и траекторию движения Земли вокруг Солнца. Чем больше признаков объекта отражает модель, тем она полнее. Однако отразить в модели все свойства объек- та-оригинала невозможно, а чаще всего и не нужно. Ведь при создании модели человек, как правило, преследует вполне определенную цель и стремится наиболее полно отразить только те признаки объектов, которые кажутся ему важными, существенными для реализации этой цели. Если, например, модель самолета создается для коллекции, то в ней воспроизводится внешний вид самолета, а не его летные характеристики.От цели моделирования зависят требования к модели: какие именно признаки объекта-оригинала она должна отражать.Отразить в модели признаки оригинала можно одним из двух Во-первых, признаки можно скопировать, воспроизвести. Такую модель называют натурной (материальной). Примерами натурных моделей являются муляжи и макеты — уменьшенные или увеличенные копии, воспроизводящие внешний вид объекта моделирования (глобус), его структуру (модель Солнечной системы) или поведение (радиоуправляемая модель автомобиля).Во-вторых, признаки оригинала можно описать на одном из языков кодирования информации — дать словесное описание, привести формулу, схему или чертеж. Такую модель называют информационной.Модели используются человеком для:• представления материальных предметов (макет застройки жилого района в мастерской архитектора); • объяснения известных фактов (макет скелета человека в кабинете биологии); • проверки гипотез и получения новых знаний об исследуемых объектах (модель полета самолета новой конструкции в аэродинамической трубе); • прогнозирования (сделанные из космоса фотоснимки движения воздушных масс); • управления (расписание движения поездов) и т. д.
