Title
Метод седиментације и његове примјене у проблемима дискретне математике
Creator
Kordić, Stevan Lj., 1969-
Copyright date
2016
Object Links
Select license
Bez licence - direktna primena zakona
License description
Ako ne izaberete neku od licenci, vaše zaštićeno delo može biti korišćeno samo u okviru opštih ograničenja autorskih prava. Na taj način ne dozvoljavate komercijalno ni nekomercijalno korišćenje, naročito reprodukciju, distribuciju, emitovanje, dostupnost i obradu dela. Izbor Creative Commons (CC) licence promoviše diseminaciju vašeg dela. Za više informacija: http://creativecommons.org.rs/licence
Language
Serbian
Cobiss-ID
Committee report
Theses Type
Doktorska disertacija
description
Datum odbrane: 20.07.2016.
Other responsibilities
mentor
Mijajlović, Žarko, 1948-
član komisije
Davidović, Tatjana, 1964-
član komisije
Janičić, Predrag, 1968-
University
Univerzitet u Beogradu
Faculty
Matematički fakultet
Alternative title
Method of sedimentation and its discrete mathematics applications
Publisher
[С. Кордић]
Format
XI, 130 листова
description
Математика - Дискретна математика / Mathematics - Discrete mathematics
Abstract (sr)
Проблеми задовољења ограничења, којима припадају и проблеми оптимизације,
спадају у веома значајне проблеме дискретне математике са широким пољем
употребе у математици и њеним примјенама.
Дисертација разматра проблем оптимизације и предлаже оригиналан метод за
његово тачно рјешавање. Назив алгоритма који се приказује у тези је метод
седиментације и приказан је заједно са двије своје хеуристике. Спада у класу
алгоритама „гранања и ограничавања“, који користе механизме „враћања по
трагу“ и „провјере унапријед“. Доказана је његова тотална коректност методе
седиментације.
Као илустрација примијенљивости методе седиментације, у дисертацији су
разматране примјене ове методе на проблеме исказне задовољивости, Вајтхедов проблем минимизације и проблем додјеле везова бродовима у контејнерским лукама. Најбоље резултате метода је показала рјешавајући проблеме
додјеле везова, јер је моделовање овог проблема за рјешавање методом седиментације укључивало све оптимизацијске технике, којима метода располаже.
Такође, за проблем додјеле везове, утврђена је прецизна оцјена комплексности
методе седиментације. Експериментални резултати потврђују да метода седиментације може да рјешава проблеме додјеле везова на нивоу најбољих приступа овом проблему.
Abstract (en)
Constrain satisfaction problems including the optimisation problems are among the
most important problems of discrete mathematics with wide area of application
in mathematics itself and in the applied mathematics.
Dissertation study optimisation problem and presents an original method for
finding its exact solution. The name of the method is Sedimentation Algorithm,
which is introduced together with two heuristics. It belongs to the class of
branch-and-bound algorithms, which uses backtracking and forward checking
techniques. The Sedimentation Algorithm is proven to be totally correct.
Ability of the Sedimentation Algorithm to solve different type of problems is
demonstrated in dissertation by its application on the Boolean satisfiability problems,
the Whitehead Minimisation Problem and the Berth Allocation Problem in
container port. The best results are obtained for Berth Allocation Problem, because
its modelling for Sedimentation Algorithm includes all available optimisation
techniques of the method. The precise complexity estimation of the Sedimentation
Algorithm for the Berth Allocation Problem is established. Experimental
results verify that the Sedimentation Algorithm is capable to solve the
Berth Allocation Problem on the state of art level.
Authors Key words
проблем задовољења ограничења, проблем оптимизације, дискретна матема-
тика, комбинаторна оптимизација, тачно рјешење, алгоритам, буловска задо-
вољивост, Вајтхедов проблем минимизације, проблем додјеле везова
Authors Key words
constrain satisfaction problem, optimisation problem, discrete mathematics, combinatorial
optimisation, exact solution, algorithm, Boolean satisfiability, Whitehead
minimisation problem, berth Allocation problem
Classification
51-7(043.3)
Type
Tekst
Abstract (sr)
Проблеми задовољења ограничења, којима припадају и проблеми оптимизације,
спадају у веома значајне проблеме дискретне математике са широким пољем
употребе у математици и њеним примјенама.
Дисертација разматра проблем оптимизације и предлаже оригиналан метод за
његово тачно рјешавање. Назив алгоритма који се приказује у тези је метод
седиментације и приказан је заједно са двије своје хеуристике. Спада у класу
алгоритама „гранања и ограничавања“, који користе механизме „враћања по
трагу“ и „провјере унапријед“. Доказана је његова тотална коректност методе
седиментације.
Као илустрација примијенљивости методе седиментације, у дисертацији су
разматране примјене ове методе на проблеме исказне задовољивости, Вајтхедов проблем минимизације и проблем додјеле везова бродовима у контејнерским лукама. Најбоље резултате метода је показала рјешавајући проблеме
додјеле везова, јер је моделовање овог проблема за рјешавање методом седиментације укључивало све оптимизацијске технике, којима метода располаже.
Такође, за проблем додјеле везове, утврђена је прецизна оцјена комплексности
методе седиментације. Експериментални резултати потврђују да метода седиментације може да рјешава проблеме додјеле везова на нивоу најбољих приступа овом проблему.
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.