Automatizacija postupka određivanja redoslijeda razvoja podsustava informacijskog sustava

doctoral thesis

• Title (english): Automatic determination of information system subsystems development order
• Author: Robert Kudelić; MBZ: 318731
• Mentor: Alen Lovrenčić (mentor); MBZ: 218662
• Committee member: Neven Vrček (predsjednik povjerenstva); MBZ: 218614
• Committee member: Robert Manger (član povjerenstva); MBZ: 93880
• Committee member: Zdravko Dovedan Han (član povjerenstva); MBZ: 151654
• Committee member: Mirko Čubrilo (član povjerenstva); MBZ: 135963
• Committee member: Alen Lovrenčić (član povjerenstva); MBZ: 218662
• Granter: University of Zagreb; Faculty of Organization and Informatics; Varaždin
• Defense date and country: 2015-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: SOCIAL SCIENCES; Information and Communication Sciences
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

Prilikom razvoja informacijskog sustava potrebno je odrediti slijed razvoja podsustava informacijskog sustava. Ovaj problem trenutno nije formalno riješen. Stoga predlažemo rješenje koje će kao kriterij, određivanja slijeda razvoja podsustava informacijskog sustava, imati sumu težina povratnih lukova u slijedu podsustava informacijskog sustava. Nadalje, dokazali smo kako je ovaj problem NP-potpun, NP-težak, i APX-težak. Isto tako, kako bismo riješili ovaj problem osmislili smo: algoritam temeljen na metodi Grananja i ograničenja, Monte Carlo randomizirani algoritam, i heuristički algoritam. Za sva tri algoritma smo procijenili složenost. Sva tri algoritma su implementirana i empirijski testirana. Na kraju smo pokazali na koji način se u praksi, po potrebi, mogu uvrštavati dodatna ograničenja, i gdje se još osmišljeni algoritmi potencijalno mogu koristiti.

Abstract (english)

When we are developing Information System we must determine development order of its subsystems. Currently, this problem is not formally solved. Therefore, we have proposed a solution which takes sum of weights of feedback arcs as a criteria for determining development order of Information System subsystems. Furthermore, we have proved that the problem of Information System Subsystems Development Order is NP-complete, NP-hard, and APX-hard. Also, in order to solve this problem we have created: Branch and Bound algorithm, Monte Carlo randomized algorithm, and heuristic algorithm. Complexity has been calculated for all three algorithms. All three algorithms have been implemented and empirically analysed. Lastly, we have showed how one can apply additional constraints upon the problem of Information System Subsystems Development Order, and where can one potentially use developed algorithms outside of Information System Subsystems Development Order problem.

• Keywords: slijed čvorova; informacijski sustav; suma težina povratnih lukova; usmjereni ciklički graf; metoda grananja i ograničenja; monte carlo randomizacija; heuristika; np-težak; np-potpun; apx-težak; algoritmi; složenost; uvrštavanje dodatnih ograničenja; primjena na ostale probleme
• Keywords (english): sequence of nodes; Information System; sum of weights of feedbackarcs; Directed Cyclic Graph; Branch and Bound method; Monte Carlo randomization; heuristics; NP-hard; NP-complete; APX-hard; algorithms; complexity; applying additionalconstraints; application on other problems
• Language: croatian
• URN:NBN: urn:nbn:hr:211:622433
• Study programme: Title: Postgraduate doctoral study in Information Science; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica znanosti, područje društvenih znanosti, polje informacijske i komunikacijske znanosti (doktor/doktorica znanosti, područje društvenih znanosti, polje informacijske i komunikacijske znanosti)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Repository: Faculty of Organization and Informatics - Digital Repository
• Created on: 2017-01-23 14:20:40