'Algoritmer til løsning af ubegrænsede influensdiagrammer på begrænset plads'
Oversat titel
Forfattere
Semester
4. semester
Uddannelse
Udgivelsesår
2006
Afleveret
2012-02-14
Abstract
'Ubegrænsede influensdiagrammer (UIDer) er blevet introduceret som en generalisering af influensdiagrammer, hvor kravet fra influensdiagrammer, om at alle beslutninger skal være ordnet i forhold til hinanden, er blevet ophævet. Således er UIDer velegnede til at repræsentere problemer, hvor ordningen af beslutningerne ikke eller kun delvist er fastlagt, dvs. ordningsasymmetriske beslutningsproblemer. En algoritme, der kan tilbyde en afvejning mellem tid og plads ved løsning af UIDer, opstilles og aftestes empirisk. Den opstillede algoritme er baseret på konditionering og opnår afvejningen mellem tid og plads ved indførelse af cache. Sammen med algoritmen opstilles øvre grænser for algoritmens tids- og pladskompleksitet i grænserne, hvor der er plads til fuld cache, og hvor der ikke er plads til cache. I grænsen, hvor der ikke er plads til cache, vokser algoritmens pladsforbrug (ud over en given basisallokering) lineært med antallet af knuder i UIDet. Der opstilles ligeledes en formel til estimering af kørselstiden ved en given mængde plads.'