Ви є тут

H-модель алгоритму і універсальна SH-модель обчислювача та їх використання для дослідження комп'ютерних засобів

Автор: 
Хуссейн Халіл Мурад
Тип роботи: 
Дис. канд. наук
Рік: 
2007
Артикул:
0407U001902
129 грн
Додати в кошик

Вміст

РАЗДЕЛ 2
1. АППАРАТНО-ПРОГРАММНОЕ ТОЛКОВАНИЕ АЛГОРИТМА
1.1. Компьютерная алгебра
В теории алгоритмов существует ряд научных направлений, которые в наибольшей
степени приближаются к развиваемому нами направлению – теории аппаратно
реализуемых компьютерных алгоритмов. Наиболее полно это направление
представлено в трудах украинского учёного В.Глушкова [2]. Одна из
основополагающих идей В.Глушкова, развитая широко известными учеными киевской
школы Ю.Капитоновой, А.Летичевским, Г.Луцким состоит в том, что вычислительная
система представляется в виде системы алгебрологических выражений, над которыми
можно выполнять ряд преобразований, а также в виде сети алгоритмических
модулей. Эти модули, в свою очередь, можно рассматривать как сети
алгоритмических модулей и т.п. Идея алгебрологических преобразований имеет
универсальный характер и может воплощаться как в аппаратуре, так и в программе
[22].
Последняя фраза выражает основную идею работы: универсальность
алгебрологических (алгоритмических) преобразований аппаратными и программными
средствами. Эта идея полностью подтверждается работами М.Черкасского.
Компьютерные алгоритмы (SH-модели) также реализуются аппаратно-программными
средствами. Они не находятся в противоречии с концепцией В.Глушкова и могут
рассматриваться как составная часть этой концепции.
Ниже приведены основные результаты по разработке алгебрологических
преобразований и исследование того, насколько эти преобразования согласуются с
теорией компьютерных алгоритмов, которая нашла развитие в данной диссертации, и
в чём имеются различия.
Далее в диссертации рассматриваются и сравниваются основные положения работы,
которые развиваются учеными киевской школы, с компьютерными алгоритмами на
основе SH-модели, которые реализуются аппаратно-программными средствами.
Некоторые новые результаты, полученные при выполнении диссертационной работы,
приведены ниже. В следующих разделах рассматриваются основные модели теории
компьютерной алгебры [34].
1.1.1. Схемы программ
Последовательная программа, выполняемая на компьютере, рассматривается здесь,
как управляющая компонента дискретного преобразователя, информационная среда
которого представляет собой обрабатываемые данные, включая состояния регистров
процессора и внешних устройств — внешней памяти, устройств ввода-вывода и т.п.
Состояние программы в текущий момент времени определяется выполняемой командой.
Специфика программы как управляющей составляющей дискретного преобразователя
состоит в том, что выполняемые ею элементарные преобразования разделяются на
две компоненты — проверку условия и преобразование состояния информационной
среды. В результате проверки условия происходит выбор оператора, действующего
на состояние информационной компоненты, и определяется следующее состояние
программы. Указанная специфика сохраняется также в процедурных языках
программирования высокого уровня, которые можно рассматривать как языки
описания моделей реальных программ.
Как видим, авторы используют понятие “элементарный преобразователь”, который
неформально почти совпадает с понятием “элементарный преобразователь” в теории
компьютерных алгоритмов [65].
Понятие схемы программы представляет собой наиболее распространенную
математическую модель программы. Большая общность понятия схемы программы
позволяет использовать его для изучения и представления алгоритмов, реализуемых
не только программными, но и микропрограммными, а также аппаратными средствами
вычислительных систем. С помощью схем программ можно выражать алгоритмы,
реализуемые и другими кибернетическими системами, отличными от ЭВМ, например,
биологическими, экономическими и т.п.
Здесь имеется расхождение. В этих абзацах понятие схемы программы -
математическая модель программы охватывает достаточно большой круг моделей
алгоритмов, включая собственно программу, независимую от реализующей её
компьютерных средств. Модель “схемы программы” подобна лишь частично модели
аппаратно-программных средств. SH-модель не исследует программы отдельно от
аппаратных средств. SH-модель, также как машина Тьюринга, нормальные алгоритмы
Маркова и др., является формальной алгоритмической системой. Она включает,
наряду с другими средствами, средства реализации вычислений и программу. Таким
образом, программа здесь лишь часть формальной алгоритмической системы, часть,
которая принципиально не может быть реализована без аппаратных (технических)
средств.
Далее приводится математическое описание схемы программы. Пусть U и Y два
множества. Первое будем называть множеством базовых условий, второе —
множеством базовых операторов. Рассмотрим множество U пропозициональных булевых
функций от базовых условий, т.е. будем рассматривать элементы множества U как
переменные, принимающие значения 0, 1, и строить из них функции, также
принимающие значения 0, 1. Функции такого рода будем называть элементарными
условиями.
Схемой программы над базисом (U , У) или U - Y-схемой программы называется
множество А состояний схемы вместе с множеством ТМАґЫґУ*ґА переходов и двумя
выделенными состояниями: начальным a(0) и заключительным a(1). Таким образом,
формально U- У-схема программы — это шестерка (A, U, Y, Т, a(0), a(1)). Слова в
алфавите Y, т.е. последовательности базовых операторов, будем называть
элементарными операторами. Каждый переход из множества Т представляет собой
четверку (а, и, q, а'), где и - элементарное условие, q - элементарный
оператор. Эту четверку так же, как и высказывание о ее принадлежности множеству
Т, будем записывать в виде . Если и = 1, то вместо будем писать , если же q = e
(пу