Implementacija, evaluacija te trenutni limiti algoritma uzročnog dekonvoluiranja podataka i mreža

undergraduate thesis

• Title (english): Implementation, evaluation and current limits of the causal deconvolution algorithm of data and networks
• Author: Nikola Marić
• Mentor: Mario Brčić (mentor)
• Committee member: Mario Brčić (predsjednik povjerenstva)
• Committee member: Mihael Kovač (član povjerenstva)
• Committee member: Kristijan Poje (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-05, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu istraženi su i implementirani algoritmi za uzročno dekonvoluiranje podataka i mreža, koristeći metodologije temeljene na algoritamskoj teoriji informacija. Cilj je bio razviti alate za procjenu algoritamske složenosti i dekonvoluciju podataka s posebnim naglaskom na njihove trenutne limite.

Predložene metode uključuju Metodu teorema kodiranja (CTM) i Metodu dekompozicije blokova (BDM). Eksperimenti su provedeni na različitim tipovima podataka, uključujući ručno pisane nizove, sintetički generirane nizove i nizove generirane elementarnim celularnim automatima. Rezultati pokazuju da algoritmi mogu teorijski uspješno razdvojiti složene podatke na osnovne komponente, ali također ističu izazove u razvoju učinkovitih algoritama, posebice kod duljih nizova.

Posebno je analiziran problem rukovanja granicama objekata u BDM metodi, gdje je predložena nova metoda za kompenzaciju ostatka pokazala poboljšanja u točnosti procjene algoritamske složenosti. Unatoč postignutim napretcima, daljnje istraživanje i razvoj naprednijih algoritama ostaje nužno za postizanje optimalnih rezultata i bolje razumijevanje složenih sustava.

Abstract (english)

This thesis explores and implements algorithms for causal deconvolution of data and networks, utilizing methodologies based on algorithmic information theory. The aim was to develop tools for assessing algorithmic complexity and data deconvolution, with a particular focus on their current limitations.

The proposed methods include the Coding Theorem Method (CTM) and the Block Decomposition Method (BDM). Experiments were conducted on various types of data, including hand-written sequences, synthetically generated sequences, and sequences generated by elementary cellular automata. The results indicate that the algorithms can theoretically successfully deconvolve complex data into their fundamental components, but also highlight the challenges in developing effective algorithms, especially for longer sequences.

A particular focus was placed on the issue of handling object boundaries in the BDM method. A new method for remainder compensation was proposed, showing improvements in the accuracy of algorithmic complexity estimation. Despite the advances made, further research and development of more advanced algorithms is necessary to achieve optimal results and a better understanding of complex systems.

• Keywords: uzročno dekonvoluiranje; algoritamska složenost; Kolmogorovljeva složenost; metoda teorema kodiranja; metoda dekompozicije blokova; kompleksnost podataka
• Keywords (english): causal deconvolution; algorithmic complexity; Kolmogorov complexity; coding theorem method; block decomposition method; data complexity
• Language: croatian
• URN:NBN: urn:nbn:hr:168:910349
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 21:26:37