20.500.12556/DKUM-86779 Graph theory approaches to maturity models master thesis Obravnava zrelostnih modelov s pristopi iz teorije grafov. study programme 2nd degree Mathematics The masters thesis, which follows the paper Graph drawing applications in combinatorial theory of maturity models, in preparation, coauthored by the author of the thesis, introduces the tiled graphs as models of learning and maturing processes. In the thesis, we show how tiled graphs can combine graphs of learning spaces or antimatroids (partial cubes) and maturity models (total orders) to yield models of learning processes. We visualise processes with optimal drawings. In the thesis, we show NP-hardness of visualisation problems resulting from most detailed models. Further, we introduce a simpler model, which ignores the details of learning and for which the visualisation problem can be solved in a polynomial time. For the rest of the thesis, we consider this model. We describe an algorithm, which finds a drawing of an ordinal panel data graph with a minimal number of edge crossings. For this problem we further define an extremal crossing number for a chosen family of ordinal panel data. Further, we explore a certain type of random instances of ordinal panel data and the expected value of a crossing number for this type of random instances. After that, we define a problem of finding the most suitable ordering on categories in panel data, in other words finding the best maturity model to fit the data. We prove the NP-hardness of the problem and formulate an integer linear program. Master thesis consists of nine chapters. The first chapter contains known results and definitions from set and graph theory and a section of computational complexity theory (NP-hardness), which will be used throughout the thesis. The following chapters present the new theory introduced in the aforementioned paper in preparation and the needed additional results and definitions. In the last chapter we present the thesis and some selected parts of the thesis with the help of learning space theory. The chapter serves as both the overview of the thesis and the use case for the theory of learning spaces, presented in the thesis. Magistrsko delo, ki sledi članku Graph drawing applications in combinatorial theory of maturity models v pripravi, čigar soavtorica je avtorica dela, predstavlja tlakovane grafe kot modele učnih in zrelostnih procesov. V delu pokažemo kako lahko tlakovani grafi povežejo grafe učnih procesov (delne kocke) in zrelostnih modelov (popolna urejenost) z namenom modeliranja učnega procesa. Procese vizualiziramo z optimalnimi risbami, pri čemer pokažemo NP-polnost problemov vizualizacije večine natančnejših modelov. Podamo preprostejši model, ki ignorira podrobnosti učenja in za katerega je problem vizualizacije rešljiv v polinomskem času. V nadaljevanju magistrskega dela se osredotočimo na ta model. Opišemo algoritem, ki poišče risbo grafa ordinalnih panelnih podatkov z najmanjšim številom križanj povezav. Nadalje uvedemo problem ekstremalnega prekrižnega števila ter poiščemo ekstremalno prekrižno število za izbrano družino ordinalnih panelnih podatkov. Nato raziščemo družino naključnih primerkov ordinalnih panelnih podatkov in raziščemo pričakovano vrednost prekrižnega števila primerkov tega tipa. V nadaljevanju definiramo problem najustreznejše urejenosti kategorij v panelnih podatkih, z drugimi besedami problem iskanja panelnim podatkom najustreznejšega zrelostnega modela, dokažemo njegovo NP-polnost in ga formuliramo kot linearni celoštevilski program. Delo je sestavljeno iz devetih poglavij. V uvodnem poglavju podamo znane definicije in rezultate iz področij teorije množic, teorije grafov ter sekcije o NP-polnosti iz področja teorije računske kompleksnosti, ki se bodo uporabljali tekom magistrskega dela. V nadaljnjih poglavjih predstavimo novo teorijo, vpeljano v zgoraj omenjenem članku, ter potrebne rezultate in definicije, povezane s to teorijo. V zadnjem poglavju predstavimo magistrsko delo ter nekatere izbrane dele s pomočjo učnih prostorov. Poglavje služi kot pregled dela, prav tako pa tudi kot primer uporabe predstavljene teorije učnih prostorov. Maturity models learning spaces crossing number crossing minimisation tile crossing number. Zrelostni modeli učni prostori prekrižno število minimiziranje križanj tlakovsko prekrižno število. true true false Š. Kajzer Angleški jezik Slovenski jezik Magistrsko delo/naloga 2024-01-18 08:42:30 2024-03-14 14:29:54 2024-03-15 03:17:00 0000-00-00 00:00:00 2024 0 Maribor 0 Maribor 114 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17:519.85(043.2) 188712195 MAG_Kajzer_Spela_2024.pdf MAG_Kajzer_Spela_2024.pdf 1 388C880501FE16BF252923122D8E1A4D 0df7977a57f6727c0416756f4bf232bdfd947f59b12a92391e319bb83743fd5a 4a3adfb5-b5da-11ee-9c45-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=175381 Fakulteta za naravoslovje in matematiko 0 0 0