Automati grafova primarni su problem istraživanja ove disertacije. U teoriji automata postoji cijeli niz praktičnih problema koji se mogu jednostavnije riješiti, odnosno modelirati, upotrebom grafova. Fokus naše analize automata na grafovima bit će na ekstremalnim problemima kombinatorne optimizacije. Ugrubo, graf se može predstaviti kao familija točaka, koje nazivamo vrhovima, zajedno sa spojnicama između tih točaka, koje nazivamo bridovima. Zbog svoje jednostavnosti i dobrih iskustava primjene u medicini i biologiji, (bio)kemiji, (bio)fizici i (bio)informatici nama su posebno bili zanimljivi takozvani celularni ili stanični (ćelijski) automati, odnosno zasebna klasa – stanični automati smrzavanja. Nadalje, zbog svoje važnosti pri analiziranju i predviđanju svojstava peptida, također su nam zanimljive ljestvice aminokiselina. Stoga će drugi fokus ove doktorske disertacije biti na konstrukciji (pronalaženju) manjeg, ali još uvijek reprezentativnog, skupa ljestvica aminokiselina. Koristit ćemo metodu pretrage promjenjivom okolinom, relativno nedavno razvijenu metaheuristiku. – Graph automata are the primary research problem of this dissertation. In automata theory, there is a whole series of practical problems that can be more easily solved, or modeled, using graphs. The focus of our analysis of automata on graphs will be on extremal combinatorial optimization problems. Roughly, a graph can be represented as a family of points, which we call vertices, together with the connections between these points, which we call edges. Because of their simplicity and good experiences of application in medicine and biology, (bio)chemistry, (bio)physics and (bio)informatics, so-called cellular automata were especially interesting to us, that is, a special class – freezing cellular automata. Furthermore, because of their importance in analyzing and predicting the properties of peptides, we also find amino acid scales interesting. Therefore, the second focus of this doctoral dissertation will be on the construction (finding) of a smaller, but still representative, set of amino acid scales. We will use the variable neighborhood search method, a relatively recently developed metaheuristic.