Rozszerzenie algebry algorytmów

• Autorzy: Owsiak W. , Owsiak A.

Warianty tytułu

EN

The expansion of algorithm algebra

• Języki publikacji: PL

Abstrakty

PL

W artykule za pomocą metody aksjomatycznej przedstawiono pod-stawy rozszerzonej algebry algorytmów. Algebra ta obejmuje operacje sekwencjonowania, eliminowania, zrównoleglenia, rewersowania oraz cyklicznego sekwencjonowania, eliminowania i zrównoleglenia, wykonywane na unitermach. Podano definicję algorytmu, do jakiego ma zastosowanie rozszerzona algebra algorytmów. Istotę zdefiniowanych operacji rozszerzonej algebry algorytmów zilustrowano za pomocą rysunków. Na przykładzie pokazano jej zastosowanie. Opis porównano z opisem algorytmów, otrzymywanym za pomocą klasycznej algebry algorytmów.

EN

Very often algorithms are described verbally or like a unit - diagram. The well known methods offering algorithms are: Post [1], Turing [2], Aho-Ullman-Hopcroft [3] or Schönhage [4] virtual machines, recursive functions (calculus λ, Church) [5], Markov algorithms [6], b-complexes of Kolmogorov (Kolmogorov machine) [7], Krinitski universal algorithms [8], and algorithm algebra [9]. It is obvious that verbal methods, and methods of unit - diagram, as well as, algorithm methods [1] - [8] are depicted by the intuition, not formally. Only by means of the algorithm algebra, the algorithm description is getting into the formulae form, on abstract and meaningful levels. The transformation and investigation of their trustworthiness can be made on formulae of algorithms with minimization target, by the specific operations. These advantages of algebra algorithms beyond other methods of algorithm description make a ground for it's using. Classical algorithm algebra [9] manipulates over conditional uniterms, which are delivered only two meanings (e.g. "yes" and "no" or "0" and "1").Very often conditional uniterm can deliver more than two meanings. For example, automation systems are operated in a plenty of regimes. Score parameters are controlled in checking systems. It is possible to describe the algorithms which contain more than 2 conditions by means of classical algebra algorithms. These formulae - algorithms are complicated for apprehension. To avoid possible mistakes, the expansion of the algorithm algebra is presented in the paper.

Słowa kluczowe

PL

uniterm; operacja; sekwencjonowanie; cykliczne sekwencjonowanie; eliminowanie; cykliczne eliminowanie; zrównoleglenie; cykliczne zrównoleglenie; rewersowanie; algebra algorytmów

EN

uniterm; operation; sequencing; elimination; cyclic paralleling

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 2
• Strony: 184--188
• Opis fizyczny: Bibliogr. 10 poz., wzory

Twórcy

autor

Owsiak W.

autor

Owsiak A.

• Politechnika Opolska, Opole i Ukraińska Akademia Drukarstwa, Lwów,

Bibliografia

• [1] Post E. L.: Finite Combinatory Processes ̃ Formulation 1. Journal of Symbolic Logic, 1, pp. 103-105, 1936. Reprinted in The Undecidable, pp. 289ff.
• [2] Turing A. M.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of London Mathematical Society, series 2, vol. 42 (1936-1937), pp. 230-265; correction, ibidem, vol. 43, pp. 544-546. Reprinted in [13 Davis M., pp. 155-222] and available online at http://www.abelard.org/turpap2/tp2-ie.asp
• [3] Aho A. V., Hopcroft J. E., Ullman J. D.: The design and analysis of computer algorithms. Addison-Wesley Publishing Company, 1974.
• [4] Schönhage A.: Universelle Turing Speicherung. In J. Dörr and G. Hotz, Editors, Automatentheorie und Formale Sprachen, Bibliogr. Institut, Mannheim, 1970, pp. 369-383.
• [5] Church A.: An unsolvable problem of elementary number theory. American Journal of Mathematics, vol. 58 (1936), pp. 345-363.
• [6] Markov A. A.: Theory of algorithms (in Russian). Editions of Academy of Sciences of the USSR, vol. 38, 1951, pp. 176-189; translated into English in American Mathematical Society Transactions, 1960, series 2, 15, pp. 1-14.
• [7] Kolmogorov A. N.: On the concept of algorithm (in Russian). Uspekhi Mat. Nauk 8:4 (1953), pp. 175?176; translated into English in Uspensky V. A., Semenov A. L.: Algorithms: Main Ideas and Applications, Kluwer, 1993.
• [8] Krinitski N. A.: Algorithms around us (in Russian). Mir, Moscow, 1988; also translated to Spanish (Algoritmos a nuestro alrededor).
• [9] Owsiak W., Owsiak A., Owsiak J.: Teoria algorytmów abstrakcyjnych i modelowanie matematyczne systemów informacyjnych. Wyd. Pol. Opolskiej, Opole, 2005.
• [10] Perry S. C.: C# i .NET. Wyd. Helion, Gliwice, 2006.