last updated: 23/5/05

 

ACADEMIEJAAR 2004-2005

Begeleiding programmeerproject Wiskunde voor Informatici II --- Dr. Ann Dooms

 

PROJECT TW2

Op deze pagina vind je alle informatie in verband met het project WvI2: belangrijke data, projectopgaven met referenties en praktische info.

 

Belangrijke data

indienen onderwerp (per mail): maandag 28 februari

indienen theorieverslag: vrijdag 25 maart voor 17u: Naam_Voornaam.pdf via email

indienen eindverslag+code: vrijdag 27 mei voor 17u (10F745). Inbinden, mapjes etc niet nodig, gewoon uitprinten en vastnieten is voldoende.

projectverdediging: 24 juni.

back to top

 

Praktische Info

Vragen

Voor algemene vragen over het projekt kunnen jullie de mailinglijst van TW2 te gebruiken (o9553@elvas.vub.ac.be). Voor specifieke vragen sturen jullie nest een mailtje naar mij (Ellie.DHondt@vub.ac.be).

Algemeenheden

Het programmeerproject voor de 2de kandidatuur wordt verplicht in Scheme geschreven. 

Over de deadlines wordt niet gediscusieerd. Voor iedere week te laat voor om het even welke deadline verlies je 2 punten van je eindcijfer.  Ben je meer dan 2 weken te laat voor om het even welke deliverable, dan wordt het hele project met een afwezigheid gekwoteerd. 

Heb je in 1e zit al het project meegedaan, en tussen 10 en 12 gehaald, dan kan je je project verderzetten. Stuur dan gewoon even een mailtje om af te spreken.

Theorieverslag/oefeningenverslag

Op vrijdag 25 maart geef je het verslag van het wiskundig gedeelte van je project af voor 17u in lokaal 10F745. Voor project 1 en 2 betekent dit de opgeloste oefeningen. Voor projecten 3-13 is dit een theorieverslag van ongeveer 10 blz, waarin je de de wiskundige theorie waarop je project steunt overloopt.

Eindverslag + Code

Op vrijdag 27 mei (dit is net voor de paasvakantie) geef je je eindverslag en code af, voor 17u in lokaal 10F745. In het eindverslag bespreek je kort je gekozen onderwerp en hoe je dit uiteindelijk aangepakt hebt.  Geef aan welke doelstellingen je wel en niet gehaald hebt, en evalueer je gemaakte keuzes. Bespreek de design van je project en beschrijf de structuur en de belangrijkste onderdelen van je code. Dit alles op maximum 5 blz (enkel eindverslag, code komt hier nog bovenop).

Samen met je eindverslag geef je ook je code af. Zorg ervoor dat je code geindenteerd is, en dat de files in een logische volgorde zijn afgeprint. Bij je code voeg je een inhoudsopgave, zodat we snel een specifiek deel kunnen terugvinden.

Verdediging

De projectverdedigingen gaan door tijdens de 1e zittijd. De verdediging bestaat uit 2 onderdelen: een wiskundig gedeelte en een demo. Ten eerste wordt je kennis van de ondersteunende theorie wordt getoetst, adhv oplossen van een oefening (project 1-2) of een theorievraag uit je verslag (project 3-13), dit alles schriftelijk. Daarnaast geef je een demo waarin je aan de hand van een duidelijk en realistisch voorbeeld toont hoe je code in elkaar zit. Ook moet je een korte rondleiding door je code geven (structuur, kernaalgoritmes). De demo mag uitgevoerd worden op je eigen laptop of dien je naar mij te mailen als je geen eigen laptop hebt. Het is je eigen verantwoordelijkheid ervoor te zorgen dat je project beschikbaar is voor de demo op het examen. Een niet werkend project betekenen automatisch puntenverlies.

Evaluatie van het project

De evaluatie van het project gebeurt op basis van je verslag en je verdediging. Hierbij zullen we evenveel belang hechten aan wiskunde- als informatica-aspecten (50/50):

