Provider: - Institution: - Data provided by Europeana Collections- In this work some actual combinatorial optimization problems are investigated. Several different methods are suggested for solving the following NP hard problems: maximally balanced connected partition problem in graph, general maximally balanced problem with q partitions ( q ≥ 2), maximum set splitting problem and p-ary transitive reduction problem in digraphs. Together with investigation of combinatorial optimization methods for solving these problems, the applying of these problems in education is also considered in the dissertation. For solving each of these problems, metaheuristics are developed: variable neighborhood search is developed for each problem and genetic algorithm is used for solving p-ary transitive reduction problem in digraphs. For maximally balanced connected partition problem a mixed linear programming model is established, which enables to solve the problem exactly for the instances of lower dimensions. Achieved numerical results indicate the high level of reliability and usability of the proposed methods. Problems solved in this research are of a great interest both in theoretical and practical points of view. They are used in production, computer networks, engineering, image processing, biology, social sciences and also in various fields of applied mathematics and computer science. In this work the applying of some problems in educational issues is also considered. It is shown that approaches of finding maximally balanced connected partition in graph and finding maximum splitting of the set can be successfully used in course organization, which is verified on the concrete examples. Based on the objective indicators and professor's assessment, the techniques for the identifying the connections between the lessons, as well as the weights of the lessons are developed. Thus, whole course can be represented as a connected weighted graph, enabling the resolving of the lesson partition problem by mathematical approaches. By assigning the lessons into the appropriate categories (topics area) inside a iv course, a collection of subsets (corresponding to the topics) of the set of lessons is created. If we set the requirement that lessons should be split into two disjoint subsets (e.g. into the winter and summer semesters), in a way that corresponding topics are processed in both subsets, then the mathematical model of the requirement and its solution corresponds to the set splitting problem. By the developed models of course organization, from which the NP hard problems arise, in addition to the scientific contributions in the fields of mathematical programming and operational research, contributions in educational aspects are added, especially in the methodology of teaching mathematics and computer science.- U ovom radu se istražuju neki aktuelni problemi kombinatorne optimizacije. Analizirane su i predstavljene različite metode rješavanja sljedećih NP teških problema: problem pronalaženja maksimalne povezane particije, uopšteni problem pronalaženja maksimalno balansirane povezane particije u grafu sa q particija (q ≥ 2), problem pronalaženja podjele skupa na dvije particije i problem pronalaženja p-arne tranzitivne redukcije u digrafu. Zajedno sa istraživanjem metoda kombinatorne optimizacije, kojima se rješavaju navedeni problemi, u disertaciji se istražuje i mogućnost primjene nekih od navedenih problema kombinatorne optimizacije u organizaciji nastave. Za svaki od ovih problema prikazane su metaheuristike za njihovo rješavanje: metod promjenljivih okolina je razvijen za sva četiri problema, dok je za problem tranzitivne redukcije u digrafu razvijen i genetski algoritam. Za problem maksimalno balansirane povezane particije u grafu je razvijen i model mješovitog cjelobrojnog linearnog programiranja, koji omogućava pronalaženje tačnog rješenja za instance manjih dimenzija. Dobijeni eksperimentalni rezultati ukazuju na visoku upotrebnu vrijednost svih razvijenih metoda. Problemi koji su rješavani u ovom radu su od velikog teorijskog i praktičnog značaja. Koriste se u proizvodnji, oblastima računarskih mreža, inžežerstvu, obradi slika, biologiji, društvenim naukama, a takođe i u oblastima primijenjene matematike i računarstva. U radu je razmatrana primjena nekih od navedenih problema u organizaciji nastave. Pokazalo se da se pronalaženja maksimalno balansirane povezane particije u grafu i problem pronalaženja podjele skupa na dvije particije uspješno mogu primijeniti u ogranizaciji planova i programa, kako je to prikazano i na konkretnim primjerima. Razvijene su tehnike za načine povezivanja lekcija, kao i za određivanje njihovih težina, zasnovanih na objektivnim pokazateljima i subjektivnim procjenama profesora. Time je postignuto da se čitav kurs predstavi kao povezan težinski graf, što pruža mogućnost da se problem podjele lekcija unutar kursa posmatra i rješava kao matematički problem. Pridruživanjem lekcija odgovarajućim kategorijama (tematskim cjelinama) unutar jednog kursa, kreira se familija podskupova (tematskih cjelina) čitavog skupa lekcija. Ako pretpostavimo da lekcije kursa treba razbiti u dva disjunktna podskupa (na primjer na zimski i ljetnji semestar), tako da što više tematskih cjelina bude "pokriveno" u oba ta podskupa, tada se navedeni problem svodi na rješavanje problema maksimalne podjele skupa. Razvijenim modelima u organizaciji nastave, iz kojih nastaju NP teški problemi, ovom radu je, pored naučnog doprinosa u polju matematičkog programiranja i operacionih istraživanja, pridodat i doprinos iz oblasti metodologije nastavnog procesa, sa naglaskom na metodologiju nastave matematike i računarstva.- All metadata published by Europeana are available free of restriction under the Creative Commons CC0 1.0 Universal Public Domain Dedication. However, Europeana requests that you actively acknowledge and give attribution to all metadata sources including Europeana