Artificiële Intelligentie

Ga naar: navigatie, zoeken
DannyDeSchreye.jpg
JoostVennekens.jpg

Samenvattingen

Klik hier om de samenvattingen te bekijken

Nuttige links

Examens

19/01/2016 - 8u

Oefeningen:

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

Theorie:

  1. Mini-Max
    1. Discuss the Mini-Max approache 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-bata 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?
  2. 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
  2. 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*?
  2. 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.

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 eigelijk backjumping en backmarking een klein beetje nadoen
    2. dynamic rearrange search is toepasbaar is op intelligent backtracking, leg uit.


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


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?


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 prediaktenlogica. (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 vormel
    • 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 als 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
    • intuitief 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.