Artificiële Intelligentie

Ga naar: navigatie, zoeken
Daniel De Schreye
Joost Vennekens

Samenvattingen

Klik hier om de samenvattingen te bekijken

Nuttige links

Over het vak

2018-2019: Het vak wordt gedoceerd door Daniel De Schreye en Luc De Raedt. De nodige documenten voor het gedeelte van prof. De Schreye zijn nog steeds op zijn website te vinden, maar voor de bestanden van Luc De Raedt kan je op Toledo terecht. De eerste paar weken waren er twee hoorcolleges per week, maar de weken daarna slechts één. Wel is de oefenzitting nog steeds wekelijks, dus 13 in totaal. Ook zijn er geen practica meer doorheen het semester.

Outdated, maar wel nuttig: Dit vak wordt gegeven door prof. Danny De Schreye aan de tweedejaars Informatica, derdejaars Wiskunde met minor IT en derdejaars Ingenieurswetenschappen met hoofdrichting Computerwetenschappen. Per week zijn er één of twee colleges en één oefenzitting, waarvan de oplossingen overlopen worden en ook uitgewerkt online te vinden zijn. Er is geen handboek of cursustekst; alles staat in principe op de slides. Wie zeker wil zijn, kan dus best naar de colleges komen. Prof. De Schreye is een uitstekend leraar.

Er is weinig werk vereist voor dit vak: voor de oefenzittingen is geen voorbereiding nodig en de hoeveelheid theorie is klein, zeker voor een vak van zes studiepunten. Tijdens het semester zijn er wel twee practica, waarbij je een verslag schrijft over de werking van een gekend algoritme. Deze staan elk op 3 van de 20 punten voor het eindexamen.

Voor wie in de loop van het semester mee was met de leerstof is het maken van enkele oefeningen op automatisch redeneren en het overlopen en beantwoorden van de theorievragen van vorige jaren voldoende voorbereiding voor het examen.

Vakevaluatie

Elk puntje hieronder is iemands mening. Verander aub geen puntjes. Als je een andere mening hebt, gelieve ze onderaan toe te voegen.

Kwaliteit cursus (prijs, duidelijkheid, overeenkomst met les, ...)

  • 2016: Gewoon een paar slides (en een onofficiele studentencursus die online te vinden is). Eigenlijk heb je niet veel meer nodig als je naar de les komt.

Studiebelasting (aantal studiepunten in verhouding met bestede tijd)

  • 2016: Belachelijk weinig tijdens de examenperiode. Nog gemakkelijker dan in het middelbaar. Er zijn twee practica, die een beetje vergelijkbaar zijn met die van G&A.

Plaats binnen de opleiding (nodige voorkennis, overlap met andere vakken, relevantie van het vak,...)

  • 2016: Bepaalde dingen ken je al uit het eerste jaar informatica: zoeken in bomen, backtracking, en logica.

Manier van lesgeven bij hoorcolleges (snelheid, verstaanbaarheid, structuur, nut, ...)

  • 2016: Danny is een geweldige prof. De colleges zijn zeker aan te raden. Zeker als er niet echt een cursustekst is.

Evaluatie oefenzittingen/labo's (nut, begeleiding, ...)

  • 2016: OK. Ze helpen je om bepaalde algoritmen beter te leren begrijpen. Uiteindelijk moet je vooral theorie kennen, maar de oefenzittingen zijn wel nuttig.

Examen (mate waarin het een weerspiegeling is van de cursus, examenvorm, ...)

  • 2016: Een oefening op logica en automatisch redeneren, een theorievraag over zoeken (de mogelijke vragen staan op Danny's homepagina), en en theorievraag over een ander hoofdstuk (de mogelijke vragen staan op de Wiki's van Wina en VTK)

Examens

2018

30/01/2018 - 9u

Oefeningen:

  1. Automated reasoning

Theorie:

  1. Wat is de motivatie voor het invoeren van IDA* en SMA*?
    1. Leg de werking uit van IDA*:
      1. Hoe worden de f-bounds gekozen?
      2. Eigenschappen
      3. Klein voorbeeld
      4. Verschillen/gelijkenissen van de eigenschappen t.o.v. ID
  1. Version Spaces
    1. Waarom bestaat het?
    2. Als je een negatief voorbeeld toevoegt, wat gebeurt er? (idem voor positief)?
    3. Hoe wordt het geïnitialiseerd?
    4. Wanneer stopt het algoritme?
    5. Wat zijn de voor- en nadelen?
    6. Leg uit hoe je de resultaten kan interpreteren
    7. Wat is BIAS?