wiskunde-aspecten: Er wordt er van jullie verwacht dat je de onderliggende wiskunde kent en in zijn context kan plaatsen. Zorg ervoor dat je de wiskunde begrepen hebt vooraleer je aan het eigenlijke programmeren begint. Het wiskundeverslag is hiervoor een noodzakelijke houvast. Dit verslag wordt ook als basis gebruikt voor het theoriegedeelte van het projectexamen, waar onderzocht wordt of jullie de wiskundige concepten, structuren en abstracties kennen, of de oefeningen zelfstandig kunnen oplossen. Je hebt er dus alle belang bij dit verslag goed op te stellen! Ontbreken van cruciale elementen betekent niet dat je daarover niet ondervraagd wordt, integendeel!

informatica-aspecten: Je code wordt geëvalueerd aan de hand van dezelfde kwaliteitseisen als voor het jaarproject, waarbij je eindverslag als leidraad wordt gebruikt. Het is dus weeral in je eigen belang dit verslag goed op te stellen! Er wordt van je verwacht dat je ook in dit (wiskunde)project deze eisen nastreeft! We hoeven je natuurlijk ook niet te vertellen dat je regelmatig backups neemt, en je code goed documenteert.Anderzijds word je ook gekwoteerd op je verdediging. Het is niet alleen belangrijk juiste en gestructureerde code te schrijven, maar ook om over het functioneren van deze code goed en duidelijk verslag uit te brengen, dit beide in je eindverslag en op de demo.

De deliverables die je afgeeft op of voor de deadline zijn de enige documenten die wij zullen bekijken en evalueren.  Je mag dus nog wel verderprogrammeren nadat je je code hebt afgegeven (bijv. om je demo op de verdediging beter te maken), maar wij zullen enkel de afgegeven code in rekening brengen bij de evaluatie.

Avond- en werkstudenten

De avond- en werkstudenten dienen zich te houden aan dezelfde deadlines als de gewone studenten.  Is er een probleem vanwege overlap met werkuren, stuur dan gewoon even (op tijd!) een mailtje.

back to top

 

Projectopgaven

De eerste 2 projectopgaven sluiten het nauwste bij de theorie aan. Het is de bedoeling op termijn enkel op deze onderwerpen over te schakelen. Voor deze onderwerpen bestaat het wiskundegedeelte uit het oplossen van enkele oefeningen, voor de andere projectopgaven uit een theorieverslag.

De bijgevoegde referenties zijn niet exhaustief! Alle boeken in deze lijst staan ofwel al in jullie boekenkast, ofwel in de VUBbib, ofwel op 10F. Van alle projectonderwerpen zijn er verschillende referentiewerken in de bib te vinden. Het is de bedoeling daar zelf naar op zoek te gaan als je niet genoeg informatie vindt in onderstaande lijst. Vanzelfsprekend zijn er ook massa's andere interessante weblinks.

 

project1: Fractale beeldcompressie
Algoritme voor beeldcompressie aan de hand van fractalen.
Wiskunde: Enkele oefeningen over binaire beelden. Toepassen van Banach-Fixpuntstelling en Collagestelling (o.a. berekenen van affiene transformaties door stelsel op te lossen) opgaven
Programmeren:
-algoritme voor beeldcompressie en decompressie van grijswaardige beelden (kleur mag ook) adhv. collagestelling en quad-tree partities (driehoeken mogen ook)
-bespreek (en pas toe) extra mogelijke compressietechnieken
-pas ev. feature extraction toe
-pas ev. domein classificatie toe adhv. een zelf-organiserend neuraal netwerk.
[1] Stephen Welstead, Fractal And Wavelet Image Compression Techniques.
[2] Michael F. Barnsley, Fractals Everywhere.


project2: Wavelet beeldcompressie
Algoritme voor beeldcompressie aan de hand van wavelets.
Wiskunde: Enkele oefeningen over D6 wavelets. Concreet voorbeeld uitwerken met Haar Wavelets en bepalen van de D6-filter (o.a. door oplossen van een klein niet-lineair stelsel, inverteren van een matrix) opgaven
Programmeren:
-algoritme voor beeldcompressie en decompressie van grijswaardige beelden (kleur mag ook) met algemene filter en zero-tree codering
-toepassen op D6 filter(s) gevonden in oefeningen en bespreken
-vergelijk Haar, D4 en D6 en hun compressie en decompressie bij verschillende tresholds
-bespreek (en pas toe) ev. extra mogelijke compressietechnieken.

