Knowledge base: Warsaw University of Technology

Settings and your account

Back

Randomness propagation in the cellular automata dynamics

Mateusz Niewiadomski

Abstract

The aim of this paper was to analyze the simplest two-state and one-dimensional cellular automata with long-range interactions between their cells. The research problem was an attempt to answer the question about the number of orbits of the automaton depending on the choice of dynamics and how (in the probabilistic sense) these orbits differ from each other. Various dynamics will be tested for their usability as pseudorandom number generators. Individual dynamics have been described in a theoretical way in terms of propagation and the increase of complexity of cells states dependency during their evolution in time. Basic differences between the dynamics and their possible influence on the propagation of randomness were shown. Simulations for various dynamics were performed, and the numbers generated by the machine were statisticly tested pseudo-randomness. Parameters such as the entropy of the system or the density of orbits were examined. From the created states a visualization was made showing time evolution and dependencies between consecutive automata states.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Mateusz Niewiadomski (FP) Mateusz Niewiadomski,, Faculty of Physics (FP)
Title in Polish
Propagacja przypadkowości w dynamice automatów komórkowych
Supervisor
Grzegorz Siudem (FP/PCSD) Grzegorz Siudem,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP)
Certifying unit
Faculty of Physics (FP)
Affiliation unit
Physics of Complex Systems Divison (FP/PCSD)
Study subject / specialization
, Fizyka Techniczna
Language
(pl) Polish
Status
Finished
Defense Date
14-02-2019
Issue date (year)
2019
Reviewers
Maciej Mrowiński (FP/PCSD) Maciej Mrowiński,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP) Grzegorz Siudem (FP/PCSD) Grzegorz Siudem,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP)
Keywords in Polish
automaty komórkowe, generator liczb pseudolosowych, układy złożone
Keywords in English
cellular automata, pseudorandom number generator, complex system
Abstract in Polish
Celem pracy była analiza najprostszych, dwustanowych i jednowymiarowych automatów komórkowych, posiadających dalekozasięgowe oddziaływania pomiędzy swoimi komórkami. Problemem badawczym była próba odpowiedzi na pytanie o liczbę orbit automatu w zależności od wyboru dynamiki oraz o to, czym (w sensie probabilistycznym) różnią się od siebie te orbity. Automaty dla różnych dynamik zostaną przebadane pod kątem swojej jakości jako generatory liczb pseudolosowych. Poszczególne dynamiki zostały opisane w sposób teoretyczny pod kątem propagacji i narastania złożoności pomiędzy komórkami w trakcie ewolucji czasowej. Wykazano podstawowe różnice pomiędzy dynamikami i ich możliwy wpływ na propagacje przypadkowości. Automat komórkowy zaimplementowano w sposób pozwalający na modyfikowanie jego podstawowych parametrów. Wybrano różne środowiska programistyczne najlepiej spełniające oczekiwane funkcje: C++ do szybkiego wykonywania reguł automatu, Java do prostej wizualizacji ewolucji stanów oraz środowisko ROOT do statystycznej analizy danych uzyskanych w eksperymencie. Wykonano symulacje działania automatu dla różnych dynamik, a wygenerowane przez automat stany przebadano pod kątem statystycznej pseudolosowości. Zbadano takie parametry jak entropia układu czy gęstość orbit w przestrzeni fazowej stanów. Z wygenerowanych stanów automatu stworzono też wizualizację prezentującą naocznie ewolucję czasową automatu.
File
  • File: 1
    Praca_Inżynierska_Mateusz_Niewiadomski.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 27239

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT184edf85a39949999a93072daa570c5c/
URN
urn:pw-repo:WUT184edf85a39949999a93072daa570c5c

Confirmation
Are you sure?
Report incorrect data on this page