 |
Algemeen
-
Studiepunten: 4.10
-
Onderwijstaal: Nederlands
-
Werkvorm:
hoorcollege
-
Begeleidingsuren:
26.0 uren
-
Periode:
Wordt gedoceerd in het tweede semester
-
Verantwoordelijke POC:
POC Informatica
Docenten/didactisch team
Blockeel Hendrik
Inhoud
Complexiteitstheorie (8 uur)
• het begrip taal en beslissen van een taal
• reguliere talen en hun beslissing door FSA
• Turing machines - deterministisch en niet-deterministisch
• rekenen met TM
• formulering van de hypothese van Church
• definitie van complexiteit van een algoritme/probleem en de big O notatie
• opstellen van een recurrentievergelijking voor de tijdscomplexiteit van een algoritme
• technieken voor het oplossen van recurrentievergelijkingen
• P, NP en NP-C: definities en verbanden
Grafentheorie (13 uur)
• definities: graaf, pad
• voorstelling van grafen
• isomorfisme van grafen
• gewogen grafen
• vlakke grafen
• het kleuren van grafen
• bomen: definities en eigenschappen
• opspannende bomen
• minimale opspannende bomen
• doorlopen van bomen
• spelbomen
• transportnetwerken
• maximale stroming
• matching netwerken en de stelling van Hal
• Petrinetten
Vastepuntstheorie (5 uur)
• orderelatie
• monotone en continue afbeeldingen
• stelling van Tarski
• stelling van Kleene
|
B-KUL-G0P79A Fundamenten voor de informatica