[1] Stephen Welstead, Fractal And Wavelet Image Compression Techniques.

 

project3: neurale netwerken
Studie van neurale netwerken en hun toepassingen.
wiskunde: Formele modellen vor neurale netwerken: perceptron, verschillende architecturen, leerproces (back-propagation algorithm), tijdsafhankelijkheid, Hopfield en Kohonen netten Niet-lineaire dynamische systemen.
programmeren: Uitbouw neurale netwerken architectuur. Uitwerken van toepassing(en) hierop: domein classificatie voor fractale beeldcompressie adhv. een neuraal netwerk, niet-lineaire dynamische systemen, patroonherkenning op alle vlak (beurs, taal, schrift, genen...)
[1] http://www.shef.ac.uk/psychology/gurney/notes/contents.html

[2]
http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.htmls.
[3] Stephen Welstead, Fractal And Wavelet Image Compression Techniques.
[4] Michael F. Barnsley, Fractals Everywhere.

 

project4: priemgetallen en het RSA-algoritme
Algoritme bij uitstek voor publieke sleutel encryptie en het maken van digitale handtekeningen, steunend op priemgetallen en de complexiteit van factoriseren van grote getallen.
wiskunde: Formeel bewijs van het algoritme. Hiervoor heb je enkele definities en eigenschappen vanuit getaltheorie nodig (priem, relatief priem, grootste gemene deler, Euler phi-functie, congruentie modulo n, kleine stelling van Fermat, stelling van Fermat-Euler). Veel van deze dingen ken je vanuit de cursus Discrete Wiskunde en moet je niet uitgebreid herhalen in je verslag.
programmeren: Algoritme uitwerken: sleutelgeneratie, encryptie, decryptie. Genereren grote priemgetallen, random-getalgeneratoren, priemtesten.
variant1: Cayley-Purser algoritme. Dit is een veralgemening van het RSA algoritme dat werkt met matrices. Zowel wat betreft de wiskunde als het programmeren komt hier naast het bovenvermelde matrixtheorie bij kijken.
variant2: Priemtesten. Er zijn enorm veel verschillende priemtesten (Rabin-Miller,...), dus je kan je ook hierop focuseren eerder dan op het RSA-algoritme op zich. Deze testen steunen allen op getaltheorie, dus qua wiskunde blijft dit hetzelfde als bovenstaande. Ook in dit geval moet je formeel alsook via je code kunnen aantonen hoe deze testen werken.
[1] Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An applied introduction.
[2] Neal Koblitz, A course in number theory and cryptography, bib CB511.1GKOBL9.

 

project5: lineair programmeren
Zoeken van een optimale opossing voor een set van lineaire beperkingen. Concreet betekent dit het bepalen van de doorsnede van een verzameling halfvlakken, waarbinnen je de optimale waarde van een lineaire functie zoekt. Dit kent tal van toepassingen in de praktijk (economie, luchttransport, landbouw...)
wiskunde: Het basisalgoritme steunt op enkele wiskunde lemma's en/of stellingen. Hiernaast natuurlijk de complexiteit van het probleem, algemene definities voor complexiteit (P, NP O(...) ). Lineaire algebra. Sommige toepassingen zijn inherent wiskundig en dit kan je dan ook uitdiepen in het theroiegedeelte.
programmeren: algoritme uitwerken: via het simplexalgoritme naar algemene LP. Toepassing(en) uitwerken.
[1] H.R. Lewis & C.H. Papadimitriou, Elements of the theory of computation (of om het even welk standaard boek over berekenbaarheid).en.
[2]
M. de Berg, M. van Kreveld, M. Overmars & O. Schwarzkopf, Computational Geometry

 