22/01/2018 - 8u

Oefening:

  1. Automated reasoning

Theorie:

  1. Eigenschappen van A*
    1. Wat betekent het als een A* algoritme "sterker geïnformeerd" is dan een andere A*? Wat is het nut van sterker geïnformeerd zijn? Illustreer a.d.h.v. een voorbeeld.
    2. Leg uit: monotoniciteitsrestrictie. Wat is het, hoe kom je eraan, wat is het nut van dit concept? Illustreer a.d.h.v. een voorbeeld.
  1. Leg uit: Forward check, Lookahead check, AC1 en AC3.
    1. Welke van bovenstaande leunt het meest aan bij de procedure van Waltz? Leg uit.

17/01/2018 - 8u

Oefening:

  1. Automated reasoning: 1) Vertaal zinnen naar logica, 2) normaliseer, 3) bewijs

Theorie:

  1. A*
    1. Leg uit: Uniform cost, branch-and-bound principe, een optimalisatie (path deletion)
    2. Hoe kan een heuristische waarde worden toegevoegd aan uniform cost?
    3. Hoe wordt al het vorige in A* geïmplementeerd?
  1. Backtracking
    1. Leg uit wat trashing en redundante checks zijn en illustreer.
    2. Welk probleem wordt opgelost door backmarking?
    3. Welke informatie houdt het algoritme bij?
    4. Hoe gebruikt het deze informatie?
    5. Je hoeft het algoritme verder niet in detail te bespreken.

15/01/2018 - 8u

Oefeningen:

  1. Automated reasoning.

Theorie:

  1. Wat is de motivatie voor het invoeren van IDA* en SMA*?
    1. Leg de werking uit van IDA*:
      1. Hoe worden de f-bounds gekozen?
      2. Eigenschappen
      3. Klein voorbeeld
      4. Verschillen/gelijkenissen van de eigenschappen tov ID
  1. Leg uit: Forward checking, Lookahead checking, AC1 en AC3.
    1. Welke van bovenstaande is de beste keuze voor de Waltz procedure? Leg uit.


15/01/2018 - 14u

Oefeningen:

  1. Automated reasoning.

Theorie:

  1. SMA*
    1. Waarom werd het ingevoerd?
    2. Leg de vier dingen uit die SMA* doet (acties bij vol geheugen, ...) en illustreer met een voorbeeld.
    3. Wanneer stopt SMA*?
    4. Geef de eigenschappen.
  1. Version Spaces
    1. Initialisatie
    2. Wat gebeurt er met S en G tijdens positieve en negatieve voorbeelden?
    3. Wanneer stopt het?
    4. Hoe kan je het resultaat gebruiken voor classificatie?
    5. Wat is een BIAS?

2017

31/01/2017 - 9u

Oefening:

  1. Automated reasoning:
    1. Vertaal zinnen naar logica
    2. Normaliseer deze zinnen
    3. Bewijs door resolutie

Theorie:

  1. Blind search
    1. Bespreek Depth first, Breadth first, Iterative deepening en Bi-directional search op vlak van tijdscomplexiteit, geheugengebruik en volledigheid.
  1. Backtracking
    1. Trashing en redundant checks kunnen voorkomen bij backtracking. Leg uit wat dit betekent.
    2. Backmarking lost één van deze problemen op, welk?
    3. Bespreek de werking van backmarking en hoe het dit probleem oplost. (Je hoeft het algoritme niet gedetailleerd te bespreken, enkel vermelden dat het met twee arrays werkt enz.)

17/01/2017 - 9u

Oefening:

  1. Automated reasoning: 1) Vertaal zinnen naar logica, 2) normaliseer, 3) bewijs

Theorie:

  1. A*
    1. Leg uit: Uniform cost, branch-and-bound principe, een optimalisatie (path deletion)
    2. Hoe kan een heuristische waarde toegevoegd worden aan uniform cost?
    3. Hoe wordt al het vorige in A* geïmplementeerd?
  1. Constraint programming: lijnfiguur interpretatie
    1. Geef een beetje context tot het lijnfiguur interpretatie probleem
    2. Leg de Waltz procedure uit
    3. Geef de definitie voor een constraint probleem (variabelen, domein en de constraints) en vertel hoe het lijnfiguren probleem en de Waltz procedure hierin passen.
    4. De Waltz procedure is zeer gelijkaardig aan een algoritme dat we gezien hebben (AC1, AC3, Forward check, Look ahead check, Forward checking of Look ahead checking)

16/01/2017 - 14u

Oefening:

