Алгебра алгоритмов

Материал из Циклопедии
Перейти к навигации Перейти к поиску

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

Возникновение теории алгоритмов[править]

Монография В. М. Глушкова, Г. Е. Цейтлина и Е. Л. Ющенко «Алгебра, языки, программирование», содержащая введение в теорию универсальных алгебр с учетом применения этого аппарата в теоретическом программировании, была опубликована в 1974 году. На стыке математической логики и теории программирования в середине 1970-х годов возникло новое направление по алгоритмическим (программным) логикам и логикам процессов. Прообразом пропозициональных программных логик явились системы алгоритмических алгебр, исследованные В. М. Глушковым. Киевская школа (Е. Л. Ющенко, Г. Е. Цейтлин, В. Н. Редько) развивала эти исследования в направлении аксиоматизации систем алгоритмических алгебр как основы схематологии структурного программирования и универсальных программных логик. Система алгоритмических алгебр, разработанная В. М. Глушковым и его учениками, называемая обычно алгебра алгоритмов Глушкова (в дальнейшем алгебра алгоритмов), хорошо зарекомендовала себя при решении весьма широкого класса задач, подтверждая, таким образом, перспективность использования алгебраического аппарата в рамках прикладной теории алгоритмов . При этом, естественно, необходимо сохранить положительные свойства алгебры алгоритмов, в частности, возможности преобразования алгоритмов с целью их оптимизации.

Система алгоритмических алгебр[править]

Для разработки алгебраической системы В. М. Глушковым была предложена известная абстрактная модель функционирования ЭВМ, которая представляет собой схему взаимодействия двух автоматов управляющего — U и операционного — O.

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

См. также[править]

Литература[править]

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
  • Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Программирование. — Киев: Наук. думка, 1978. — 319 с.
  • Ющенко Е. Л., Цейтлин Г. Е.,Грицай В. П., Терзян Т. К. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий. — М.: Финансы и статистика, 1989. — 208 с.
  • Цейтлин Г. Е. Введение в алгоритмику. — Киев: «Сфера», 1998. — 310 с.
  • Брусенцов Н. П., Владимирова Ю. С. Компьютеризация булевой алгебры // Докл. Академии наук, 2004. — Т. 395.- № 1.
  • Поспелов Д. А. Логические методы анализа и синтеза схем. Изд. 3-е, перераб. и доп. — М.: Энергия, 1974. — 368 с.
  • Акуловський В. Г., Костенко В. В. Перетворення елементарних алгоритмічних конструкцій за допомогою засобів алгебри алгоритмів // Вісн. АМС України.  2006. — № 3. — С. 93 — 99.
  • Вирт Н. Алгоритмы + структуры данных = программы. — М.: Мир, 1985. — 406 с.
  • Колмогоров А. Н. Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
  • Марков А. А., Нагорный Н. М. Теория алгорифмов, изд. 2. — М.: ФАЗИС, 1996.
  • Мальцев А. И. Алгоритмы и рекурсивные функции, М., 1965;
  • Успенский В. А. Машина Поста, М., 1979;
  • «Енциклопедія кібернетики», відповідальний ред. Глушков, Виктор Михайлович, 2 тт., 1973, рос. вид. 1974;
  • Овсяк Володимир Казимирович. Методи підвищення ефективності математичного моделювання алгоритмів інформаційно-технологічних систем : Дис… д-ра техн. наук: 05.13.02 / Українська академія друкарства. —Львів, 1996. — 229л.
  • Owsiak W., Owsiak A., Owsiak J. Teoria algorytmów abstrakcyjnych i modelowanie matematyczne systemów informacyjnych / Owsiak W., Owsiak A., Owsiak J. — Opole: Politechnika Opolska, 2005. — 275 s.
  • Овсяк В. Принципи побудови комп’ютерної бібліотеки абстрактних алгоритмів Коба / В. Овсяк, А. Василюк, О. Яремчишин // Комп’ютерні технології друкарства: Збірник наукових праць.- Львів: УАД, 2006. — № 15. — С.85 — 95.
  • Ovsyak V. Automation of the Process of Search of the Algorithms’ Formulae in the Library «КоБА» / V. Ovsyak, A. Vasyluk, O. Yaremchyshyn // Proc. of the IX-th intern. Conference «The experience of designing and application of CAD systems in microelectronics (CADSM’2007)». -Lviv-Polyana: Lviv Polytechnic National University, 2007. — P. 418—420.
  • Бритковський В. М., Овсяк В. К., Огірко О. І. Редактор формул алгоритмів і аналіз синтаксису і семантики алгебри алгоритмів-секвенцій. /Матеріали 7 всеукраїнської наукової конференції «Сучасні проблеми прикладної математики та інформатики» Львів: НУ ім. І. Франка, 2000. — С. 17-18

Ссылки[править]

Источник — http://cyclowiki.org/w/index.php?title=Алгебра_алгоритмов&oldid=402851