Optioneel in fase
Eerste semester
Tweede semester
Beide semesters
Dit jaar
Volgend jaar
Wisselende jaren
Extern
Voorwaarden
Docenten
Onderwijstaal
Duur
NiveauFundamenten voor de informatica (B-KUL-G0P79A)
Doelstellingen
Inzicht verschaffen in een aantal formele aspecten van en voor informatica, in het bijzonder complexiteitstheorie (die al informeel ingevoerd is in het vak Beginselen van Programmeren), grafentheorie (die belangrijk is in vele toepassingen) en vastepuntstheorie (o.a. nodig voor het begrijpen van inductieve definities). De student moet in staat zijn bewijzen te reproduceren en stellingen te gebruiken om oefeningen op te lossen. De student moet gefundeerd kritisch staan t.o.v. de definities en toepassingsmogelijkheden kunnen begrijpen en ontdekken.
Begintermen
De student moet vertrouwd zijn met een aantal elementen van hogere wiskunde (limieten, afgeleiden) en discrete wiskunde (logica, verzamelingenleer).
Aard van het studiemateriaal
Cursustekst
Volgtijdelijkheidsvoorwaarden
Dit opleidingsonderdeel is een voorwaarde voor het opnemen van volgende opleidingsonderdelen:
H01Q3A : P&O Computerwetenschappen, hoofdrichting
H01Q3C : P&O: Computerwetenschappen
Plaats in het onderwijsaanbod
- Schakelprogramma: Master in de toegepaste informatica 59 sp.
- Bachelor in de biochemie en de biotechnologie (Minor informatica) 180 sp.
-
Bachelor in de informatica
180 sp.
- Bachelor in de wiskunde (Minor informatica) 180 sp.
- Bachelor in de wiskunde (Minor verbreding) 180 sp.
- Bachelor in de fysica (Minor informatica) 180 sp.
-
Bachelor in de informatica (verkort programma)
120 sp.
Onderwijsleeractiviteiten
4.1 sp. Fundamenten voor de informatica (B-KUL-G0P79a)
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
1.9 sp. Fundamenten voor de informatica: oefeningen (B-KUL-G0P80a)
Inhoud
Zie hoorcollege.
Evaluatieactiviteiten
Evaluatie : Fundamenten voor de informatica (B-KUL-G2P79a)
Toelichting
Gesloten boek voor theorie.
Open boek voor oefeningen.