Gegeven de volgende theorie over de Rode Duivels:

  1. Als er iemand speelt of snel loopt, dan bestaat er een speler.
  2. Niemand is zowel verwond als uit vorm.
  3. Rode Duivels zijn spelers.
  4. Wie niet uit vorm is, kan snel lopen of is een geen Rode Duivel.
  5. Het is niet zo dat er een Rode Duivel is die speelt.
  6. Alle spelers die niet verwond zijn, spelen.

Hier is de "of" een gewone disjunctie, dus geen exclusieve of. Formuleer deze in predicatenlogica met de predicaten speelt(x), snel(x), speler(x), verwond(x), uitvorm(x) en RodeD(x). Bewijs hiermee dat Rode Duivels snel lopen.

Theorie:

  1. SMA* (zoals op de webpagina)
    1. Wat is de motivatie voor het uitvinden van SMA*?
    2. Leg de 4 stappen uit die SMA* toevoegt: vol geheugen, sequentieel genereren van kinderen, opgeven van te lange paden, propagatie van f-waarden. Illustreer elke stap met een voorbeeld.
    3. Wanneer stopt het algoritme?
    4. Wat zijn de eigenschappen van SMA*? // Optimaliteit, volledigheid, tijd, geheugen,...
  1. Backtracking
    1. Leg uit wat trashing en redundante checks zijn en illustreer.
    2. Welk probleem wordt opgelost door backmarking?
    3. Welke informatie houdt het algoritme bij?
    4. Hoe gebruikt het deze informatie?
    5. Je hoeft het algoritme verder niet in detail te bespreken.

16/01/2017 - 8u

Oefeningen:

  1. Automated reasoning.

Theorie:

  1. Wat is de motivatie voor het invoeren van IDA* en SMA*?
    1. Leg de werking uit van IDA*:
      1. Hoe worden de f-bounds gekozen?
      2. Eigenschappen
      3. Klein voorbeeld
      4. Verschillen/gelijkenissen van de eigenschappen tov ID
  1. Leg uit: Forward checking, Lookahead checking, AC1 en AC3.
    1. Welke van bovenstaande is de beste keuze voor de Waltz procedure? Leg uit.

2016

19/01/2016 - 8u

Oefeningen:

  1. Automated reasoning. // Conform laatste oefening in oefenzittingen.

Theorie:

  1. Mini-Max
    1. Discuss the Mini-Max approach to game playing:
    2. Explain how the basic Mini-max search works.
    3. Explain the extension with Alpha-Beta pruning:
      1. How do we get Alpha-Beta values?
      2. How are these values used?
      3. Illustrate.
    4. What are deep cut-offs? Illustrate.
    5. What is a perfectly ordered tree?
    6. What is known about the gain of Alpha-Beta (compared to mini-max)?
    7. What is the horizon effect and how can you solve it?
    8. Why is iterative deepening useful in this context?
  1. Backtracking
    1. Heeft 2 problemen, welke? Leg uit.
    2. Backmarking lost 1 van deze problemen op. Welk?
    3. Hoe gaat backmarking te werk?
    4. Niet nodig heel het algoritme uit te leggen. // Wel 2 arrays + properties, red.


13/01/2016 - namiddag

Oefeningen:

  1. Zinnen vertalen naar predicatenlogica, normaliseren en contradictie via resolutie.

Theorie:

  1. 1: Wat is de motivatie voor het invoeren van IDA* en SMA*?
    1. Leg de werking uit van IDA*:
    2. Hoe worden de f-bounds gekozen?
    3. Eigenschappen
    4. Klein voorbeeld
    5. Verschillen/gelijkenissen van de eigenschappen tov ID
  1. 2: Wat is STRIPS planning?
    1. Wat is de methode?
    2. Hoe worden toestanden voorgesteld?
    3. Illustreer met het blokkenwereldprobleem.
    4. Wat zijn establish/threatens/before links?
    5. Hoe bekomt men before links?
    6. Wat zijn de 2 principes van 'least commitment'?

13/01/2016 - 8u

Oefeningen:

  1. Automatisch redeneren: omzetten van 3 zinnen + doelzin van natuurlijke taal naar implicatieve normaalvorm, inconsistentiebewijs geven (~8 resolutiestappen).