project6: speltheorie
Dit is een domein waar veel in te doen valt: er zijn veel verschillende spelen, spelstrategieen en onderliggende theorieën.
wiskunde: Concepten en definities uit de speltheorie. Nulsom- en niet-nulsomspelen, cooperatief en niet-cooperatief spelgedrag, combinatorieke spelen, Bayesian spelen... Anderzijds spelsemantiek, i.e. de semantiek van spelen, wat nauw gerelateerd is met logica.
programmeren: praktische kant van de speltheorie, i.e. uitbouwen platform waarin je kan spelen volgens verschillende strategieën etc. Je kan je ook focuseren op een enkele diepgaandere toepassing.
[1] http://www.gametheory.net

 

project7: cellulaire automaten
Net zoals speltheorie een uitgebreid domein waar je vanalles in kan doen...
wiskunde: cellulaire automaten als universele computers, theorie van attractoren en cyclussen, discrete dynamische systeemtheorie. Theorie van je toepassing indien die vanuit de wiskunde komt (zie onder).
programmeren: cellulaire automaat uitbouwen: (niet)-homogeen, (a)synchroon etc. Uitwerken toepassing: biologie, evolutie spiraalmelkwegstelsels, getaltheorie en textielontwerp, parallel matrixvermenigvuldigen, parallele versies van priemgetalzeven, beeldverwerking, fractalen... take your pick!
[1] http://www.stephenwolfram.com/publications/articles/ca/
[2] http://www.ddlab.com/
[3] http://www.traffic.uni-duisburg.de/

 

project8: Rijndael encryptie
Studie van het Rijndael encoderen/decoderen van informatie.
wiskunde: het eindige veld GF(2^8), polynoomrepresentatie en -rekenkunde van bytes, efficiëntie van de methode, algemene eigenschappen ivm resistentie tegen aanvallen (patroonpropagatie). Groepentheorie.
programmeren: Rijndael encryptie/decriptie. Crypto-analyse. Verwante technieken.
variant: Alternatief kan je een project maken waar je verschillende cryptografische technieken vergelijkt, en niet enkel Rijndael encryptie benadrukt. Dit kan gaan van een eerder historisch overzicht van encryptiemethodes uit WOII (waarvan de crypto-analyse hand in hand ging met de ontwikkeling van Turingmachines, beide theoretisch en in de praktijk), tot moderne cryptografische standaarden: symmetrische (bvb Rijndael), asymmetrische (bvb RSA, zie project2) en hashing algoritmes.
[1] http://csrc.nist.gov/CryptoToolkit/aes/rijndael/, http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael-ammended.pdf
[2]
http://csrc.nist.gov/CryptoToolkit/, http://csrc.nist.gov/CryptoToolkit/aes/rijndael/misc/nissc4.pdfs.
[3] Neal Koblitz, A course in number theory and cryptography, bib CB511.1GKOBL9.

 

project9: errorcorrectie
Studie van lineaire (Hamming) en cyclische (CRC) errorcorrectiecodes.
wiskunde: lineaire onafhankelijkheid, vectorruimten, Hamming metriek, gerererende- en pariteitscheckmatrix, syndroom, veeltermrekenkunde, genererende polynoom, CRC algoritme.
programmeren: encoderen/decoderen van lineaire en cyclische errorcorrectingcodes.
[1] Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An applied introduction.
[2]
http://web.syr.edu/~rrosenqu/ecc/main.htm.
[3] Neal Koblitz, A course in number theory and cryptography, bib CB511.1GKOBL9.

 

project10: fast Fourier transform (FFT)
Het fast Fourier algoritme, theorie en toepassingen.
wiskunde: commutatieve ringen, eenheidswortels, convolutiestelling, veeltermrekenkunde, werking fast Fourier algoritme, complexiteitsgedrag met definities.
programmeren: fast Fourier algoritme met varianten (iteratief, recursief, meerdimensionaal, andre transforms) met uitwerking van toepassing (signaalcompressie en -analyse, SETI, vermenigvuldigen grote getallen, DNA analyse, spectraalanalyse...)
[1]
FFT.pdf

 

project11: projectieve meetkunde
Uitbouwen van een platform waarin multiprojecties van een voorwerp kunnen getoond worden alsook transformaties kunnen uitgevoerd worden op dit voorwerp.
wiskunde: Trigonometrische formules nodig voor de verschillende projecties. Matrices. Translatievectoren. Rotatiegroep SO(3).
programmeren: implementatie van de transformaties (translaties, rotaties) en van de verschillende projecties (perspectief, obliek, orthografisch...).
[1] Om het even welk standaard werk over lineaire algebra

 

project12: navigatietechnieken
Navigatie door middel van loxo- en orthodromen, verband met kaartprojecties. Van toepassing in de luchtvaart- en scheepsnavigatie en bij navigatie door dieren (migrerende vogels bijvoorbeeld).
wiskunde: Trigonometrische formules. Kaartprojecties (Mercator, Miller, Robinson, orthografisch, gnomonisch...). Definities en bepalen van orthodromen en loxodromen.
programmeren: Kaartprojecties. Bepalen ortho- en loxodromen binnen de context van kaartprojecties. Uitwerken gekozen toepassing.
[1] http://mac.usgs.gov/mac/isb/pubs/MapProjections/projections.html

 

project13: grafalgoritmes
Theorie en implementatie van grafalgoritmes: Euler paden, Hamilton cycli, handelsreizigerprobleem, grafkleuring, cliques, algoritme van Dijkstra... Je kan verschillende van deze algoritmes bespreken, oftewel je focuseren op een bepaald algoritme, zoals het handelsreizigersprobleem, en daarvan verschillende algoritmes onderzoeken (heuristieken).
wiskunde: berekenbaarheidstheorie: definities P/NP en complexiteit, grafproblemen in deze context. NP compleetheid. Polynomiale tijdsreductie van grafproblemen naar andere problemen in NP. Graftheorie ken je vanuit de cursus Discrete Wiskunde en moet je niet uitgebreid herhalen in je verslag.
programmeren: implementeren van verschillende algoritmes. De implementatie van de ADT voor graffen is gekend vanuit Algo&Data1, het is dus de bedoeling dat je aanzienlijk verder gaat.
variant: Je kan je ook toespitsen op een welbepaalde toepassing van graftheorie in het programmeerluik van het project, bijvoorbeeld op het gebruik van grafalgoritmen voor het uitbouwen van een ad hoc wireless netwerk of een sensoren netwerk.
[1] Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An applied introduction.
[2] H.R. Lewis & C.H. Papadimitriou, Elements of the theory of computation (of om het even welk standaard boek over berekenbaarheid).sensoren netwerk.
[3] T. H. Cormen, C. E. Leiserson & R. L. Rivest, Introduction to Algorithms.
[4] http://www.antd.nist.gov/wctg/manet/adhoclinks.html
[5] http://www.research.rutgers.edu/~mini/sensornetworks.html

back to top

 

 

Praktische Info

Vragen

Voor algemene vragen over het projekt kunnen jullie de mailinglijst van TW2 te gebruiken (o9553@elvas.vub.ac.be). Voor specifieke vragen sturen jullie nest een mailtje naar mij (Ellie.DHondt@vub.ac.be).

Algemeenheden

Het programmeerproject voor de 2de kandidatuur wordt verplicht in Scheme geschreven. 

Over de deadlines wordt niet gediscusieerd. Voor iedere week te laat voor om het even welke deadline verlies je 2 punten van je eindcijfer.  Ben je meer dan 2 weken te laat voor om het even welke deliverable, dan wordt het hele project met een afwezigheid gekwoteerd. 

Heb je in 1e zit al het project meegedaan, en tussen 10 en 12 gehaald, dan kan je je project verderzetten. Stuur dan gewoon even een mailtje om af te spreken.

Theorieverslag/oefeningenverslag

Op vrijdag 25 maart geef je het verslag van het wiskundig gedeelte van je project af voor 17u in lokaal 10F745. Voor project 1 en 2 betekent dit de opgeloste oefeningen. Voor projecten 3-13 is dit een theorieverslag van ongeveer 10 blz, waarin je de de wiskundige theorie waarop je project steunt overloopt.

