Vermoedens in Grinvin

Vermoedens in Grinvin
Promotoren: Gunnar Brinkmann, Kris Coolsaet
Grinvin (zie www.grinvin.org) is een programma om met grafen te werken dat bedoeld
is voor het onderzoek en het onderwijs op universitair en zelfs middelbaar niveau. E´en van
de features van Grinvin is dat Grinvin op basis van grafen en invarianten in een database vermoedens kan genereren – b.v. ((aantal toppen)+(grootste graad))/2 <= (aantal bogen)
(in dit geval een vermoeden dat natuurlijk fout is).
aantal toppen
grootste graad
+
2
/
In feite zijn deze vermoedens in Grinvin alleen combinaties van invarianten (b.v. “aantal
bogen”, “koppelingsgetal”,. . . ) en operatoren ( +,-,*,/) waarvoor een zekere foutfunctie
geminimaliseerd wordt. Maar zodra de formules iets langer mogen worden is een exhaustieve
zoektocht naar het optimum niet meer doenbaar.
De taak van deze thesis is een overzicht te geven over tot nu toe gepubliceerde algoritmen
om vermoedens te genereren en een op metaheuristieken gebaseerd algoritme voor Grinvin
te ontwikkelen.
Meer uitleg kan natuurlijk aan de promotoren gevraagd worden.

Download Report