Алгебра алгоритмів — вивчає властивості алгоритмів, виникла в 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.
Див. також
Ця стаття потребує додаткових для поліпшення її . (березень 2017) |
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algebra algoritmiv vivchaye vlastivosti algoritmiv vinikla v 80 h rokah 20 stolittya Pri comu formalni modeli buli zaproponovani dlya pervisnogo ponyattya algoritmu Algebra algoritmiv AA A W yak i bud yaka algebra ce osnova A i signatura W operacij z elementami ciyeyi osnovi Za dopomogoyu operaciyi signaturi mozhna dodati dovilnij element q I AA Ce nazivayetsya sistemoyu utvoryuvalnoyi algebri Istoriya rozvitkuPershoyu formalnoyu modellyu algoritmichnoyi mashini bula mashina Tyuringa Alan Tyuring Emil Post 1936 Iz piznishih modelej vidznachimo normalni algoritmi A Markov I952 Doslidzhennya i pobudova algebri algoritmiv abo algoritmichnoyi algebri pochalosya z proektuvannya logichnih struktur EOM pid kerivnictvom akademika V M Glushkova Yak rezultat bula stvorena teoriya sistem algoritmichnih algebr SAA sho potim G O Cejtlinim bula pokladena v osnovu uzagalnenoyi teoriyi strukturovanih shem algoritmiv i program nazvanoyu nim algoritmikoyu Dlya formalizaciyi samogo ponyattya algebri algoritmu buli zaproponovani tochni matematichni opisi Algebra algoritmiv vinikla yak rozdil matematichnoyi logiki Pershi zastosuvannya algebri algoritmiv v matematichnij logici Algebra algoritmiv ye teoretichnim fundamentom programuvannya vona maye zastosuvannya de zustrichayutsya algoritmichni problemi matematiki teoriya informaciyi teoriya keruvannya konstruktivnij analiz obchislyuvalna matematika teoriya jmovirnosti lingvistika ekonomika ta in Narazi rozrobleno kilka algoritmichnih algebr najvidomishimi z yakih ye algebra Dejkstri algebra shem Yanova ta algoritmika program doslidzhena u pracyah V M Glushkova i G O Cejtlina a takozh teoriya sekvencijnih algoritmiv komp yuterna realizaciya algebri algoritmiv Osnovni ponyattya algebri algoritmivOsnovnimi ponyattyami algebri algoritmiv ye operaciyi nad mnozhinami bulevi operaciyi predikati funkciyi j operatori binarni i n arni vidnoshennya ekvivalentnist chastkovo i cilkom uporyadkovani mnozhini grafi shemi j operaciyi nad grafovimi strukturami operaciyi signaturi SAA aksiomi i pravila viznachennya vlastivostej program na osnovi strategiyi zgortannya rozgortannya i yih kombinacij metodi sintaksichnogo analizu strukturnih program i simvolna obrobka Operaciyi algebri zadovolnyayut nastupni aksiomatichni zakoni asociativnosti komutativnosti idempotentnosti zakoni viklyuchennya tretogo i superechnosti Teoriya sekvencijnih algoritmiv i proektuvannya komp yuternih sistem Redaktor formul algoritmiv i analiz sintaksisu i semantiki algebri algoritmiv sekvencij Zasobi ekvivalentnih peretvoren algoritmiv Metodi pidvishennya efektivnosti matematichnogo modelyuvannya algoritmiv informacijno tehnologichnih sistem Principi pobudovi komp yuternoyi biblioteki abstraktnih algoritmiv Zastosuvannya algebri algoritmivSintez optimizaciya i doslidzhennya matematichnih modelej algoritmiv keruvannya elektroprivodom drukarskoyi mashini i proektuvannya komp yuternih sistem Praktichnim rezultatom doslidzhen algebri algoritmiv ye pobudova originalnih instrumentalnih sistem proektuvannya program na osnovi suchasnih zasobiv pidtrimki OOP Rational Rose LiteraturaMarkov A A Nagornyj N M Teoriya algoritmov M 1984 Malcev A I Algoritmy i rekursivnye funkcii M 1965 Uspenskij V A Mashina Posta M 1979 Enciklopediya kibernetiki vidpovidalnij red V Glushkov 2 tt 1973 ros vid 1974 Ovsyak Volodimir Kazimirovich Metodi pidvishennya efektivnosti matematichnogo modelyuvannya algoritmiv informacijno tehnologichnih sistem Dis d ra tehn nauk 05 13 02 Ukrayinska akademiya drukarstva Lviv 1996 229l Ovsyak V Zasobi ekvivalentnih peretvoren algoritmiv Ovsyak V Dopovidi nacionalnoyi akademiyi nauk Ukrayini 1996 9 C 83 89 Ovsyak V Princip pobudovi pidsistemi redaguvannya formul abstraktnih algoritmiv V Ovsyak A Vasilyuk Komp yuterni tehnologiyi drukarstva Zbirnik naukovih prac Lviv UAD 2004 12 S 137 145 Owsiak W Owsiak A Owsiak J Teoria algorytmow abstrakcyjnych i modelowanie matematyczne systemow informacyjnych Owsiak W Owsiak A Owsiak J Opole Politechnika Opolska 2005 275 s Ovsyak V Principi pobudovi komp yuternoyi biblioteki abstraktnih algoritmiv Koba V Ovsyak A Vasilyuk O Yaremchishin Komp yuterni tehnologiyi drukarstva Zbirnik naukovih prac Lviv UAD 2006 15 S 85 95 Ovsyak V Automation of the Process of Search of the Algorithms Formulae in the Library KoBA 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 Ovsyak V Vozna M Sintez optimizaciya i doslidzhennya matematichnih modelej algoritmiv keruvannya elektroprivodom drukarskoyi mashini Visnik Derzhavnogo universitetu Lvivska politehnika 364 Prikladna matematika Lviv 1999 S 105 110 Britkovskij V M Ovsyak V K Ogirko O I Redaktor formul algoritmiv i analiz sintaksisu i semantiki algebri algoritmiv sekvencij Materiali 7 vseukrayinskoyi naukovoyi konferenciyi Suchasni problemi prikladnoyi matematiki ta informatiki Lviv NU im I Franka 2000 S 17 18 Ovsyak V K Britkovskij V M Ovsyak O V Ovsyak Yu V Teoriya sekvencijnih algoritmiv i proektuvannya komp yuternih sistem Navchalnij posibnik Lviv UAD 2001 141 s Ogirko O Sintaksis optimizaciyi modeli ta modelyuvannya sintaksisu mehanizmu rozpiznavannya simvoliki algebri algoritmiv sekvenciyi Komp yuterni tehnologiyi drukarstva 5 2000 S 296 303 Ogirko O Komp yuterna realizaciya algebri algoritmiv Komp yuterni tehnologiyi drukarstva 5 2000 S 200 205 Ogirko O Avtomatizovani sposobi rozpiznavannya dlya algebri algoritmiv Avtomatika 2000 T 6 Lviv Derzhavnij NDI informacijnoyi infrastrukturi 2000 Ogirko O Model sistemi generaciyi program SKANER Komp yuterni tehnologiyi drukarstva 6 2001 S 42 48 Ogirko O Model komp yuternoyi sistemi generaciyi program z formul algoritmiv Komp yuterni tehnologiyi drukarstva 6 2001 S 93 97 Ogirko O I Princip pobudovi sistemi generaciyi program z operacij teoriyi sekvencijnih algoritmiv KVALILOGIYa KNIGI 6 2003 S 189 193 Ogirko O I Realizaciya matematichnoyi modeli pidsistemi generaciyi program z operacij teoriyi sekvencijnih algoritmiv Komp yuterni tehnologiyi drukarstva 8 2004 Div takozhSpisok algoritmiv Teoriya skladnosti obchislenCya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno berezen 2017 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi