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

Алгебра алгоритмів — вивчає властивості алгоритмів, виникла в 80-х роках 20 століття. При цьому формальні моделі були запропоновані для первісного поняття алгоритму. Алгебра алгоритмів АА = {A, W}, як і будь-яка алгебра, — це основа А і сигнатура W операцій з елементами цієї основи. За допомогою операції сигнатури можна додати довільний елемент q Î AA. Це називається системою утворювальної алгебри.

Історія розвитку

Першою формальною моделлю алгоритмічної машини була машина Тюрінга (Алан Тюрінг, Еміль Пост, 1936). Із пізніших моделей відзначимо нормальні алгоритми (А. Марков, І952) .Дослідження і побудова алгебри алгоритмів або алгоритмічної алгебри почалося з проектування логічних структур ЕОМ під керівництвом академіка В. М. Глушкова. Як результат була створена теорія систем алгоритмічних алгебр (САА), що потім Г. О. Цейтліним була покладена в основу узагальненої теорії структурованих схем алгоритмів і програм, названою ним алгоритмікою. Для формалізації самого поняття алгебри алгоритму були запропоновані точні математичні описи .Алгебра алгоритмів виникла як розділ математичної логіки. Перші застосування алгебри алгоритмів -в математичній логіці. Алгебра алгоритмів є теоретичним фундаментом програмування, вона має застосування, де зустрічаються алгоритмічні проблеми (математики, теорія інформації, теорія керування, конструктивний аналіз, обчислювальна математика, теорія ймовірності, лінгвістика, економіка та ін.).Наразі розроблено кілька алгоритмічних алгебр, найвідомішими з яких є алгебра Дейкстри, алгебра схем Янова та алгоритміка програм, досліджена у працях В. М. Глушкова і Г. О. Цейтліна, а також теорія секвенційних алгоритмів, комп'ютерна реалізація алгебри алгоритмів.

Основні поняття алгебри алгоритмів

Основними поняттями алгебри алгоритмів є:– операції над множинами, булеві операції, предикати, функції й оператори;– бінарні і n-арні відношення, еквівалентність, частково і цілком упорядковані множини;– графи-схеми й операції над графовими структурами;– операції сигнатури САА, аксіоми і правила визначення властивостей програм на основі стратегії згортання, розгортання і їх комбінацій;– методи синтаксичного аналізу структурних програм і символьна обробка. Операції алгебри задовольняють наступні аксіоматичні закони: асоціативності, комутативності, ідемпотентності, закони виключення третього і суперечності.

Теорія секвенційних алгоритмів і проектування комп'ютерних систем. Редактор формул алгоритмів і аналіз синтаксису і семантики алгебри алгоритмів-секвенцій. Засоби еквівалентних перетворень алгоритмів. Методи підвищення ефективності математичного моделювання алгоритмів інформаційно-технологічних систем. Принципи побудови комп'ютерної бібліотеки абстрактних алгоритмів.

Застосування алгебри алгоритмів

• Синтез, оптимізація і дослідження математичних моделей алгоритмів керування електроприводом друкарської машини і проектування комп'ютерних систем. Практичним результатом досліджень алгебри алгоритмів є побудова оригінальних інструментальних систем проектування програм на основі сучасних засобів підтримки ООП (Rational Rose).

Література

• Марков А. А., Нагорный Н. М., Теория алгоритмов, М., 1984;
• Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965;
• Успенский В. А., Машина Поста, М., 1979;
• «Енциклопедія кібернетики», відповідальний ред. В. Глушков, 2 тт., 1973, рос. вид. 1974;
• Овсяк Володимир Казимирович. Методи підвищення ефективності математичного моделювання алгоритмів інформаційно-технологічних систем: Дис… д-ра техн. наук: 05.13.02 / Українська академія друкарства. —Львів, 1996. — 229л.
• Овсяк В. Засоби еквівалентних перетворень алгоритмів / Овсяк В. // Доповіді національної академії наук України. — 1996. — № 9. — C.83-89.
• Овсяк В. Принцип побудови підсистеми редагування формул абстрактних алгоритмів / В. Овсяк, А. Василюк // Комп'ютерні технології друкарства: Збірник наукових праць.- Львів: УАД, 2004. — № 12. — С. 137—145.
• 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.
• Овсяк В., Возна М. Синтез, оптимізація і дослідження математичних моделей алгоритмів керування електроприводом друкарської машини // Вісник Державного університету «Львівська політехніка». — № 364. -Прикладна математика. — Львів, 1999. — С. 105 — 110.
• Бритковський В. М., Овсяк В. К., Огірко О. І. Редактор формул алгоритмів і аналіз синтаксису і семантики алгебри алгоритмів-секвенцій. /Матеріали 7 всеукраїнської наукової конференції «Сучасні проблеми прикладної математики та інформатики» Львів: НУ ім. І. Франка,2000. -С. 17-18
• Овсяк В. К., Бритковський В. М., Овсяк О. В., Овсяк Ю. В. Теорія секвенційних алгоритмів і проектування комп'ютерних систем: Навчальний посібник. —Львів: УАД, 2001. —141 с.
• Огірко О. Синтаксис оптимізації моделі та моделювання синтаксису механізму розпізнавання символіки алгебри алгоритмів секвенції. // Комп'ютерні технології друкарства, № 5, 2000. -С. 296—303.
• Огірко О. Комп'ютерна реалізація алгебри алгоритмів. // Комп'ютерні технології друкарства, № 5, 2000. -С. 200—205.
• Огірко О. Автоматизовані способи розпізнавання для алгебри алгоритмів.// Автоматика — 2000. — Т.6. — Львів: Державний НДІ інформаційної інфраструктури, 2000.
• Огірко О. Модель системи генерації програм СКАНЕР. // Комп'ютерні технології друкарства, № 6, 2001. -С. 42-48.
• Огірко О. Модель комп'ютерної системи генерації програм з формул алгоритмів. // Комп'ютерні технології друкарства, № 6, 2001. -С. 93-97.
• Огірко О. І. Принцип побудови системи генерації програм з операцій теорії секвенційних алгоритмів//. КВАЛІЛОГІЯ КНИГИ, № 6, 2003. -С. 189—193.
• Огірко О.І Реалізація математичної моделі підсистеми генерації програм з операцій теорії секвенційних алгоритмів// Комп'ютерні технології друкарства, № 8, 2004.

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

Див. також

• Список алгоритмів
• Теорія складності обчислень