Onderwerpen Masterproef Opleiding Wiskunde Academiejaar Vakgroep Toegepaste Wiskunde, Informatica en Statistiek

Onderwerpen Masterproef Opleiding Wiskunde Academiejaar 2016-2017 Vakgroep Toegepaste Wiskunde, Informatica en Statistiek

Titel: Veralgemeende Fourier transformaties: discreet versus continu Promotor: Hendrik De Bie ([email protected]) Joris Van der Jeugt ([email protected]) Doelgroep: Studenten uit de tweede master Wiskunde. Korte beschrijving: De klassieke Fourier transformatie (FT) kan men linken aan een realisatie in termen van differentiaaloperatoren van de Lie algebra sl_2. Deze herschrijving laat vervolgens toe om vergaande veralgemeningen van de FT te bekomen, door nieuwe differentiaaloperator realisaties van sl_2 (of zelfs ingewikkeldere Lie (super)algebra's ) te construeren. De laatste jaren vormt dit een actief domein van onderzoek, waar zowel continue als discrete transformaties ingevoerd werden. In veel gevallen is er bovendien een interessante kwantummechanische interpretatie. Doel van deze scriptie is om een aantal dergelijke transformaties in detail te bestuderen, en in het bijzonder een vergelijkende studie te maken van het discrete en continue geval.

Titel: “Constant term identities” Promotor: Joris Van der Jeugt ([email protected]) Doelgroep: Studenten uit de tweede master Wiskunde. Korte beschrijving: In de literatuur zijn er tal van intrigerende “constant term identities” te vinden, die dikwijls hun oorsprong vinden in algebra of combinatoriek. Het berekenen of bepalen van de constante term van een rationale functie (van een bepaalde klasse) is niet eenvoudig. Meestal moet men zich wenden tot technieken die dan kunnen geïmplementeerd worden in computeralgebrapakketten. Voor deze scriptie onderzoekt de student eerst een gebied waarin de berekening van constante termen van belang is, zoals de bepaling van Kronecker coëfficiënten voor symmetrische functies. Hiervoor is kennis van symmetrische functies en karakters van S_n een pluspunt. Vervolgens onderzoekt de student enkele methodes/algoritmes om constante term berekeningen te doen. Implementatie van zulke algoritmes in Maple (of Sage) maakt ook deel uit van het werk. Referentiewerken:  A. Garsia, N. Wallach, G. Xin and M. Zabrocki, Kronecker coefficients via symmetric functions and constant term identities. (zie o.a. arXiv:0810.0060 [math.CO]).  G. Xin, A fast algorithm for MacMahon’s partition analysis (arXiv:math/0408377 *math.CO+).

Titel: Lie-superalgebra’s: representaties en toepassingen. Promotor: Joris Van der Jeugt ([email protected]) Doelgroep: Studenten uit de tweede master Wiskunde.

Korte beschrijving: Lie-superalgebra’s zijn structuren die nauw verwant zijn met Lie-algebra’s. Zoals men Lie-algebra’s kan beschouwen als algebra’s waar het product met een commutator correspondeert, zo kan men Liesuperalgebra’s beschouwen als algebra’s waar het product een commutator of een anti-commutator kan zijn. Lie-superalgebra’s zijn structuren die hun oorsprong vinden in wiskundige natuurkunde (supersymmetrie), maar die ook door wiskundigen bestudeerd worden. Hun classificatie werd voltooid in 1977 door V.G. Kac. Inhoudelijk omvat deze masterproef: - een studie van de structuur van enkelvoudige Lie-superalgebra’s - begrippen van representaties van Lie-superalgebra’s, belangrijke klassen van representaties - verwerken van enkele toepassingen van Lie-superalgebra representaties, bijvoorbeeld in Wignerkwantumsystemen. Afhankelijk van de interesse van de student kan de nadruk liggen op representatietheorie (met begrippen als “supersymmetrische Schur functies”, karakters,…) of op toepassingen. Referentiewerken:  M. Scheunert, The theory of Lie superalgebras. An introduction. Lecture Notes in Mathematics, 716. Springer, Berlin, 1979.  V.G. Kac, Lie superalgebras. Advances in Math. 26 (1977), no. 1, 8--96.  S. Lievens, N.I. Stoilova, J. Van der Jeugt, Harmonic oscillators coupled by springs: discrete solutions as a Wigner quantum system. J. Math. Phys. 47 (2006), no. 11, 113504, 23 pp.

Titel: Prijsbepaling en hedging van regenboogopties Promotor: David Vyncke Doelgroep: Toegepaste Wiskunde Korte beschrijving Een regenboogoptie is een financieel derivaat waarvan de pay-off afhangt van twee of meer onderliggende effecten. Magrabe (1978) beschrijft bijvoorbeeld een exchange optie die de belegger het recht geeft om een bepaald aandeel om te ruilen voor een ander aandeel. De beslissing om de optie al dan niet uit te oefenen hangt in dit geval af van de prijs van beide aandelen op de vervaldatum. De prijs van een dergelijke optie wordt bijgevolg bepaald door de individuele effecten maar ook door hun onderlinge afhankelijkheid. De bedoeling van deze masterproef is het bestuderen en implementeren van verschillende methoden om regenboogopties te prijzen en hedgen. Referenties: Chen C.-Y., Wang H.-C. & Wang J.-Y. (2015). The valuation of forward-start rainbow options. Review of Derivatives Research, 18, 145–188. Margrabe W. (1978). The value of an option to exchange one asset for another. The Journal of Finance, 23, 177-186. Ouwehand P., West G. (2006) Pricing rainbow options. Wilmott Magazine, 74-80.

Een ander onderwerp in de financiële wiskunde Promotor: David Vyncke Doelgroep: Toegepaste Wiskunde Korte beschrijving Bespreekbaar

Titel: Alles normal of niet ? Promotor: Christophe Ley ([email protected]) Doelgroep: studenten wiskunde met interesse in mathematische statistiek en kansrekening Korte beschrijving: De normale verdeling heeft een speciale plaats in kansrekening, statistiek en, algemeen, in wetenschappen. Dit heeft historische en wiskundige redenen. Er zijn heel wat verschillende stellingen die zeggen dat slechts de normale verdeling een speciale eigenschap bezit : maximale entropie, limiet van een som van toevalsvariablen, onafhankelijkheid tussen positie en dispersie schatters, etc. Het doel van deze masterproef is een studie van de verschillende stellingen die de normale verdeling karakteriseren, en een vooruitzicht op limitaties van de normale verdeling.

Titel : Information theory Promotor: Christophe Ley ([email protected]) Doelgroep: studenten wiskunde met interesse in mathematische statistiek en kansrekening Korte beschrijving: De historische werken van Claude Shannon over transport van informatie vormen de basis voor een hoog interessant onderzoeksdomein : information theory. Er zijn verschillende maten van informatie : entropie, wederzijds informatie, Kullback-Leibler divergence, etc. Deze maten zijn verbonden met codetheorie. In recente jaren hebben onderzoekers meer en meer links gevonden tussen information theory en statistiek. Het doel van deze masterproef is het bestuderen van deze links en dus van een gloednieuw domein. Referenties: Er zijn veel goede tekstboeken. Voorbeeld: Cover, T. and Thomas, J. (2006) : Elements of Information Theory. Wiley New York.

Titel: Risicominimalisatie onder partiële informatie Doelgroep: master wiskunde Promotor: prof. M. Vanmaele Korte beschrijving: Een verzekeringsmaatschappij kan op elk moment het aantal sterftegevallen voor een bepaalde portefeuille met individuele verzekeringscontracten waarnemen. Echter, de hazard rate van sterfte

kunnen ze niet waarnemen. Bij een hazard rate gaat het om een (voorwaardelijke) kans om van de ene toestand in de andere terecht te komen. Om een unit-linked levensverzekeringscontract te hedgen stelt zich dus het probleem van deze partiële informatie. Bij dergelijke contracten hangen de verzekeringsvoordelen immers af van de prijs van een specifiek aandeel en de uitvoering van betalingen hangt af van het al dan niet voorkomen van een gebeurtenis verbonden met het leven/de leeftijd van de polishouder. Er moet een model opgesteld worden dat de financiële en de verzekeringsmarkt combineert rekening houdend met de beperkingen op de beschikbare informatie over de verzekeringsmarkt. De hedging kan niet perfect gebeuren want er is geen complete markt. In het geval van kwadratische hedging maakt men gebruik van een risicominimalisatie in een martingaalsetting en van lokale risicominimalisatie in een semimartingaalsetting. Deze hedgingstrategieën zijn gebaseerd op de Galtchouck-Kunita-Watanabe-decompositie respectievelijk de Föllmer-Schweizer-decompositie. Daarom dat eerst deze decomposities dienen bestudeerd te worden in het geval van partiële informatie om daarna de kwadratische hedgingstrategieën onder beperkte informatie te bestuderen. Voor deze studie kan gesteund worden op de volgende artikels:  Ceci C., Colaneri K., Cretarola A., Local risk-minimization under restricted information on asset prices. prepint  Ceci C., Colaneri K., Cretarola A., Hedging of unit-linked life insurance contracts with unobservable mortality hazard rate via local risk-minimization. Insurance: Mathematics and Economics, Volume 60, pp. 47-60, 2015.  Ceci C., Cretarola A., Russo F., GKW representation theorem under restricted information. An application to risk-minimization. Stochastics and Dynamics, Volume 14, Issue 2, pp. 1350019 (23 pages), 2014.  Ceci C., Cretarola A., Russo F., BSDEs under partial information and financial applications. Stochastic Processes and their Applications, Volume 124, Issue 8, pp. 2628-2653, 2014.

Titel: Arbitragevrije volatiliteitsparametrisaties via stochastische collocatie Doelgroep: master wiskunde Promotor: prof. M. Vanmaele Korte beschrijving: Bij het hanteren van een groot aantal quotes van de marktvolatiliteit is het normaal om deze uit te drukken in termen van een parametrische vorm, zodat het hele scala van uitoefenprijzen kan worden verklaard door enkele parameters. Zodra de parametrische vergelijking wordt gegeven, kan men de volatiliteiten direct bekomen door het evalueren van de parametrische functie. Sedert enkele jaren is de Hagan-formule een marktstandaard voor volatiliteitsparametrisatie. Deze formule is afkomstig van een “heat kernel expansion” voor een korte looptijd. Alhoewel de dichtheid afkomstig van deze benadering zeer eenvoudig te implementeren is, is deze niet altijd vrij van arbitrage vooral niet voor zeer lage uitoefenprijzen (de dichtheid wordt negatief of integreert niet tot één). Het prijzen van specifieke financiële derivaten, zoals Constant Maturity Swaps (CMS), is gebaseerd op de integratie van de uitbetaling over de dichtheidsfunctie die afkomstig is van zo’n volatiliteitsparametrisatie. Voor deze CMS producten maakt de praktijk gebruik van marginale dichtheden die naar behoren moeten gedefinieerd en arbitrage-vrij zijn. Bijgevolg kunnen deze marginale dichtheden niet gebaseerd zijn op de Haganformule. Grezlak en Oosterlee (2016) stellen een methode voor om een arbitrage-vrije dichtheidsfunctie af te

leiden uit de Hagan-formule. De techniek is gebaseerd op de stochastische collocatiemethode (SCM). De voorgestelde methode is zeer snel en eenvoudig te implementeren omdat het alleen gaat om ééndimensionale Lagrange-interpolatie en de inversie van een lineair systeem van vergelijkingen. De techniek is algemeen en kan toegepast op andere varianten of andere modellen die arbitrage genereren zoals bijvoorbeeld de SVI parametrisatie. Voor deze studie kan gesteund worden op volgende artikels:  Grzelak, L.A., Oosterlee, C.W., From Arbitrage to Arbitrage-Free Implied Volatilities (March 07, 2016). Journal of Computational Finance, Forthcoming. Available at SSRN: http://ssrn.com/abstract=2529684 or http://dx.doi.org/10.2139/ssrn.2529684  Homescu, C., Implied Volatility Surface: Construction Methodologies and Characteristics, eprint arXiv:1107.1834v1, 2011  Kahale N., An arbitrage-free interpolation of volatilities, RISK MAY 2004  Le Floc'h, F., Arbitrages in the Volatility Surface Interpolation and Extrapolation (September 21, 2012). Available at SSRN: http://dx.doi.org/10.2139/ssrn.2175001

Titel: Affiene LIBOR-modellen met meerdere curven: theorie, voorbeelden en calibratie Doelgroep: master wiskunde Promotor: prof. M. Vanmaele Korte beschrijving: Dit onderwerp over interestvoetmodellen betreft de studie van een theoretisch kader met meerdere curven dat leidt tot semi-analytische formules voor het prijzen van renteproducten met positieve interestvoet en basis spreads. Het geval van negatieve interestvoeten en positieve spreads die momenteel waargenomen worden in de markt, past ook in deze theorie. De evolutie van OIS en LIBORtarieven wordt beschreven volgens de methodologie van affiene LIBOR-modellen en is aangedreven door de brede en flexibele klasse van affiene processen. De affiene eigenschap blijft behouden onder voorwaartse maten. Dit laat toe om caps, swaptions en basis swaptions te prijzen via Fouriertransformaties. Om op een efficiënte en nauwkeurige manier een stelsel van capletprijzen te caliberen wordt een model met afhankelijke LIBOR-tarieven gebruikt. Voor deze studie kan gesteund worden op het artikel en de daarin vermelde referenties:  Grbac, Z., Papapantoleon, A., Schoenmakers, J., Skovmand, D., Affine LIBOR Models with Multiple Curves: Theory, Examples and Calibration, SIAM Journal on Financial Mathematics 2015 6:1, 984-1025

Een ander onderwerp in het domein van de financiële wiskunde Promotor: Prof. dr. M. Vanmaele Doelgroep: studenten uit de tweede master Wiskunde Korte beschrijving: Bespreekbaar

Targeted maximum likelihood estimation (TLME) voor het schatten van causale effecten in observationele studies Promotor: Prof. dr. S. Vansteelandt Doelgroep: studenten wiskunde met interesse in mathematische statistiek Korte beschrijving: In heel wat epidemiologische studies is men geïnteresseerd in het schatten van het causaal effect van een blootstelling op een bepaalde uitkomst; bijvoorbeeld, het causaal effect van roken op het risico op sterfte. Dit wordt vaak bemoeilijkt door confounding: de aanwezigheid van factoren die zowel de blootstelling als uitkomst beïnvloeden, waardoor de associatie tussen beiden niet langer een zuiver causaal effect weerspiegelt. Bijvoorbeeld, niet-rokers zijn doorgaans individuen met een gezondere levensstijl dan rokers. Het niet in rekening brengen van confounding leidt tot een vertekende inschatting van het effect van roken. Over de laatste jaren zijn er heel wat schattingstechnieken ontwikkeld om vertekening ten gevolge van confounding te elimineren. Hiervoor moeten statistische modellen worden gebouwd die de associatie van confounders met de uitkomst en/of blootstelling modelleren. Wanneer deze modellen echter niet correct gespecificeerd zijn, kunnen vertekende schattingen worden bekomen. Recent werd er in de literatuur een algemene schattingsmethode voorgesteld, targeted maximum likelihood estimation, die om die reden zuinig omspringt met statistische modellering en schatters met gunstige eigenschappen (bvb. kleine variantie) oplevert. Het doel van deze masterproef zal in eerste instantie zijn om inzicht te verwerven hoe deze schattingsmethode te werk gaat en vervolgens de performantie van TMLE door middel van een simulatiestudie te vergelijken met andere bestaande schattingsmethoden om een causaal effect van een blootstelling op een uitkomst te schatten. Uitgangspunt is het boek “Targeted Learning, causal inference for observational and experimental data” van Mark J. van der Laan en Sherri Rose, Springer Series in Statistics, hoofdstukken 1 tot 7.

Optimale inschatting van nuisance parameters in statistische analyses Promotor: Prof. dr. S. Vansteelandt Doelgroep: studenten wiskunde met interesse in ofwel theoretische, ofwel toegepaste statistiek. Korte beschrijving: Over de laatste jaren maken statistische analyses meer en meer gebruik van `invers wegen'. Dit is een techniek waarbij de metingen van elk individu op een specifieke manier gewogen worden, met als doel bepaalde vormen van vertekening (bijvoorbeeld, ten gevolge van confounding) te elimineren. Een nadeel van deze techniek is echter dat de gewichten, die op basis van de maximum kans methode bekomen worden, voor sommige individuen soms zeer hoog kunnen oplopen. Dat heeft tot gevolg dat deze individuen zeer invloedrijk worden in de analyse, en bijgevolg de analyse danig in de war kunnen sturen. In deze masterproef zult u betrokken worden in een lopend onderzoeksproject waarbij een algemene theorie werd ontwikkeld om deze gewichten op een veel betere manier in te schatten (niet via de maximum kans methode). Het doel zal er meer concreet in bestaan om, na een studie van deze theorie, ze toe te passen op een concrete probleemstelling die momenteel zeer veel aandacht krijgt in de literatuur. Met name zullen we de theorie toepassen om (via zogenaamde directe en indirecte effecten) inzicht te krijgen in het causale mechanisme waarbij een bepaalde blootstelling een bepaalde uitkomst

beïnvloedt. Deze toepassing is gemotiveerd door de concrete probleemstelling waarom bepaalde genen met longkanker geassocieerd zijn: omdat ze mensen ertoe aanzetten te roken, of omdat ze rechtstreeks het risico op longkanker beïnvloeden. De focus van deze masterproef kan, afhankelijk van de interesses van de student, van zeer theoretisch tot zeer toegepast variëren.

Een ander onderwerp in het domein van de mathematische statistiek en/of toegepaste data-analyse Promotor: Prof. dr. S. Vansteelandt Doelgroep: studenten uit de tweede master Wiskunde. Bespreekbaar

Bepalen van Ramsey getallen Promotor: Jan Goedgebeur

Het Ramsey getal R(G, H) is het kleinste getal r zodat elke graaf met tenminste r toppen de graaf G als deelgraaf bevat of zijn complement de graaf H als deelgraaf bevat. Voor complete grafen kan het Ramsey getal R(Kk , Kl ) kan ge¨ınterpreteerd worden als een oplossing voor het feestprobleem: wat is het minimum aantal gasten dat uitgenodigd moet worden op een feestje zodat tenminste k mensen kennissen zijn of tenminste l mensen elkaar niet kennen? Het berekenen van Ramsey getallen is een moeilijk computationeel probleem en daardoor zijn er slechts weinig exacte resultaten gekend. Ramsey getallen R(G, H) kunnen computationeel bepaald worden door Ramsey grafen te genereren. Dit zijn grafen die G niet bevatten en wiens complement ook H niet bevat. Onlangs [1, 2] werden de Ramsey getallen R(K3 , G) van bijna alle 12 005 168 grafen G met 10 toppen bepaald, behalve voor 7 grafen. De bedoeling van deze thesis is om gespecialiseerde algoritmes te ontwerpen en te implementeren om de Ramsey getallen van deze 7 resterende grafen te bepalen. De figuur hieronder toont de complementen van deze 7 grafen.

Door de snelle groei van Ramsey getallen is het heel waarschijnlijk dat de Ramsey getallen R(K3 , G) voor grafen met 10 toppen voor heel lange tijd de laatste volledige lijst van Ramsey getallen zal zijn die mogelijks bepaald kan worden. Meer uitleg kan bekomen worden via: [email protected]. Referenties: [1] G. Brinkmann, J. Goedgebeur, and J.C. Schlage-Puchta. Ramsey Numbers R(K3 , G) for Graphs of Order 10. Electronic Journal of Combinatorics, 19(4), 2012. [2] J. Goedgebeur and S.P. Radziszowski. The Ramsey Number R(3, K10 − e) and Computational Bounds for R(3, G). Electronic Journal of Combinatorics, 20(4), 2013.

De generatie van chemische grafen Promotor: Jan Goedgebeur

Chemische grafen zijn vlakke grafen met maximale graad 4. Deze grafen zijn modelleringen van molecules waarbij de toppen atomen voorstellen en de bogen bindingen tussen de atomen. De figuur hieronder toont een voorstelling van benzeen (met chemische formule C6 H6 ).

H C

H

H

H

C

C

C

C C

H

H De bedoeling van deze thesis is om effici¨ente algoritmes te ontwerpen en te implementeren om alle isomorf-vrije chemische grafen met een gegeven aantal toppen te genereren. Dit programma kan dan gebruikt worden door chemici die onder andere energieberekeningen kunnen doen op de gegenereerde grafen om de meest stabiele molecules te bepalen. Er bestaan reeds verschillende programma’s die bepaalde families van chemische grafen kunnen genereren (zoals bijvoorbeeld nanotubes). Verschillende van die programma’s maken deel uit van de softwarepakket CaGe1 dat chemische grafen kan visualiseren. Er bestaan echter nog geen effici¨ente programma’s om alle chemische grafen te genereren. Het is de bedoeling om het programma dat uit deze thesis resulteert ook toe te voegen aan CaGe. Meer uitleg kan bekomen worden via: [email protected].

1

Zie: http://caagt.ugent.be/CaGe/

Kritische grafen voor lijst-kleurbaarheid Promotor: Jan Goedgebeur Een geldige (toppen)kleuring van een graaf is een toekenning van kleuren aan de toppen van de graaf zodat adjacente toppen een verschillende kleur krijgen. Typisch is het de bedoeling om een gegeven graaf met zo weinig mogelijk kleuren te kleuren. Het kleuren van grafen heeft verschillende toepassingen, bijvoorbeeld voor het plannen van taken. De vraag of een graaf kleurbaar is met hoogstens k kleuren wordt ook het k-kleurbaarheidsprobleem genoemd. Er bestaan verschillende varianten en veralgemeningen van het klassieke k-kleurbaarheidsprobleem, zoals het lijst k-kleurbaarheidsprobleem. Hier wordt aan elke top een lijst van toegelaten kleuren toegekend die een deelverzameling zijn van {1, ..., k}. Een top kan enkel gekleurd worden met ´e´en van zijn toegelaten kleuren. (Dus het klassieke k-kleurbaarheidsprobleem is een speciale versie van het lijst k-kleurbaarheidsprobleem waar elke top {1, ..., k} als toegelaten kleuren heeft). De bedoeling van deze thesis is om de grafen die niet lijst k-kleurbaar zijn te karakteriseren door (alle) kritische grafen voor lijst k-kleurbaarheid te bepalen (voor een gegeven k). Een graaf is kritisch voor (lijst) k-kleurbaarheid als de graaf niet kleurbaar is met k kleuren en elke subgraaf van deze graaf wel kleurbaar is met k kleuren. Onlangs [1] werden de kritische grafen voor bepaalde klassen grafen voor het k-kleurbaarheidsprobleem bepaald en het is de bedoeling om dit nu ook te doen voor lijst k-kleurbaarheid. De studie van deze kritische grafen is vooral belangrijk voor het ontwerp van certificerende algoritmes. Zijn algoritmes die naast een antwoord ook een certificaat teruggeven dat toelaat om in polynomiale tijd te verifi¨eren dat het gegeven antwoord inderdaad correct is. De meeste kleuringsalgoritmes kunnen een ja-certificaat teruggeven (bijvoorbeeld een kleuring van de graaf), maar geen nee-certificaat. De kritische grafen die in deze thesis bepaald zullen worden, leveren een nee-certificaat op en zullen het ontwerp van volledig certificerende algoritmes voor lijst k-kleurbaarheid toelaten. Het is de bedoeling om in deze thesis volledige lijsten van kritische grafen te bepalen door een algoritme te ontwerpen en ook te implementeren voor de generatie van alle kritische grafen. Meer uitleg kan bekomen worden via: [email protected]. Referenties: [1] M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong. Obstructions for threecoloring graphs with one forbidden induced subgraph. In Proceedings of the TwentySeventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, 2016, pages 1774–1783, 2016.

Printplaten testen Promotoren: Jan Goedgebeur ([email protected]) en Nico Van Cleemput ([email protected])

In zowat elk elektronisch toestel vind je vaak verschillende printplaten (PCB’s). Deze PCB’s worden gemaakt uit een sterk isolerende stof waarin verschillende geleidende sporen gelegd worden die verbindingen maken tussen verschillende contactpunten. Op deze contactpunten kunnen dan elektronische componenten gesoldeerd worden. Die componenten zijn duur in vergelijking met de rest van het toestel, dus men wil zeker zijn dat er geen fouten zitten in de interne bedrading van de PCB vooraleer de componenten er op gesoldeerd worden. Daarom worden eerst de PCB’s volledig getest: voor elke twee contacten wordt er gecontroleerd of ze al dan niet verbonden zijn. Dit testen gebeurt met een “flying probe tester”. Dit wil zeggen dat ´e´en paar naalden aan elke zijde de PCB overlopen en telkens testen of er een verbinding is tussen twee contactpunten.

Het doel van deze thesis is om een algoritme te ontwikkelen en effici¨ent te implementeren dat bepaalt welke posities in welke volgorde getest moeten worden. Door gebruik te maken van de transitiviteit van de verbinding is het niet nodig om elk paar van contactpunten te testen. Anderzijds vraagt het verplaatsen van de naalden ook enige tijd, waardoor meer punten testen beter kan zijn als hierdoor een kleinere afstand moet afgelegd worden. Ten slotte zijn er ook nog fysieke beperkingen op de onderlinge posities van de naalden. Dit alles maakt dat tegelijkertijd het “set cover”-probleem (SCP) en het “travelling salesman”-probleem (TSP) moeten opgelost worden rekening houdende met bijkomende beperkingen. Deze thesis gebeurt in samenwerking met Ucamco (http://www.ucamco.com). Zij produceren deze PCB’s en het uiteindelijke doel is om het ontwikkelde algoritme te gebruiken in hun productieproces. Er zijn reeds enkele mogelijke aanzetten tot het probleem, maar eigen idee¨en zijn zoals bij elke thesis meer dan welkom.

Hamiltoniaanse cykels in 5-samenhangende triangulaties Promotor: Nico Van Cleemput ([email protected])

Een hamiltoniaanse cykel in een graaf is een cykel die alle toppen van die graaf bevat. Een triangulatie is een graaf die je in het vlak kan inbedden zonder kruisende bogen zodat alle vlakken (inclusief het buitenvlak) driehoeken zijn. We noemen een triangulatie op meer dan n toppen n-samenhangend als het geen cykel bevat van lengte kleiner dan n die geen vlak is. In 1979 publiceerden Hakimi, Schmeichel en Thomassen een vermoeden dat een 4-samenhangende triangulatie steeds minstens 2(n − 2)(n − 4) verschillende hamiltoniaanse cykels bevat. Tot op heden is dit vermoeden nog niet bewezen: de best gekende grens is momenteel lineair. De grens van Hakimi, Schmeichel en Thomassen was gebaseerd op een familie van triangulaties die exact deze grens bereikt. Met behulp van een computer hebben we twee families van 5-samenhangende triangulaties gevonden die voor elke orde het minst aantal hamiltoniaanse cykels heeft. De ene familie heeft steeds een even aantal toppen, terwijl de andere steeds een oneven aantal heeft.

Voor een even aantal toppen zie je hierboven het kleinste lid van de familie: de icosahedron. Je construeert de triangulaties in de familie door een antiprisma met minstens 10 toppen te nemen, en vervolgens het boven- en ondervlak op te delen met een extra top. Voor een oneven aantal toppen is de familie iets moeilijker te omschrijven. Het doel van deze thesis is om een geslote formule op te stellen voor het aantal hamiltoniaanse cykels in deze families. Deze formule zou dan een goede kandidaat zijn voor een ondergrens voor het aantal hamiltoniaanse cykels in 5-samenhangende triangulaties.

Korte en lange randen Promotor: Gunnar Brinkmann Stel dat je ´e´en rubberen 4-hoek, ´e´en rubberen 5-hoek en zes rubberen 6-hoeken hebt. De bedoeling is nu om die zo in het vlak samen te voegen dat elke top in ten hoogste drie vlakken ligt (het buitenvlak meegerekend) en alle toppen die niet aan de rand liggen in precies 3 vlakken. Toont de tekening een manier om dat te doen waarbij de rand zo kort mogelijk is? P "" PPPP " P " B  B  B  B  B  " HH "bb " bbb "  " HH" bb b ""

" bb " "bb " bbb bb "" "" bb " " b " " !! !! bb "bb "" bb"" bb"""

Dit lijkt misschien een spelletje, maar het heeft wel een toepassing: stel dat de toppen koolstofatomen zijn en de toppen met graad 2 nog met een waterstofatoom verbonden zijn. Bij planaire polycyclische koolwaterstoffen ga je er normaal vanuit dat de meeste vlakken zeshoeken zijn, maar soms heb je ook andere groottes. Stel dus dat je ´e´en 4-hoek en ´e´en 5-hoek toelaat. Als je dan kan bepalen welke randlengten wel dan niet mogelijk zijn, kan je bepalen welke scheikundige formules Cx Hy mogelijk zijn. De bedoeling is dus precies te bepalen welke randlengten voor een gegeven aantal vlakken (waarbij er wel voorwaarden zijn, die ik hier niet vermeld) mogelijk of niet mogelijk zijn. Deze en andere thesissen met meer of minder algoritmische inslag kunnen aansluitend aan de les algoritmische grafentheorie gekozen worden. Andere thesissen hebben bv. met labelling van bomen, met hamiltoniaanse cykels, etc. te maken.

Meer uitleg kan natuurlijk aan de promotor gevraagd worden.

Integer Programming algoritmen voor distributieproblemen Promotor/begeleider: Veerle Fack ([email protected]) Doelgroep: Master Wiskundige Informatica / Master Wiskunde Korte beschrijving Linear Programming (LP) is een techniek voor het oplossen van optimalisatieproblemen waarbij de doelfunctie en de randvoorwaarden alle lineair zijn. Een Mixed Integer Programming (MIP) probleem heeft als extra vereiste dat sommige of alle variabelen integer moeten zijn. Dergelijke problemen zijn onhandelbaar. Exacte algoritmen voor MIP-problemen zijn doorgaans varianten van de branch-and-bound methode, waarbij LP-relaxaties als snoeimethode gebruikt worden. Daarnaast worden uiteraard ook heuristische methodes (zoals local search, simulated annealing, e.d.) gebruikt voor het oplossen van MIP-problemen.

Figuur 1: Vehicle Routing Problem

Het is de bedoeling om Integer Programming algoritmen uit te werken voor enkele optimalisatieproblemen waarmee distributiebedrijven te maken krijgen. In het Vehicle Routing Problem (VRP) beschouwen we een pakjesdienst, die dagelijks goederen moet afleveren bij veel verschillende klanten. Hiervoor is een vloot van voertuigen beschikbaar, die opereert vanuit een centraal distributiecentrum. Het doel is een route voor elk voertuig te ontwerpen (vergelijkbaar met de route uit het handelreizigersprobleem), zodanig dat alle klanten bediend worden door precies e´ e´ n voertuig en dat de totale reiskost van de voertuigen minimaal is. In het Facility Location Problem (FLP) beschouwen we een distributiebedrijf, dat goederen in Figuur 2: Facility Location Problem bulk opslaat in meerdere opslagruimtes, om ze van daaruit te verdelen naar meerdere klanten. Het doel is om te bepalen welke opslagruimtes geschikt zijn voor welke goederen, zodanig dat de kost om de klanten te bedienen minimaal is. De moeilijkheid van dit probleem komt van het feit dat elke opslagruimte een eigen kost en een eigen opslagcapaciteit heeft.

Een studie van de theorie en de implementatie van Constant Pertubation-methoden Doelgroep: master wiskunde / master wiskundige informatica promoter/begeleider : prof. M. Van Daele Beschrijving Klassieke methoden voor de numerieke integratie van gewone differentiaalvergelijkingen zijn vaak gebaseerd op veelterminterpolatie. Dit zorgt ervoor dat wanneer de oplossing van het probleem een veelterm is van voldoend lage graad, de exacte oplossing wordt teruggevonden, terwijl voor vele andere problemen een numerieke oplossing gevonden kan worden die, binnen een bepaalde afgesproken toleratie, aanvaardbaar is. Er kunnen echter problemen rijzen wanneer de oplossing sterk oscillatorisch is. In dat geval dient men met een klassieke methode zeer kleine stapjes te nemen om de oplossing accuraat te kunnen beschrijven. Dit resulteert in enorm veel rekenwerk, waardoor die klassieke methoden praktisch onbruikbaar zijn. Een alternatief wordt geboden door de klasse van de CP-methoden, wat staat voor Constant Perturbation methods. Als concrete toepassing beschouwen we het berekenen van de golffunctie y van een Schr¨odinger-probleem. Het Schr¨ odingerprobleem bestaat uit een tweede orde gewone differentiaalvergelijking (ODE) van de vorm y 00 = (V (x) − E)y,

a < x < b,

(1)

met randvoorwaarden in de eindpunten a en b. De Schr¨odingervergelijking vormt de fundamentele vergelijking in de kwantummechanica. Een waarde voor de parameter E waarvoor een niet-nul oplossing bestaat, wordt een eigenwaarde genoemd. De eigenwaarden worden typisch geordend als E0 < E1 < E2 < . . . en de golffunctie of eigenfunctie yk (x), horende bij Ek , heeft dan exact k nulpunten in het interval (a, b). Dit betekent dat de “hogere” eigenfuncties sterk oscilleren. De eerste stap van een CP methode bestaat er in de functie V (x) stuksgewijs te benaderen door een constante, d.w.z. in het interval [xi , xi+1 ] wordt de vergelijking (1) gewijzigd in y 00 = (V¯ − E)y,

xi < x < xi+1 ,

(1) ,

waarbij V¯ een geschikte constante is. Deze vergelijking, waarvan de co¨effici¨enten constanten zijn, kan analytisch exact opgelost worden. Aldus verkrijgen we de waarde van de golffunctie y en van de eerste orde afgeleide y 0 in een aantal roosterpunten. Deze oplossing is uiteraard maar een benaderende oplossing, want V (x) werd vervangen door V¯ . Deze benaderende oplossing, laat ze ons y (0) noemen, wordt vervolgens gecorrigeerd door het in acht nemen van V (x) − V¯ . Via een perturbatieprocedure bekomt men uiteindelijk alsmaar betere benaderingen y (1) , y (2) , . . . die telkens analytisch kunnen worden bepaald. Het doel van de thesis is een studie van de theorie en de implementatie van deze CP-methoden, die de basis vormen van de succesvolle code MATSLISE, onwikkeld in de onderzoeksgroep Numerieke Wiskunde van de UGent. Literatuur Enkele wetenschappelijke artikels: 1. L. Gr. Ixaru, Numerical operations on oscillatory functions, Computers and Chemistry 25 (2001). 2. L. Gr. Ixaru, CP methods for the Schr¨odinger equation, J. Comput. Appl. Math. 125 (2000). Een link naar MATSLISE: 3. http://www.twist.ugent.be/index.php?page=onderzoek&ot=SLsoftware

1

Numerieke methoden voor tweede-orde differentiaalvergelijkingen Doelgroep: master wiskunde/ master wiskundige informatica promoter/begeleider : prof. M. Van Daele Beschrijving In de cursussen Numerieke methoden voor Differentiaalvergelijkingen (opleiding wiskunde) en Wetenschappelijk rekenen (opleiding informatica) worden methoden besproken voor eerste orde differentiaalvergelijkingen. In principe volstaan deze om tweede-orde differtiaalvergelijkingen y 00 = f (x, y) op te lossen, want elke tweede-orde vergelijking kan omgezet worden in een stelsel eerste-orde vergelijkingen. Hierdoor wordt echter y 0 ge¨ıntroduceerd in het probleem. Om dit te vermijden, zijn er ook methoden ontwikkeld die rechtstreeks geschikt zijn voor tweede-orde (of algemeen gesproken hogere orde) differentiaalvergelijkingen. De meest bekende methode hiervoor is wellicht de Numerov methode. Het doel van deze thesis is na te gaan hoe deze methoden kunnen geconstrueerd worden. Wat is hun orde? Hoe zit de stabiliteitstheorie voor deze methoden in elkaar? . . . Literatuur o.a : E. Hairer, S.P. Norsett, G. Wanner, Solving Ordinary Differential Equations I, Springer-Verlag (1991)

Exponential fitting Doelgroep: master wiskunde/ master wiskundige informatica promoter/begeleider : prof. M. Van Daele Beschrijving Heel veel numerieke methoden (voor de benadering van afgeleiden, de berekening van integralen, het oplossen van differentiaalvergelijken, . . . ) steunen op veelterminterpolatie. Voor sommige toepassingen (bvb. als geweten is dat het integrandum of de af te leiden functie periodiek is), zijn veeltermen niet zo geschikt, maar zijn trigonometrische of exponenti¨ele functies eerder aangewezen. Daarom werden nieuwe methoden ontwikkeld die met dit oscillerend of exponentieel karakter rekening houden. Deze techniek heet exponential-fitting. Het doel van deze thesis is dieper in te gaan op de exponential-fitting techniek en zo’n methoden toe te passen op een aantal typische problemen. Literatuur o.a. Liviu Gr. Ixaru and G. Vanden Berghe, Exponential Fitting, Kluwer, Boston - Dordrecht - London, 2004.

2

Grafen en hun hamiltoniaanse eigenschappen Promotoren:

Carol T. Zamfirescu ([email protected]) en Gunnar Brinkmann ([email protected])

Een graaf bestaat uit een verzameling toppen, waarvan sommige verbonden zijn door bogen. Een cykel of pad in een graaf heet hamiltoniaans als hij alle toppen van de graaf precies ´e´en keer bezoekt. Het onderzoek van hamiltoniaanse eigenschappen van grafen heeft een lange geschiedenis met verbindingen met de beroemde 4-kleuren-stelling, maar het is ook heel actueel: bijvoorbeeld om optimale routes voor vrachtwagens te vinden (het handelsreizigersprobleem), voor communicatienetwerken, of om scheikundige moleculen te bestuderen. De bedoeling van jouw thesis zal zijn, interessante klassen van grafen te onderzoeken door het prisma van hamiltoniaansheid. Concreet zal je effici¨ente algoritmen ontwerpen (gebaseerd op bekende oude theorie en jouw nieuwe resultaten) om zo klein mogelijke grafen uit verschillende klassen te vinden. Om een voorbeeld te geven: een graaf G heet bijna hypohamiltoniaans, als G niet hamiltoniaans is, er ´e´en top w is zodat G − w (dat betekent dat we w uit G verwijderen) niet hamiltoniaans is, maar voor alle toppen v 6= w, de graaf G − v toch hamiltoniaans is. Een 4-samenhangende bijna hypohamiltoniaanse graaf zie je hieronder.

Hoewel we hier niet alle details kunnen geven, zijn alle klassen die je zal onderzoeken variaties van hamiltoniaanse en traceerbare grafen (dat zijn grafen met een hamiltoniaans pad). Om meer over deze families van grafen te leren, kan je naar [1] kijken. Je kan jouw thesis zeker ook als jacht naar kleinste voorbeelden zien: als jouw theorie goed is en jouw algoritme snel, kan jij misschien een wereldrecordgraaf vinden!

Referenties [1] Carol T. Zamfirescu. On hypohamiltonian and almost hypohamiltonian graphs. J. Graph Theory 79, Iss. 1 (2015) 63–81.