Theorie:

  1. SMA*:
    1. Wat is de motivatie hierachter tegenover A*?
    2. Leg de vier concepten uit die toegevoegd moeten worden aan A* om SMA* te bekomen, en illustreer: wat als geheugen vol zit, sequential child generation, te lange paden, f-waarde propagatie (deze werden dus gegeven, je moest alleen uitleggen).
    3. Wanneer stopt SMA*? Hoe kan je dit in de zoekboom zien?
    4. Geef de eigenschappen van SMA*.
    5. Wat heeft het gemeen met IDA*?
  1. Intelligente backtracking:
    1. Wat zijn no-goods, hoe worden deze gebruikt in intelligente backtracking, ...
    2. Hoe komt intelligente backtracking voor in backjumping en backmarking?
    3. Wat is dynamic search rearrangement?
    4. Op welke manieren kan dit geïmplementeerd worden?

12/01/2016 - 8u

Oefeningen:

  1. Logica (zin formuleren in predicatenlogica, normaliseren, en zin bewijzen door contradictie)

Theorie:

  1. A* : uniforme kost, branch and bound, heuristiek, onderschatting, redundant path elimination (dat deeltje vragen op de website)
  2. Backtracking: trashing, backmarking (hoe lost het redundantie op, hoe werkt het)

11/01/2016 - 8u

Oefeningen:

  1. Automatisch redeneren (zinnen omvormen naar logica, normaliseren en tot een contradictie komen via een inconsistentiebewijs)

Theorie:

  1. Waarom zijn IDA* en SMA* in het leven geroepen (== wat is er slecht aan A*)?
    1. Bespreek IDA* en illustreer aan de hand van een voorbeeld.
  1. Leg uit: Forward checking, Lookahead checking, AC1 en AC3.
    1. Welke van bovenstaande is de beste keuze voor de Waltz procedure? Leg uit.

2015

20/01/2015 - 14u

Oefeningen:

  1. Automatisch redeneren

Theorie:

  1. Lookahead, forward, AC1, AC3
    1. Welke van bovenstaande trekt het meest op Waltz? Waarom?
  1. Machine learning
    1. Waarom bestaat het?
    2. Als je een negatief voorbeeld toevoegt, wat gebeurt er? (idem voor positief)?
    3. Hoe wordt het geïnitialiseerd?
    4. Wat zijn de voor- en nadelen?

14/01/2015 - 8u

Oefeningen:

  1. Automatisch redeneren

Theorie:

  1. Blind Search
    1. Leg de basis blind search algoritmen uit. (depth first, breadth first, iterative deepening search en bidirectional search - aan de hand van snelheid, memory usage en completeness)
  1. Intelligent backtracking
    1. Leg uit hoe no-goods eigenlijk backjumping en backmarking een klein beetje nadoen.
    2. Dynamic rearrange search is toepasbaar is op intelligent backtracking, leg uit.

2014

30/01/2014 - 14u

Oefeningen:

  1. Version spaces
  2. Automatisch redeneren

Theorie:

  1. SMA*:
    1. Waarom bestaat het?
    2. Welke vier stappen moet je toevoegen aan het gewone A* algoritme om SMA* te hebben?
    3. Geef de eigenschappen van SMA* (complexiteiten en zo).
    4. Wat is de grootste overeenkomst tussen SMA* en IDA*?
  1. Backtracking:
    1. Leg de twee problemen van backtracking uit:
      1. Thrashing
      2. Redundant checks
    2. Wat houdt het algoritme bij van info en hoe wordt die info gebruikt? (Niet nodig om heel het algoritme uit te leggen)

21/01/2014 - Voormiddag

Oefeningen (open boek):

  1. Version spaces
  2. Automatisch redeneren

Theorie:

  1. De eigenschappen van A* bespreken
  2. Backmarking

2013

21/01/2013

Oefeningen (open boek):

  1. Version spaces
  2. Automatisch redeneren

Theorie:

  1. A*, Waltz


14/01/2013

Oefeningen (open boek):

  1. Version spaces
  2. Logica

Theorie:

  1. A*, lookahead, forward, AC1, AC3, k-consistency
  2. Wat is de overeenkomst tussen AC3 en Waltz? Waarom?

2011

27/06/2011 (namiddag)

Open boek oefeningen gedeelte.

Je mag hiervoor ALLES gebruiken, niet alleen de slides. Wij krijgen 2u15, wat wel nipt kan zijn omdat de oefeningen meestal uitgebreid zijn.

  1. Een oefening op automatisch redeneren, helemaal gelijkaardig aan de moeilijkste oefening op AR uit de oefenzittingen.
    • Je krijgt 7 nederlandse zinnen en moet die omvormen tot eerste orde predikatenlogica. (Belangrijke tip uit logica van het eerste jaar: na een "voor alle" komt een pijl (-->), na een "er bestaat" komen conjuncties (^). Als je de zinnen niet correct omzet krijg je natuurlijk problemen later.)
    • Vervolgens moet je die zinnen omvormen tot implicatieve normaalvorm om zo je model te vormen
    • Tenslotte krijg je een uitspraak, deze zet je ook om tot eerste orde predikatenlogica, dan neem je er de negatie van, dan zet je dat om tot implicatieve normaalvorm, en vervolgens breidt je je model uit met deze uitspraak.
    • Tot slot bewijs je dat het model inconsistent is waarmee je ook bewijst dat de uitspraak waar is.
  2. Een oefening op version spaces.

