Rešavanje nekih problema u nastavi primenom metoda kombinatorne optimizacije

eBiblioteka

 
 

Rešavanje nekih problema u nastavi primenom metoda kombinatorne optimizacije

Show simple item record

dc.contributor.advisor Filipović, Vladimir
dc.contributor.author Matić, Dragan
dc.date.accessioned 2013-10-08T09:58:49Z
dc.date.available 2013-10-08T09:58:49Z
dc.date.issued 2013
dc.identifier.uri http://hdl.handle.net/123456789/3050
dc.description.abstract In this work some actual combinatorial optimization problems are investigated. Several di erent 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 elds 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 nding maximally balanced connected partition in graph and nding maximum splitting of the set can be successfully used in course organization, which is veri ed 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 scienti c contributions in the elds of mathematical programming and operational research, contributions in educational aspects are added, especially in the methodology of teaching mathematics and computer science. en_US
dc.description.provenance Submitted by Slavisha Milisavljevic (slavisha) on 2013-10-08T09:58:49Z No. of bitstreams: 1 phd_matic_dragan.pdf: 1438102 bytes, checksum: 603067dbe51a5291b3eb6677059078ed (MD5) en
dc.description.provenance Made available in DSpace on 2013-10-08T09:58:49Z (GMT). No. of bitstreams: 1 phd_matic_dragan.pdf: 1438102 bytes, checksum: 603067dbe51a5291b3eb6677059078ed (MD5) Previous issue date: 2013 en
dc.format.mimetype PDF en_US
dc.language.iso sr en_US
dc.publisher Beograd en_US
dc.title Rešavanje nekih problema u nastavi primenom metoda kombinatorne optimizacije en_US
mf.author.birth-date 1977-08-23
mf.author.birth-place Sremska Mitrovica en_US
mf.author.birth-country Srbija en_US
mf.author.residence-state Srbija en_US
mf.author.citizenship Srpsko en_US
mf.author.nationality Srpsko en_US
mf.subject.area Matematika en_US
mf.subject.keywords combinatorial optimization, mixed integer linear programming, metaheuristics en_US
mf.subject.subarea Metodika nastave matematike i računarstva en_US
mf.contributor.committee Tošić, Dušan
mf.contributor.committee Božić, Milan
mf.contributor.committee Lalović, Ilija
mf.contributor.committee Savić, Aleksandar
mf.university.faculty Mathematical en_US
mf.document.references 106 en_US
mf.document.pages 107 en_US
mf.document.location Belgrade en_US
mf.document.genealogy-project No en_US
mf.university Belgrade en_US

Files in this item

Files Size Format View
phd_matic_dragan.pdf 1.438Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record