Wybrane właściwości statystyczne dynamiki procesu sortowania przez wstawianie

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

Abstrakty

PL

W artykule pokazano, że pełne zrozumienie dynamiki struktury wykonawczej wymaga w pierwszej kolejności zrozumienia mechanizmów rządzących stykiem algorytm struktura danych wejściowych. Procesy generowane na szczycie tej struktury są następnie przenoszone na kolejne warstwy struktury wykonawczej powodując ich kumulowanie się, co w efekcie sprawia, że spada wydajność całego systemu komputerowego. Zrozumienie i próba zamodelowania tych procesów pozostaje kluczową kwestią nie tylko w kontekście nowego spojrzenia na dynamikę całej struktury wykonawczej oraz nowego spojrzenia na problem złożoności obliczeniowej, ale także z punktu widzenia dalszego rozwoju systemów operacyjnych i zastosowanych w nich metod dostępu do zasobów.

EN

In article there will be shown a new, general view on algorithmic processing in computer system basing on problem of task, in which exist the long-range dependencies, fit to the execution structure with particular considerations about the algorithm level. The existing misfits at contact between the successive levels of this structure cause that the task realization, which can be compared to the fluid flow, is no longer a process with short-range dependencies (a laminar flow) but becomes the process with long-term dependencies (a turbulent flow}. The understanding of mechanisms that govern this phenomenon by the analysis of contact between input set and algorithm is possible when one considers the whole structure as a complex system. In paper there will be presented some statistical properties of insertion sorting process, which will show not only its complex character but also can be used to wider aur knowledge that can be used for design the execution structure that will dynamically fit to the existing phenomena that can appear during the task processing.

Słowa kluczowe

PL

algorytm sortowania przez wstawianie; przetwarzanie algorytmiczne; zależności dalekiego zasięgu; systemy złożone

EN

insertion sort algorithm; algorithmic processing; long-range dependencies; complex systems

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2009
• Tom: nr 1 (18)
• Strony: 85--98
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Strzałka D.

autor

Grabowski F.

• Politechnika Rzeszowska, Wydzial Elektrotechniki i Informatyki

Bibliografia

• [1] Grabowski F., Strzałka D. Influence of data structure and algorithm on sort dynamics. Proc. CS&P’2005 Workshop, Warsaw University, 2005, pp. 168-184.
• [2] Papadimitriou Ch. H. Złożoność obliczeniowa. WNT, Warszawa, 2002.
• [3] Knuth D. E. Sztuka programowania. WNT, Warszawa, 2002.
• [4] Deutsch K. Mechanism, Organism, and Society. Philosophy of Science, 18, 1951, pp.230-252.
• [5] von Bertalanffy L. An Outline of General System Theory. British Journal of the Philosophy of Science, 1, 1950, pp. 134-164.
• [6] Wróblewski P. Algorytmy, struktury danych i techniki programowania. Helion, Gliwice, 1997.
• [7] Banachowski L., Diks K., Rytter W. Algorytmy i struktury danych. WNT, Warszawa, 1996.
• [8] Cormen T. H., Leiserson Ch. E., Rivest R. L. Wprowadzenie do algorytmów. WNT, Warszawa, 2001.
• [9] Euler L. Institutiones Calculi Differentialis. St. Petersburg, 1775, pp. 485-487.
• [10] Weron A., Burnecki K., Weron K., Mercik Sz. Complete description of all self-similar models driven by Lévy stable noise. Phys. Rev. E 71, 2005, p. 016113.
• [11] Kołmogorov A. N. Wienersche Spiralen und einige interessante Kurven in Hilbertschen Raum. Acad. Sci. USSR, 28, 1940, pp. 115-118.
• [12] Mandelbrot B., Van Ness J. Fractional Brownian motions, fractional noises and applications. SIAM Rev., vol. 10, 1998, pp. 422-437.
• [13] Hurst H. E. Long-term storage capacity of reservoirs. Trans. Am. Soc. Civil Eng., vol. 116, 1951, pp. 770-799.
• [14] Mandelbrot B. Fractal Geometry of Nature, WH Freeman, 1982.
• [15] Weron A., Weron R. Inżynieria finansowa. WNT, Warszawa, 2005.
• [16] Janicki A., Weron A. A Simulation and Chaotic Behavior of –Stable Stochastic Processes. Marcel Dekker Inc., New York, 1994.
• [17] Mercik Sz. Ułamkowy ruch Browna jako model transportu jonów potasu przez kanały jonowe w błonie komórkowej, Ph.D. Thesis, Instytut Fizyki, PW, Wrocław, 2001.
• [18] Mantegna R. N., Palágyi Z., Stanley H. E. Applications of statistical mechanics to finance., Physica A 274, 1999, pp. 216-221.
• [19] Kulczycki P. Estymatory jądrowe w analizie systemowej. WNT, Warszawa, 2005.
• [20] Grabowski F., Strzałka D. Dynamic behavior of simple insertion sort algorithm. Fundamenta Informaticae 72, IOS Press, 2006, pp. 155-165.
• [21] Descartes R. Discourse de la Methode, ed. By Donald Cress, Hackett Pub Co Inc; 1999.
• [22] Arystoteles Metafizyka. przeł. K. Żeleźnik, Lublin, 1996.
• [23] Mertens S. Computational Complexity for Physicists. Computing in Science and Engineering, vol. 4 (3), (2000), pp. 31-47.
• [24] 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.