Datastructuren voor AI - practicum: verschil tussen versies

Versie van 20 jan 2016 om 10:38

Opzet

Het practicum datastructuren voor AI bestaat in 2016 uit twee delen:

• Een plenaire opdracht: een stapsgewijze opgave over hashtables en andere dictionary-achtige datastructuren. Je moet ze eerst bouwen en dan hun performance vergelijken. De deliverables zijn je sourcecode en een verslag met bediscussiering van je resultaten.

• Een keuzeopdracht waarin je een AI-case mag kiezen en die uitprogrammeert naar hoe jou goed lijkt. Deliverables zijn je sourcecode en een presentatie aan het eind van het vak.

Plenaire Opdracht

1) Het bestand [buildingbrains.java] is een enorme lijst van engelse woorden. Het doel is deze in het geheugen van de computer op te slaan en te gebruiken als woordenboek, om te kijken of de woorden uit de samplebestanden [link2] goed geschreven zijn. De eerste stap is dus een programma schrijven voor het inlezen van de woordenlijst, en deze op te slaan in een array. Dat is meteen je eerste datastructuur. Daarna lees je één voor één de samplebestanden in, en kijk je of de woorden uit deze samplebestanden in de woordenlijst voorkomen. Je programma moet dus voor ieder woord uit ieder bestand 'ja' of 'nee' teruggeven, en that's it. Meet hoeveel tijd het verifieren van een samplebestand kost, maar: alleen het verificatieproces zelf, dus niet het inlezen, uitprinten of opstarten.

2) We gaan het anders doen. In plaats van een array om de woorden in op te slaan, maak je nu een hash table met open adressing. Als dat nog niet in college is behandeld geeft dat niks, gebruik gewoon google en begin eraan. Het kiezen van een goede hashfunctie is heel belangrijk, maar het allerbelangrijkst is dat je hashtable werkt. Lees weer alle bestanden in en meet weer hoeveel tijd het nu kost om ieder samplebestand te verifieren. Vergelijk de performance met de array uit punt 1. Als je dit punt goed wil doen, varieer dan de grootte van de array achter de hashfunctie, en verifieer nogmaals de samplebestanden. Documenteer je resultaten goed, want je moet het straks inleveren.

3) Naast een hashtable met open adressing bestaat er nog een belangrijke hashtablevariant: de hash table met collision chaining. Maak zo'n hash table, lees opnieuw de samplebestanden in een kijk hoe lang het duurt om de samplebestanden te valideren. Als je nog tijd hebt, kijk dan eens of er verschil is tussen de bestanden, of probeer een extra hash functie.

4) [optionele sectie voor extra punten] Misschien dat een trie nog wel beter presteert dan beide hashtables. Of misschien heb je zelf wel een idee voor een datastructuur. Maak nog een trie, of een andere datastructuur naar keuze, wederom uit primitieve types. Lees weer alle samplebestanden in, en meet hoe lang het verificatieproces duurt. Als je deze sectie completeert kun je extra punten scoren op je cijfer voor het practicum.

5) Maak een overzicht van de tijdconsumptie van de verschillende datastructuren die je in punten 1-4 hebt gemaakt. Is er verschil? Hoeveel? Is het verschil te relateren aan de samplebestanden? Hoe? Maak duidelijke grafieken en/of tabellen en bediscussieer je resultaten. Niet meer dan 4 pagina's, maar wel precies zijn in je resultaten en alleen opschrijven wat je zeker weet.

Keuzeopdracht

Legends of Arborea	RentaRoom	Leeuwen & Lammetjes
Fantasy & Flanking.	Old game, new rules	The lamb that whoops the lion's manes.
SimpleChess	Rush Hour	Sliding Triangles
Chess with fewer rules.	Spitsuur!	Een schuifpuzzel.

Status (januari 2016)

We zijn in de tweede verbeterslag van het practicum bezig. Het practicum bestaat nu uit twee delen

Toetsing

Toetsing berust op twee deliverables en één interview:

1) We gaan op X maart je programma doornemen en willen je sourcecode ontvangen. Het doornemen is om te controleren of je je code zelf hebt geschreven, het inleveren om je code te beoordelen.

2) Met de ingeleverde code willen we een beschrijving, op papier, van vijf algoritmes of datastructuren die je gebruikt hebt in je programma met de keuzeverantwoording en/of de complexiteitsfunctie.

Deze twee deliverables samen vormen je projectcijfer. Je projectcijfer vormt weer de helft van je eindcijfer.

Opzet

De opzet is vrij eenvoudig: kies met je partner één van de vier games, of één van de twee puzzlesolvers en programmeer deze uit. Dat mag met any means necessary, maar moet wel in JAVA, zodat we je code kunnen lezen en kunnen corrigeren. Als je kunt, gebruik dan zinnige datastructuren voor je game maar dwing dat niet af, dat doen wij ook niet. Denk ook aan je algoritmes: hoe sneller hoe beter, en als je de complexiteitsfunctie O(f(n)) van een methode laag kunt houden, wordt dat zeker gewaardeerd.