Zum Inhalt

Com­pu­ter­feh­ler ein­fach wegrechnen

In einem vom Wis­sen­schafts­fonds FWF finan­zier­ten Pro­jekt wer­den schnelle mathe­ma­ti­sche Ana­ly­se­me­tho­den ent­wi­ckelt, um die Sicher­heit von Com­pu­ter­pro­gram­men und Hard­ware zu erhöhen.

Com­pu­ter­me­tho­den für Soft­ware-Tests gibt es schon lange, jedoch wuchs die Kom­ple­xi­tät der Pro­gramme in den ver­gan­ge­nen Jah­ren ste­tig, wäh­rend die Leis­tungs­fä­hig­keit der Test­me­tho­den hin­ter­her­hinkte, ins­be­son­dere was ihre Geschwin­dig­keit angeht. Der Com­pu­ter­wis­sen­schaf­ter Krish­nendu Chat­ter­jee beschäf­tigte sich in einem vom Wis­sen­schafts­fonds FWF finan­zier­ten Pro­jekt mit der Ana­lyse von Com­pu­ter­sys­te­men mit­tels mathe­ma­ti­scher Metho­den, die Soft­ware­tests signi­fi­kant beschleu­ni­gen sollen.

Anwen­dung der Gra­phen­theo­rie
Für die mathe­ma­ti­sche Ana­lyse von Com­pu­ter­sys­te­men wird die soge­nannte „Gra­phen­theo­rie“ genutzt. Ihr Gegen­stand sind Objekte, die man sich als Netz­werke aus mit­ein­an­der ver­bun­de­nen Punk­ten oder Kno­ten vor­stel­len kann. Com­pu­ter­sys­teme las­sen sich mathe­ma­tisch als Gra­phen dar­stel­len: Ein Kno­ten steht für einen bestimm­ten Zustand, in dem sich das Sys­tem befin­det, eine Kante steht für einen Über­gang zwi­schen zwei Zustän­den.
Die­ser Rah­men ist beson­ders geeig­net für die Prü­fung von Com­pu­ter­sys­te­men. Gemein­sam mit Pro­jekt­part­ne­rin Monika Hen­zin­ger von der Uni­ver­si­tät Wien unter­suchte er, wie die Metho­den der Gra­phen-Algo­rith­men adap­tiert und erwei­tert wer­den müs­sen, um wirk­lich bes­sere Algo­rith­men für die Pro­bleme zu bekom­men, die in kom­ple­xen Com­pu­ter­sys­te­men von heute ent­ste­hen können.

Geschwin­dig­keits­schran­ken durch­bro­chen
Es gelang, meh­rere seit den Neun­zi­ger­jah­ren bestehende Schran­ken für die Geschwin­dig­keit bestimm­ter Veri­fi­ka­ti­ons­al­go­rith­men zu durch­bre­chen, etwa im Bereich soge­nann­ter „Mar­kov Decis­ion Pro­ces­ses“. Das sind Modelle, die meh­rere Aus­wahl­mög­lich­kei­ten und ein Zufalls­ele­ment beinhal­ten. „Ein Bei­spiel ist die Ent­wick­lung von Robo­tern“, erklärt Chat­ter­jee. „Ein Robo­ter inter­agiert mit einer Umge­bung, in der es Unsi­cher­heit gibt, und er hat Aus­wahl­mög­lich­kei­ten, kann etwa nach links oder rechts gehen.“
Für viele Anwen­dun­gen ist die Beant­wor­tung der Frage zen­tral, wel­che Ereig­nisse in so einem Modell mit abso­lu­ter Sicher­heit ein­tre­ten. „Der bis­her effi­zi­en­teste Algo­rith­mus dafür war aus 1995 und hatte qua­dra­ti­sche Kom­ple­xi­tät“, sagt Chat­ter­jee. Damit ist gemeint, dass etwa ein dop­pelt so gro­ßes Sys­tem die vier­fa­che Lauf­zeit benö­tigt. „In unse­rem Pro­jekt konn­ten wir diese Grenze mit Graph-algo­rith­mi­schen Tech­ni­ken über­win­den.“ In einem Fol­ge­pro­jekt will Chat­ter­jee nun unter ande­rem unter­su­chen, wie sich die neuen Erkennt­nisse in der Pra­xis umset­zen lassen. 