Eindverslag + Code

Op vrijdag 27 mei (dit is net voor de paasvakantie) geef je je eindverslag en code af, voor 17u in lokaal 10F745. In het eindverslag bespreek je kort je gekozen onderwerp en hoe je dit uiteindelijk aangepakt hebt.  Geef aan welke doelstellingen je wel en niet gehaald hebt, en evalueer je gemaakte keuzes. Bespreek de design van je project en beschrijf de structuur en de belangrijkste onderdelen van je code. Dit alles op maximum 5 blz (enkel eindverslag, code komt hier nog bovenop).

Samen met je eindverslag geef je ook je code af. Zorg ervoor dat je code geindenteerd is, en dat de files in een logische volgorde zijn afgeprint. Bij je code voeg je een inhoudsopgave, zodat we snel een specifiek deel kunnen terugvinden.

Verdediging

De projectverdedigingen gaan door tijdens de 1e zittijd. De verdediging bestaat uit 2 onderdelen: een wiskundig gedeelte en een demo. Ten eerste wordt je kennis van de ondersteunende theorie wordt getoetst, adhv oplossen van een oefening (project 1-2) of een theorievraag uit je verslag (project 3-13), dit alles schriftelijk. Daarnaast geef je een demo waarin je aan de hand van een duidelijk en realistisch voorbeeld toont hoe je code in elkaar zit. Ook moet je een korte rondleiding door je code geven (structuur, kernaalgoritmes). De demo mag uitgevoerd worden op je eigen laptop of dien je naar mij te mailen als je geen eigen laptop hebt. Het is je eigen verantwoordelijkheid ervoor te zorgen dat je project beschikbaar is voor de demo op het examen. Een niet werkend project betekenen automatisch puntenverlies.

Evaluatie van het project

De evaluatie van het project gebeurt op basis van je verslag en je verdediging. Hierbij zullen we evenveel belang hechten aan wiskunde- als informatica-aspecten (50/50):

wiskunde-aspecten: Er wordt er van jullie verwacht dat je de onderliggende wiskunde kent en in zijn context kan plaatsen. Zorg ervoor dat je de wiskunde begrepen hebt vooraleer je aan het eigenlijke programmeren begint. Het wiskundeverslag is hiervoor een noodzakelijke houvast. Dit verslag wordt ook als basis gebruikt voor het theoriegedeelte van het projectexamen, waar onderzocht wordt of jullie de wiskundige concepten, structuren en abstracties kennen, of de oefeningen zelfstandig kunnen oplossen. Je hebt er dus alle belang bij dit verslag goed op te stellen! Ontbreken van cruciale elementen betekent niet dat je daarover niet ondervraagd wordt, integendeel!

informatica-aspecten: Je code wordt geëvalueerd aan de hand van dezelfde kwaliteitseisen als voor het jaarproject, waarbij je eindverslag als leidraad wordt gebruikt. Het is dus weeral in je eigen belang dit verslag goed op te stellen! Er wordt van je verwacht dat je ook in dit (wiskunde)project deze eisen nastreeft! We hoeven je natuurlijk ook niet te vertellen dat je regelmatig backups neemt, en je code goed documenteert.Anderzijds word je ook gekwoteerd op je verdediging. Het is niet alleen belangrijk juiste en gestructureerde code te schrijven, maar ook om over het functioneren van deze code goed en duidelijk verslag uit te brengen, dit beide in je eindverslag en op de demo.

De deliverables die je afgeeft op of voor de deadline zijn de enige documenten die wij zullen bekijken en evalueren.  Je mag dus nog wel verderprogrammeren nadat je je code hebt afgegeven (bijv. om je demo op de verdediging beter te maken), maar wij zullen enkel de afgegeven code in rekening brengen bij de evaluatie.

Avond- en werkstudenten

De avond- en werkstudenten dienen zich te houden aan dezelfde deadlines als de gewone studenten.  Is er een probleem vanwege overlap met werkuren, stuur dan gewoon even (op tijd!) een mailtje.

back to top