Stany nierównowagowe procesów w przetwarzaniu algorytmicznym

• Autorzy: Strzałka D.
• Języki publikacji: PL

Abstrakty

PL

W artykule zostały zaprezentowane rozważania dotyczące istnienia możliwych związków pomiędzy nieekstensywnmą definicją entropii zaproponowaną przez C. Tsallisa a przetwarzaniem algorytmicznym na przykładzie sortowania przez wstawianie. Wykresy rozkładów empirycznych w skali log-lin pokazujące istnienie wolno zanikających ogonów rozkładów prawdopodobieństwa wskazują, że uwarunkowania termodynamiczne pracy analizowanego algorytmu wyłaniają się dopiero dla odpowiednio dużych przetwarzanych zbiorów danych. W pewnym sensie jest to cecha o charakterze emergentnym, która w klasycznej analizie algorytmów nie jest w ogóle brana pod uwagę. W artykule [23] pokazano, że taką cechą może być także przenoszenie pewnych własności sortowanych zbiorów danych (efekt zależności długoterminowych) na poziom dynamiki zachowań algorytmu i liczby operacji dominujących, jakie są wykonywane w czasie jego pracy. Jest to podejście odmienne od dotychczas zakładanego, kiedy to w klasycznej analizie złożoności obliczeniowej przyjmowano, że najbardziej interesującym i miarodajnym jest przypadek pesymistyczny (najgorszy z możliwych) lub w niektórych przypadkach tzw. przypadek średni. Tymczasem analiza pracy algorytmu w połączeniu z wiedzą nt. przetwarzanych danych pokazuje, że istnieją pewne charakterystyczne cechy, które mogą mieć fundamentalne znaczenie w przypadku analizy maszyn Turinga traktowanych nie jako model matematyczny, ale rozważanych w kontekście fizycznych właściwości implementacji.

EN

In article there will be shown the thermodynamical analysis of simple insertion sort algorithm and its possible connections with Tsallis non-extensive definition of entropy. The algorithmic processing, which is based on the idea of Turing machine will be connected with nonequilibrium thermodynamics to indicate the existence of non-equilibrium states in the case of insertion-sort. The implementations of Turing machines (considered as algorithms) need energy for their work, thus the problem of entropy production appears. As it will turn-out in the problem of sorting for some cases the levels of enfropy production will lead to the nonextensivity.

Słowa kluczowe

PL

przetwarzanie algorytmiczne; entropia nieekstensywna; sortowanie przez wstawianie; uwarunkowania termodynamiczne

EN

non-extensive entropy; non-equilibrium thermodynamics; algorithmic processing

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2009
• Tom: nr 2 (19)
• Strony: 145--160
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Strzałka D.

• Politechnika Rzeszowska, Wydział Elektrotechniki i Informatyki

Bibliografia

• [1] Tsallis C. What should a statistical mechanics satisfy to reflect nature?, Physica D, 193, 2004, pp. 3-34.
• [2] Laidler K. J. The Physical World of Chemistry. Oxford University Press, 1995.
• [3] Prigogine I., Stengers I. Z chaosu ku porządkowi. Nowy dialog człowieka z przyrodą, Państwowy Instytut Wydawniczy, Warszawa, 1990.
• [4] Morrison F. Sztuka modelowania układów dynamicznych, deterministycznych, chaotycznych, stochastycznych, WNT, Warszawa, 1996.
• [5] von Bertalanffy L. An Outline of General System Theory. British Journal of the Philosophy of Science, 1, 1950, pp. 134–164.
• [6] Tsallis C. Possible generalization of Boltzmann-Gibbs statistics, Journal Statistical Physics, 52, 1988, p. 479.
• [7] Tirnakli U., Buyukkilic F., Demirhan D. A New Formalis for Nonextensive Physical Systems: Tsallis Thermostatistics, Journal of Physics, 23, 1999, pp. 21 –28.
• [8] Alemany P. A., Zanette D. H. Fractal random walks from a variational formalism for Tsallis entropies, Physical Reviev E, 49, 1994, p.R956.
• [9] Tsallis C., Levy S. V. F., Souza A. M . C., Mayanard R. Statistical-Machanical Foundation of the Ubiquity of Lèvy Distributions in Nature, Physical Review Letters, 75, 1995, p.3589,
• [10] Mantegna R. N., Stanley H. E. Ekonofizyka - wprowadzenie, PWN, Warszawa, 2001.
• [11] Turing A. M. On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42, 1936, pp, 230–265. Errata appeared in Series 2, 43, 1937, pp. 544–546.
• [12] Penrose R. Nowy umysł cesarza, PWN, Warszawa, 2000.
• [13] Papadimitriou Ch. H. Złożoność obliczeniowa. WNT, Warszawa, 2002.
• [14] Cormen T. H., Leiserson Ch. E., Rivest R. L. Wprowadzenie do algorytmów. WNT, Warszawa, 2001.
• [15] Church A. An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, 58, 345-363.
• [16] Horákowá J., Kelemen J., Čapek J. Turing, von Neumann, and the 20th Century Evolution of the Concept of Machine. International Conference in Memoriam John von Neumann, John von Neumann Computer Society, pp. 121–135, Budapešť, 2003.
• [17] Deutsch K. Mechanism, Organism, and Society. Philosophy of Science, 18, 1951, pp. 230-252.
• [18] Knuth D. E. Sztuka programowania. WNT, Warszawa, 2002.
• [19] Deutsch K. Mechanism, Organism, and Society. Philosophy of Science, 18, 1951, pp. 230–252.
• [20] Stepney S., Braunstein S. L., Clark J. A., Tyrrell A., Adamatzky A., Smith R. E., Addis T., Johnson C., Timmis J., Welch P., Milner R., Partridge D. Journeys in non-classical computation II: Initial journeys and waypoints. International Journal of Parallel, Emergent and Distributed Systems, 21(2), 2006, pp. 97–125.
• [21] Banachowski L., Diks K., Rytter W. Algorytmy i struktury danych. WNT, Warszawa, 1996.
• [22] Amaral L. A. N., Ottino J. M. Complex Systems and Networks: Challenges and Opportunities for Chemical and Biological Engineers, Chemical Engineering Science, 59(8-9), 2004, pp. 1653–1666.
• [23] Grabowski F., Strzałka D.: Wybrane właściwości statystyczne dynamiki procesu sortowania przez wstawianie, Metody Informatyki Stosowanej 1/2009 (18), s. 85-98
• [24] Strzałka D. Procesy w systemie komputerowym na styku dane-algorytm prostego sortowania przez wstawianie w ujęciu statystyki nie-ekstensywnej, PhD Thesis, Politechnika Śląska, Wydział Automatyki, Elektroniki i Informatyki, Gliwice 2009
• [25] Grabowski F., Strzałka D. Dynamic behavior of simple insertion sort algorithm. Fundamenta Informaticae 72, 2006, pp. 155–165.
• [26] Strzałka D., Grabowski F. Towards possible non-extensive thermodynamics of algorithmic processing - statistical mechanics of insertion sort algorithm, International Journal of Modern Physics C, vol. 19 n. 9, 2008, pp. 1443–1458.
• [27] Kuhn T. S. The Structure of Scientific Revolutions, University of Chicago Press, 1962.