De onderwerpen
Grafentheorie (deel 2)
Aantal EC: 3 EC
Voorkennis: Combinatoriek en Optimalisering, Discrete Besliskunde
Inhoudelijke samenvatting: Deel 1 van Grafentheorie is reeds in Discrete Besliskunde besproken. In dit hoofdstuk komen andere onderwerpen aan de orde: grafen en matrices, vlakke en duale grafen en kleurproblemen.
Koppelingen
Aantal EC: 2 EC
Voorkennis: Combinatoriek en Optimalisering, Discrete Besliskunde
Inhoudelijke samenvatting: Begonnen wordt met de algemene theorie voor bipartiete en algemene grafen. Vervolgens worden algoritmen voor bipartiete grafen behandeld (maximale cardinaliteit, maximaal gewicht en Gilmore-Gomory en Gale-Shapley koppelingen). Het hoofdstuk wordt afgesloten met algoritmen voor algemene grafen (maximale cardinaliteit en maximaal gewicht).
Bomen (deel 2), sorteren en het Chinese postbodeprobleem
Aantal EC: 0.5 EC
Voorkennis: Combinatoriek en Optimalisering, Discrete Besliskunde
Inhoudelijke samenvatting: Dit hoofdstuk gaat over drie onderwerpen: bomen, sorteren en het Chinese postbodeprobleem. In Discrete Besliskunde zijn bomen reeds aan de orde geweest. In de eerste paragraaf van dit hoofdstuk gaan we nader in op boomwandelingen, binaire zoekbomen en Steiner bomen. De tweede paragraaf behandelt diverse sorteermethoden en de derde het Chinese postbodeprobleem.
Netwerk Optimalisering (deel 2)
Aantal EC: 2.5EC
Voorkennis: Combinatoriek en Optimalisering, Discrete Besliskunde
Inhoudelijke samenvatting: Deel 1 van Netwerk Optimalisering is in Discrete Besliskunde behandeld. In dit deel komen aan bod: netwerkstromen (disjuncte paden; maximale stromen met minimale kosten) en de netwerk simplex methode.
Matroïden
Aantal EC: 3EC
Voorkennis: Combinatoriek en Optimalisering, Discrete Besliskunde, het hoofdstuk Koppelingen, het hoofdstuk Grafentheorie (deel 2)
Inhoudelijke samenvatting: De matroïdentheorie is een algemene theorie over het begrip onafhankelijkheid. Het is een generalisatie van de lineaire algebra, de grafentheorie en de transversaaltheorie. We beginnen met definities en voorbeelden. Daarna behandelen we de relatie tussen grafen en matroïden. Vervolgens komt het gretige algoritme aan bod. Tenslotte worden meer geavanceerde onderwerpen besproken: onafhankelijkheidssystemen, doorsnede van matroïden, grafoïden, representeerbaarheid en polymatroïden.
Beslissingstheorie
Aantal EC: 0.5EC
Voorkennis: Geen
Inhoudelijke samenvatting: Veel beslissingsproblemen bevatten onzekerheid. door gebrek aan informatie over de omstandigheden waarin we (komen te) verkeren of doordat de informatie over die omstandigheden niet deterministisch maar stochastisch is. In de beslissingstheorie worden dit soort modellen bestudeerd en wordt nader ingegaan op bepaalde criteria om tot een beslissing te komen. We onderscheiden de volgende deelgebieden: beslissen zonder kansen, beslissen met kansen en beslissingsbomen.
Voorraadtheorie
Aantal EC: 1.5EC
Voorkennis: Combinatoriek en Optimalisering
Inhoudelijke samenvatting: In de voorraadtheorie houdt men zich bezig met twee typen kosten: bestel- en voorraadkosten. Als er veel wordt besteld zijn de bestelkosten per eenheid minder dan als er weinig wordt besteld; de voorraadkosten zijn juist hoger als er veel wordt besteld. De centrale vraag is welke voorraadstrategie optimaal is. We bespreken diverse varianten van vier basismodellen: continu en deterministisch, periodiek en deterministisch, continu en stochastisch, en periodiek en stochastisch.
Knapzakprobleem
Aantal EC: 1EC
Voorkennis: Combinatoriek en Optimalisering, Discrete Besliskunde
Inhoudelijke samenvatting: Bij het knapzakprobleem heb je slechts een bepaald volume beschikbaar, maar je hebt ook een aantal objecten die elk een bepaalde waarde en een volume hebben. Het doel is om objecten te kiezen zodat het past en de gezamenlijke waarde zo hoog mogelijk is. Besproken worden de complexiteit, oplossingsmethoden en eventuele benaderingsmethoden van het 0-1 knapzakprobleem, het fractionele knapzakprobleem, het onbegrensde knapzakprobleem, het begrensde knapzakprobleem en het bin-packing probleem.
Betrouwbaarheidstheorie
Aantal EC: 1.5EC
Voorkennis: Combinatoriek en Optimalisering, Stochastische Besliskunde, Discrete Besliskunde
Inhoudelijke samenvatting: Betrouwbaarheidstheorie houdt zich bezig met het bepalen van de kans dat een bepaald systeem, bestaande uit één of meer componenten, functioneert. We behandelen de volgende onderwerpen: structuurfuncties, betrouwbaarheidsfuncties, de (verwachte) levensduur van een systeem en systemen met reparatie.
Lineaire Optimalisering (deel 2)
Aantal EC: 1.5EC
Voorkennis: Combinatoriek en Optimalisering
Inhoudelijke samenvatting: Deel 1 van Lineaire Optimalisering is reeds in Optimalisering en Combinatoriek besproken. In dit hoofdstuk komen andere resultaten aan de orde: implementatie aspecten, gevoeligheidsanalyse, de duale simplex methode en de primale-duale simplex methode.
Speciale technieken
Aantal EC: 2EC
Voorkennis: Combinatoriek en Optimalisering, Discrete Besliskunde, het hoofdstuk Lineaire Optimalisering (deel 2)
Inhoudelijke samenvatting: In dit hoofdstuk bespreken we speciale technieken voor lineaire en geheeltallige optimaliseringsproblemen. Aan de orde komen: decompositie methoden (Dantzig-Wolfe en Benders decompositie), Lagrange relaxatie en kolomgeneralisatie.
Inwendige puntmethoden
Aantal EC: 1.5EC
Voorkennis: Combinatoriek en Optimalisering
Inhoudelijke samenvatting: Dit is een vrij moderne techniek om optimaliseringsproblemen op te lossen. We bespreken inwendige punt methoden voor lineaire optimaliseringsproblemen. Bij de simplex methode wordt langs de rand van het toegelaten gebied gelopen totdat het optimum is bereikt. Bij inwendige punt methoden wordt de rand juist vermeden en wordt getracht om door het inwendige naar het optimum te lopen. We behandelen diverse specifieke methoden: de methode van Karmarkar, de affiene schaling methode, de potentiaal reductie methode en diverse pad-volgende methoden (primaal, primaal-duaal en predictor-corrector).
Niet-lineaire Optimalisering
Aantal EC: 2EC
Voorkennis: Analyse 2, Combinatoriek en Optimalisering
Inhoudelijke samenvatting: Begonnen wordt met voorbeelden, algemene optimaliteitsvoorwaarden en eigenschappen zoals convexiteit. Daarna worden de onbeperkte en de beperkte optimalisering behandeld. Bij de onbeperkte optimalisering wordt ingegaan op ééndimensionale en meerdimensionale optimalisatie. De behandeling van de beperkte optimalisering betreft zowel theorie als methoden. De theoretische zaken zijn Lagrange multipliers, Karush-Kuhn-Tucker voorwaarden en dualiteit. De methoden die worden behandeld zijn de volgende: het algoritme van Wolfe voor kwadratische optimalisering, de methode van toelaatbare richtingen, de gereduceerde gradi ̈ent methode, de gegeneraliseerde gereduceerde gradi ̈ent methode en de barriére methode.