Gesloten boek theorie gedeelte.

    • Wat betekent het als een A* algoritme "sterker geïnformeerd" is dan een andere A*? Wat is het nut van sterker geïnformeerd zijn?
    • Leg uit: monotoniciteitsrestrictie. Wat is het, hoe kom je eraan, wat is het nut van dit concept?
    • Hoe kan je verzekeren dat je boom/grafe monotoon is? (Dit is een beetje raar geformuleerd vind ik. Ik heb als antwoord gegeven dat we voor iedere 2 verbonden knopen de monotoniciteitsrestrictie nakijken, en als deze faalt we de heuristiek verhogen tot deze wel klopt. Hier gaf hij geen verdere commentaar/bijvragen op.)
    • Leg het algoritme van Waltz uit en illustreer het.
    • Met welk algoritme kan je dit vergelijken? Leg uit waarom. (antwoord was AC3, zoals hieronder ook staat)

Oude examenvragen

Deze vragen komen (tot en met het jaar 2011) steeds terug! De lijst is wel niet volledig, dus leer natuurlijk niet alleen deze vragen.

Voorbeeld 1

  • Hoe kom je tot A*? Leg daarvoor uit:
    • uniform-cost
    • branch&bound
    • hoe heuristiek erin brengen
    • intuïtief uitleggen waarom onderschattende heuristiek optimaal doel bereikt
    • redundant path deletion

--> hoe alles in A* integreren?

Voorbeeld 2

motivatie om tot IDA* en SMA* te geraken, hoe werkt IDA* leg uit (hoe kom je aan f-bound etc), eigenschappen IDA*, de 4 veranderingen tussen SMA* en A* geven en illustreren

Voorbeeld 3

Version spaces: wat is concept learning version spaces: init? wat bij negatieve voorbeelden... wat gebeurt er in G; wat in S idem voor pos wanneer stopt vs ben je er iets mee als het niet convergeert? voor en nadelen?

Voorbeeld 4.

Het standaard backtracking algoritme heeft enkele efficientie problemen in verband met ``trashing en het uitvoeren van redundante tests. Licht dit toe.

Op welke manier proberen methodes zoals ``backjumping en ``backmarking deze problemen op te lossen? Illustreer. Welke informatie gebruiken ze daarbij en hoe? Je hoeft hierbij niet in details over de eigenlijke algoritmes te gaan.

Voorbeeld 5

leg kort uit: AC1, AC3, lookahead search, forward search; geef definitie constraint problem, en geef tegenhangers bij die lijntekeningen; met welk van de hierboven methoden + lookahead searching & forward searching kan je de Methode van Waltz vergelijken? + verklaar waarom

Voorbeeld 6

Waltz algoritme : wat is het, wat is de werkwijze, hoe is dit een constraint probleem, geef de standaardonderdelen van constraint probleem hun overeenkomstige zaken bij walz. Dit komt overeen met 1 van de 6 relaxatietechnieken (forward check, lookahead check, AC1, AC3, forward checking , lookahead checking) dewelke en waarom? (antwoord: AC3)

Voorbeeld 7.

Bespreek de aanpak van STRIPS voor planning. Gebruik daarbij het blokkenwereld-probleem als een illustratie. Hoe worden toestanden gerepresenteerd? Hoe worden acties gerepresenteerd? Wat is de algemene strategie? Illustreer en verklaar de rol van ``establish en ``treat links. Hoe kom je tot ``before links? Wat zijn de 2 principes van ``least commitment? Hoe kan je de begin- en eindtoestand uitdrukken met behulp van operatoren? Welke aspecten spelen een rol bij het plannen met operatoren patronen?

Voorbeeld Oefeningen

  • Los iets op via automatische redenering. Je krijgt een aantal zinnen, zet deze om in predikatenlogica, normaliseer deze en stel dan een bewijs op via inconsistentie.
  • Een version spaces probleem. Gegeven een situatie, enkele trainingssituaties en hiërarchieën, pas nu het version spaces algoritme toe, zeg waar je aan pruning doet en waarom. Voorspel daarna de uitkomst van enkele fictieve situaties.