Autor: red
14.02.2017

Weitere aktuelle Artikel

Der Mer­ce­des im Mund. Nach KI-Ein­satz in der Zahn­be­hand­lung, gibt es nun auch Fort­schritte beim Thema Zahn­ersatz. Die TU Wien star­tet ein neues Chris­tian Dopppler-Labor zur Erfor­schung neuer Mate­ria­lien für bes­sere Zahn­fül­lun­gen und Zahnprothesen. Wenn man schon eine Zahn­fül­lung braucht, dann soll sie rasch ein­ge­setzt wer­den kön­nen und lange hal­ten. Aus mate­ri­al­wis­sen­schaft­li­cher und behand­lungs­tech­ni­scher Sicht […]
Trotz rück­läu­fi­ger Umsätze inves­tie­ren Öster­reichs bör­sen­no­tierte Unter­neh­men wei­ter stark in For­schung und Ent­wick­lung. Im Ver­gleich liegt IT-Bran­che an der Spitze. Bei Unter­neh­men füh­ren ams-Osram, Kon­tron und voest­al­pine sowie Kapsch, Faba­soft und AT&S. Öster­reichs Top-Unter­neh­men hal­ten trotz wirt­schaft­li­cher Her­aus­for­de­run­gen an ihren Inno­va­ti­ons­ak­ti­vi­tä­ten fest. Der Gesamt­um­satz der aktu­ell von EY unter­such­ten bör­sen­no­tier­ten Top-30-Unter­neh­men sank 2025 bereits das […]
Die Alfred Korn­ber­ger Foun­da­tion eröff­net in Wie­ner Bäcker­strasse 9 museale Schau­räume mit Schwer­punkt auf Expres­sio­nis­mus und Akt. Museum, Art-Shop & Gale­rie haben geöff­net von Di bis Fr: 11–18 und Sa: 10–13 Uhr. Die Eröff­nungs­aus­stel­lung „Der ero­ti­sche Moment“ mit retro­spek­ti­ver Werk­schau von Akt­mo­ti­ven aus dem Bestand von Alfred Korn­ber­ger-Foun­da­tion und Fami­lie.Die Alfred Korn­ber­ger Foun­da­tion eröff­net in der Wie­ner Bäcker­strasse […]
Eine neue Gene­ra­tion von MRT-Gerä­ten erlaubt in der bild­ge­ben­den Medi­zin schnel­lere und bes­sere Unter­su­chun­gen mit mehr Kom­fort für Pati­en­ten. Die Inns­bru­cker Uni­kli­nik setzt nun auf diese moder­nen Systeme. Höhere Bild­qua­li­tät, kür­zere Unter­su­chungs­zei­ten, moderne Soft­ware-Unter­stüt­zung und mehr Kom­fort für Pati­en­ten: In Inns­bruck wur­den an der Uni­ver­si­täts­kli­nik für Radio­lo­gie und Core Faci­lity vier der ins­ge­samt sechs MRT-Sys­teme […]
Das Med­Aus­tron fei­ert als Krebs­be­hand­lungs­zen­trum und For­schungs­in­sti­tu­tion sein 10-jäh­ri­ges Jubi­läum. Das im nie­der­ös­ter­rei­chi­schen Wie­ner Neu­stadt ansäs­sige Kom­pe­tenz­zen­trum für Inno­va­tion und medi­zi­ni­sche Exzel­lenz hat sich zu einer welt­weit beach­te­ten Insti­tu­tion der moder­nen Strah­len­the­ra­pie entwickelt. Unter dem Motto „10 Jahre Zukunft. 10 Jahre Hoff­nung.“ fei­erte das Krebs­be­hand­lungs- und For­schungs­zen­trum Med­Aus­tron soeben sein zehn­jäh­ri­ges Jubi­läum mit Ver­tre­tern aus […]
magnifier
linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram