Rijksuniversiteit Groningen Faculteit der Wiskunde en Natuurwetenschappen
Wiskunde en Informatica
Vakbeschrijvingen voor de BACHELOROPLEIDING INFORMATICA RuG
volgens het Major-Minor Model Curriculumcommissie Informatica Januari, 2006 Laatst gewijzigd: 30-11-2007
INHOUDSOPGAVE
Inhoudsopgave 1 Afstudeerproject Computational Science & Visualisation
3
2 Afstudeerproject Intelligent Systems
4
3 Afstudeerproject Software Engineering
5
4 Algoritmen en Datastructuren
6
5 Autonome Systemen
8
6 Computational Geometry
9
7 Computerarchitectuur en Netwerken
10
8 Computer Graphics
11
9 Concurrency
13
10 Discrete Structuren
14
11 Functioneel Programmeren
15
12 Imperatief Programmeren
17
13 Inleiding Informatiesystemen
19
14 Innovative Interfaces
20
15 IT-Beroepspraktijk
21
16 Kennisrepresentatie & Redeneren
23
17 Logica
24
18 Netcomputing
25
19 Introduction Neural Networks
26
20 Objectgeoriënteerd Programmeren
27
21 Operating Systems
29
22 Oriëntatie Informatica
30
23 Oriëntatie Kunstmatige Intelligentie
32
24 Parallel Computing
33
1
INHOUDSOPGAVE
25 ProgrammaCorrectheid
34
26 Signalen en Systemen
36
27 Software Construction
38
28 Software Design
40
29 Software Engineering
42
30 Software Engineering Project
43
31 Software Requirements Analysis
45
32 Software Quality Assurance and Testing
46
33 Statistiek
48
34 Talen en Automaten
49
35 Vertalerbouw
51
36 Wiskundig Modelleren 1 (Wiskunde A)
52
37 Wiskundig Modelleren 2 (Wiskunde B)
54
2
Afstudeerproject Computational Science & Visualisation
1
Afstudeerproject Computational Science & Visualisation
Positionering van het vak Omvang 10 EC, te splitsen in Afstudeerproject I (5EC) en Afstudeerproject II (5EC).
Doelstelling De afstudeerprojecten I en II zijn bedoeld om de student de verworven kennis uit meerdere vakken te laten toepassen op een welgekozen onderwerp binnen de computational science en visualisatie.
Voorkennis De inhoud van de major Informatica. Zonodig kunnen hiaten in kennis nog worden opgevuld door enkele uren college binnen het afstudeerproject.
Eindtermen De student: • is in staat tot begrip van een gegeven probleem uit de computational science en visualisatie te komen • is in staat dit probleem wat dieper te analyseren en te bezien in termen van al bestaande kennis • is in staat zonodig de benodigde kennis wat uit te breiden • is in staat een bestaande oplossing in de literatuur te zoeken of een nieuwe oplossing voor het probleem te bedenken • bezit vaardigheid in het implementeren van de oplossing • bezit vaardigheid in het schriftelijk en mondeling presenteren van de bereikte resultaten
Werkvorm De nadruk ligt op zelfwerkzaamheid van de student. De afstudeerprojecten I en II vormen bij voorkeur een samenhangend geheel, en worden uitgevoerd onder begeleiding van een of meer docenten. In afstudeerproject I ligt de nadruk sterker op het overbrengen van kennis (mogelijk, maar niet noodzakelijk, in collegevorm), terwijl afstudeerproject II wat meer het karakter van het zelfstandig doen van onderzoek zal hebben.
Toetsing De eindbeoordeling hangt af van de getoonde creativiteit, de getoonde, werkwijze, het eindproduct, het verslag en de mondelinge presentatie. In een individueel eindgesprek worden deze aspecten besproken.
3
Afstudeerproject Intelligent Systems
2
Afstudeerproject Intelligent Systems
Positionering van het vak Omvang 10 EC, te splitsen in Afstudeerproject I (5EC) en Afstudeerproject II (5EC).
Doelstelling De afstudeerprojecten I en II zijn bedoeld om de student de verworven kennis uit meerdere vakken te laten toepassen op een welgekozen onderwerp binnen de intelligente systemen.
Voorkennis De inhoud van de major Informatica. Zonodig kunnen hiaten in kennis nog worden opgevuld door enkele uren college binnen het afstudeerproject.
Eindtermen De student: • is in staat tot begrip van een gegeven probleem uit de intelligente systemen te komen • is in staat dit probleem wat dieper te analyseren en te bezien in termen van al bestaande kennis • is in staat zonodig de benodigde kennis wat uit te breiden • is in staat een bestaande oplossing in de literatuur te zoeken of een nieuwe oplossing voor het probleem te bedenken • bezit vaardigheid in het implementeren van de oplossing • bezit vaardigheid in het schriftelijk en mondeling presenteren van de bereikte resultaten
Werkvorm De nadruk ligt op zelfwerkzaamheid van de student. De afstudeerprojecten I en II vormen bij voorkeur een samenhangend geheel, en worden uitgevoerd onder begeleiding van een of meer docenten. In afstudeerproject I ligt de nadruk sterker op het overbrengen van kennis (mogelijk, maar niet noodzakelijk, in collegevorm), terwijl afstudeerproject II wat meer het karakter van het zelfstandig doen van onderzoek zal hebben.
Toetsing De eindbeoordeling hangt af van de getoonde creativiteit, de getoonde, werkwijze, het eindproduct, het verslag en de mondelinge presentatie. In een individueel eindgesprek worden deze aspecten besproken.
4
Afstudeerproject Software Engineering
3
Afstudeerproject Software Engineering
In het afstudeerproject staat het hele traject van softwareontwikkeling en de bijbehorende technische en sociale vaardigheden centraal: 1. Zelfstandig kunnen uitvoeren van taken en rollen bij grote software-ontwikkelprojecten; 2. In teamverband kunnen werken aan het ontwikkelen van software; 3. In internationaal verband kunnen werken aan het ontwikkelen van software; 4. Het kunnen kiezen van een bij een probleem passend proces van software 5. Vormgeven van kwaliteitsbeleid rondom de ontwikkeling van software; 6. Werken met subcontractors De internationale teams van studenten voeren de software-ontwikkelopdracht uit voor een bedrijf.
Globaal verloop van het afstudeerproject Ieder deelnemend bedrijf voor de studententeams een opdracht in de vorm van een Request for Information (RFI). Minimaal twee van de teams reageren daarop met een proposal, waaruit het bedrijf dat proposal kiest dat het best bij hun wensen aansluit. Nadat een opdracht verstrekt is hebben de projectteams 10 weken de tijd om een eerste werkende versie van het product op te leveren. Dit gebeurt in nauw overleg met het bedrijf dat minimaal 1 keer per week een afspraak met het studententeam heeft. Na die 10 weken worden de studententeams opnieuw ingedeeld. Het bedrijf krijgt dan een volledig of bijna volledig nieuwe groep studenten. Deze studenten werken verder aan het product zoals dat voor de herindeling door het andere teams is opgeleverd. Deze teams hebben 10 weken de tijd om de definitieve versie van het product op te leveren. In de tweede fase van het project moet de nadruk meer liggen op onderhoud van het product. De studententeams moeten in beide delen van het afstudeerproject een deel van hun opdracht uitbesteden aan een groep tweedejaars studenten (subcontractors). In de eerste 10 weken van het project is dat bij voorkeur een opdracht rondom de gebruikers-interface van het product. De docenten van het vak fungeren voor de studententeams als een intern "Quality team". Zij doen dit op basis van Spice (ISO 15540). De bedoeling is hier vooral om de kwaliteit van het gevolgde ontwikkelproces alsmede de kwaliteit van de documenten te verhogen.
5
Algoritmen en Datastructuren
4
Algoritmen en Datastructuren
Positionering van het vak Jaar 2, omvang 5 EC.
Voorkennis Oriëntatie Informatica, Objectgeoriënteerd Programmeren, Software Design, Discrete Structuren.
Doelstelling Deze cursus heeft tot doel de student kennis, inzicht en vaardigheden te verschaffen op het gebied van datastructuren en algoritmen die in de Informatica gebruikt worden om problemen abstract te formuleren en efficiënt op te lossen. Het betreft hier een aantal standaard datastructuren (bv. lijsten, bomen en grafen), algoritmen (bv. zoeken, sorteren, kortste paden vinden, fast Fourier transform) en algoritmische methoden (greedy algoritmen, verdeel-en-heers algoritmen, dynamisch programmeren). Er wordt ruim andacht besteed aan de complexiteit van de algoritmen.
Eindtermen • De student heeft kennis van en inzicht in een aantal standaard datastructuren en van algoritmen die daar gebruik van maken. • De student kent de oplossingsstrategieën als greedy methoden, divide-and-conquer, dynamisch programmeren en backtracking. • De student heeft kennis van en inzicht in een aantal graaftheoretische problemen en de algoritmen die daartoe ontworpen zijn. • De student heeft het vermogen deze problemen te herkennen en variaties op de algoritmen te ontwerpen. • De student begrijpt de begrippen tijdcomplexiteit en geamortiseerde tijdscomplexiteit en kan deze begrippen adequaat hanteren. • De student kan de complexiteit van zulke algoritmen bepalen. • In eenvoudige gevallen kan de student de geamortiseerde complexiteit van een algoritme bepalen.
Onderwerpen Dit vak overdekt een breed gebied binnen ontwerp en analyse van algoritmen en datastructuren, zoals asymptotische notatie voor complexiteit, worst-case analyse, randomisering, algoritmische paradigma’s, waaronder greedy methoden, divide-and-conquer, dynamisch programmeren, backtracking en branch-and-bound. Ook geavanceerde datastructuren komen aan de orde, zoals priority queues, AVL-bomen, 2-4-bomen, splay trees en union-find bomen. Tenslotte behandelen we graafalgoritmen, waaronder depth-first en breadth-first traversals, topologisch sorteren, kortste-pad-algoritmen (all-pairs and single-source), en algoritmen voor minimale opspannende bomen. Aangezien lijsten, stapels, wachtrijen en bomen in de voorgaande vakken minder dan nu aan de orde geweest zijn, moet deze structuren met groter zorg geïntroduceerd worden. alle weken week 1 week week week week
2 3 4 5
week 6 week 7
efficiëntie, ordeschattingen analyse van algoritmen, pseudocode, RAM-model O-notatie, amortisatie, stapels, wachtrijen bomen, priority queues, heaps, dictionaries, hash tables zoekbomen, balanceren (AVL, 2-4), splay trees, locators sorteren, sets en selectie dynamisch programmeren, grafen (ongericht, gericht) graafsearch, samenhang gewogen grafen, kortste pad, minimale opspannende boom netwerk flow, bipartite matching
6
Algoritmen en Datastructuren
Onderwijsvormen Per week 3 uur hoorcollege, 2 uur werkcollege en 2 uur verroosterd practicum. Zelfwerkzaamheid totaal 84 uur. Er is een klein verroosterd practicum, waarin geoefend wordt met het gebruik van Javabibliotheken met algoritmen en datastructuren (waaronder de Java Collections). Hierbij wordt tevens geoefend in het schrijven van een kort schriftelijk verslag.
Toetsing Het eindcijfer is een gewogen gemiddelde van practicum (1/4) en het schriftelijk tentamen (3/4), mits geen van de onderdelen onder de 5 is.
Literatuur De cursus wordt gegeven aan de hand van M.T. Goodrich en R. Tamassia, Algorithm Design. Foundations, Analysis, and Internet Examples (http: //ww3.algorithmdesign.net), John Wiley & Sons, Inc., 2002
7
Autonome Systemen
5
Autonome Systemen
Plaats in het curriculum Jaar 1, 1e semester. Omvang 5 EC. Verzorgd door Kunstmatige Intelligentie.
Doelstelling Verkrijgen van inzicht in de mogelijkheden en ontwerpaspecten van autonome systemen.
Inhoud Autonome systemen worden gekenmerkt door het feit dat hun gedrag gebaseerd is op een combinatie van de kennis in het systeem en informatie die uit de buitenwereld gehaald wordt. Hierbij kan gedacht worden aan robots, maar ook gesimuleerde agents die in een elektronische wereld functioneren. Een autonoom systeem heeft meestal als doel een taak te verrichten in een niet geheel voorspelbare of in kaart gebrachte omgeving. Het verkrijgen en verwerken van sensorische informatie uit de omgeving en aanpassing aan de omgeving zijn daarom belangrijke functies van een autonoom systeem. Onderwerpen die behandeld zullen worden zijn ondermeer: Behaviour-based architecturen, neural netwerken, genetische algoritmen, artificial life, sensoren, voortbewegen, navigatie en multi-robot systemen. Een onderdeel van het vak is het presenteren van een wetenschappelijk artikel. Daarnaast moet er een aantal practicum opdrachten worden gemaakt.
Onderwijsvorm hoorcollege (Het vak bestaat uit een serie hoorcolleges en een klein aantal practicum sessies)
Toetsing schriftelijk tentamen (essay) (Naast het tentamen wordt het eindcijfer deels bepaald door de te maken practicum opdracht en een te houden presentatie)
Literatuur Understanding Intelligence, R. Pfeifer en C. Scheier, ISBN 0-262-16181-8.
8
Computational Geometry
6
Computational Geometry
Positionering van het vak Jaar 3. Onderdeel van de Minor Computing Science. Omvang 5 EC.
Doelstelling Presentatie van elementaire algoritmen en datastructuren voor de oplossing van algemene meetkundige problemen met een algoritmisch karakter ontleend aan de praktijk van computer graphics, robotics, en geometrische optimalisatie. Ontwikkelen van vaardigheid in het toepassen van deze technieken op concrete geometrische problemen, zoals de bepaling van convexe omhullenden, het vinden van snijpunten van lijnsegmenten, berekening van triangulaties en meshes, range searching, en de constructie van Voronoi diagrammen en Delaunay triangulaties.
Voorkennis Algoritmen en datastructuren, analyse van algoritmen.
Dwarsverbanden Computer graphics, computer vision, wetenschappelijke visualisatie.
Eindtermen De student: • bezit kennis van analysetechnieken voor zowel randomized als deterministic geometrische algoritmen, en is in staat deze kennis toe te passen op elementaire algoritmisch-geometrische problemen. • bezit kennis van datastructuren voor geometrische algoritmen, zoals trapezoidal maps, k − dtrees en doubly-connected edge lists representatie van planar subdivisions. • bezit kennis van de analyse van de tijds- en geheugencomplexiteit van deterministische en randomized (geometrische) algoritmen,
Onderwijsvormen Een geïntegreerd hoor/werkcollege (totaal 4 uur per week), totaal 28 uur. Zelfwerkzaamheid totaal 112 uur.
Weekschema Week Week Week Week Week Week Week
1 2 3 4 5 6 7
Inleiding. Convexe omhullenden in 2D. Sweep-line paradigma. Triangulatie van veelhoeken. Randomized algoritmen. Lineaire programmering in 2D. Point location (randomized) in het vlak. Delaunay triangulaties. Voronoi-diagrammen in het vlak. Arrangements van lijnen, met toepassingen.
Toetsing Beoordeling vindt plaats op basis van een schriftelijke tussentoets en een schriftelijk tentamen (beide open boek). Als het tentamencijfer T hoger is dan een 5, en het toetscijfer t hoger is dan het tentamencijfer, dan is 1 2 het eindcijfer gelijk aan 3 t+ 3 T , anders is het eindcijfer gelijk aan het tentamencijfer. Bij herkansingen is het eindcijfer gelijk aan het tentamencijfer.
Literatuur De cursus wordt gegeven aan de hand van: M. de Berg, M. van Kreveld, M. Overmars en O. Schwarzkopf: "Computational Geometry. Algorithms and Applications", Springer-Verlag, 2000 (second edition).
9
Computerarchitectuur en Netwerken
7
Computerarchitectuur en Netwerken
Positionering van het vak Jaar 1, studielast 5 EC.
Doelstelling en eindtermen Het goed doorgronden van de werking, opbouw en implementatie van een computer, alsmede een netwerk van computers. Het leren werken met, een groot aantal geheel verschillende, abstractieniveau’s bij de structurering van dergelijke complexe systemen.
Voorkennis • Inl. Logica, Discrete structuren : boolese algebra, normaalvormen, dualiteit. • Oriëntatie informatica. • Imperatief programmeren.
Onderwerpen Uitgaande van de elementaire bouwstenen uit digitale techniek worden de machines gebouwd die onze programma’s uit kunnen voeren. De behandeling is bottom-up, gebruik makend van de gebruikelijke structurering in abstractieniveau’s zoals het bekende 7-laags referentie netwerk model. In het architectuurdeel komen aan de orde: • Mechanisch rekenen, de eindige automaat en zijn implementatie in digitale techniek. • Processor, control unit, datapad, microprogrammering. • Pipelining, (branch) cacheing, meerdere functionele eenheden, speculatieve executie. • Machinetaalprogramma’s: instructies, adresseringsmethoden, procedure mechanisme. • Excepties, supervisor mode, memory managment unit, virtualisatie. In het netwerkdeel behandelen we naast een uitgebreide introductie op alle lagen verder alleen de onderste netwerklagen. De netwerk-, transport- en hogere lagen worden in het vak NetComputing behandeld. • Het netwerklagen model, introductie op alle netwerklagen. • Fysieke laag: communicatie capaciteit, transmissie media, (mobiele) telefoonsysteem. • Datalink laag: fouten controle, flow control, sliding window protocollen.
Literatuur • Tanenbaum, Structured Computer Organization (5), Prentice Hall, 0-13-148521-0 • Tanenbaum, Computer Networks (4), Prentice Hall, 0-13-066102-3
Werkvormen Hoorcollege 4 uren, verroosterd practicum 2 uren, practicum 3 uren, zelfwerkzaamheid (totaal) 80 uur
Toetsing Schriftelijk tentamen en practicum verslagen.
10
Computer Graphics
8
Computer Graphics
Positionering van het vak Jaar 3. Omvang 5 EC.
Doelstelling Presentatie van de basisbegrippen op hard- en software niveau in ontwerp, implementatie en gebruik van grafische systemen en algoritmen. Bevorderen van inzicht in de werking van grafische systemen, de wiskundige modellering van grafische operaties, ontwerp van grafische algoritmen en hun implementatie.
Voorkennis Lineaire algebra (i.h.b. matrix-vector rekening). Analyse/numerieke wiskunde: integreren en differentiëren van functies.
Dwarsverbanden Beeldbewerking, computer vision, wetenschappelijke visualisatie, meetkundige algoritmen, objectgeörienteerde technieken.
Eindtermen De student: • bezit kennis van de basisbegrippen van grafische systemen (raster- en vectorgraphics, grafische pijplijn) • bezit kennis van elementaire grafische algoritmen (rasterisatie, transformaties, viewing, zichtbaarheid, ray tracing), object representaties (polyhedra, krommen en oppervlakken, procedureel), en modellen (belichting, kleur). • bezit kennis van de elementaire analyse en lineaire algebra benodigd voor de analyse van grafische algoritmen (vector- en matrixrekening, analyse van functies van één of meer variabelen) • bezit vaardigheid in de implementatie van eenvoudige grafische algoritmen m.b.v. OpenGL • bezit vaardigheid in het samenwerken met medestudenten in het uitvoeren van praktikumopdrachten • bezit vaardigheid in het verslag doen van praktikumopdrachten
Onderwijsvormen Een mengvorm van hoorcollege (2u p.w.) en verplicht practicum (6u p.w.), totaal 56u. Dit bestaat uit een aantal sessies met opdrachten. Zelfwerkzaamheid totaal 84u.
Weekschema week 1 2 3 4 5 6 7
onderwerp Overzicht grafische systemen; Bresenham lijn– en cirkelalgoritmen; Primitieven, attributen, 2D transformaties. 2D windowing en clipping; 3D object representaties; generatie van krommen en oppervlakken, splines. 3D transformaties; 3D viewing; perspectief. Hidden line/surface eliminatie. Belichtingsmodellen, shading; Kleurmodellen. Ray tracing; Radiosity. Procedurele objectrepresentaties (fractalen, shape grammars).
Toetsing Beoordeling vindt plaats op basis van een schriftelijk tentamen (gesloten boek) en het praktikum. Het eindcijfer wordt als volgt bepaald: (2×tentamencijfer + 1×praktikumcijfer)/3. Tentamen- en practicumcijfer moeten beide minimaal een 5 zijn.
11
Computer Graphics
Literatuur De cursus wordt gegeven aan de hand van:
1. D.D. Hearn & M.P. Baker, "Computer Graphics with OpenGL, 3/E", 3rd ed., 2004, Prentice-Hall, ISBN 0-13-120238-3. 2. Syllabus Lab Sessions Computer Graphics.
12
Concurrency
9
Concurrency
Positionering van het vak Jaar 3. Onderdeel van de Minor Computing Science. Studielast 5 EC.
Doelstelling en eindtermen Het in grote lijnen doorgronden van de werking en opbouw van Operating Systems.
Voorkennis Computerarchitectuur en Netwerken
Inhoud Het vak Concurrency heeft als doelstelling begrip en vaardigheden aan te leren die noodzakelijk zijn voor geavanceerde vormen van thread programming, voor gedistrueerde berekeningen, voor communicatie tussen processen of processoren, en voor het ingrijpen in het operating system. Het gaat hierbij primair om de samenwerking van sequentiële processen met of zonder gemeenschappelijk geheugen. Dit kan een groot aantal computers in een wereldwijd netwerk betreffen, of een beperkt aantal processoren in één computer, of een aantal verschillende processen dat schijnbaar gelijktijdig op één processor geëxecuteerd wordt. Het gaat er steeds weer om programma’s te ontwerpen zodat deze processen een bepaalde taak op de juiste wijze gecoördineerd uitvoeren. Problemen hierbij zijn ondermeer: wederzijdse uitsluiting; ondeelbare acties; deadlock; fairness; gedistribueerde systemen. Bruikbare mechanismen zijn seinpalen (semaforen); conditievariabelen; communicatie door boodschappen, asynchroon en synchroon; remote procedure call; rendezvous. Het vak bouwt voort op Programmacorrectheid, is complementair met Parallel Computing en Operating Systems, en is voorbereidend voor de mastervakken Automated Reasoning en Distributed Systems.
Literatuur Diktaat Concurrent Programming (W.H. Hesselink, 2004)
Werkvormen hoorcollege 2 uren, werkcollege 2 uren, practicum 6 uren.
Toetsing Schriftelijk tentamen.
Weekschema 1. Introductie 2. Busy waiting 3. Barriers 4. Semaforen 5. Java 6. Posix threads 7. Message passing
13
Discrete Structuren
10
Discrete Structuren
Positionering Jaar 1. 5 EC.
Voorkennis Logica (1e jaar, 1e semester).
Doelstelling Doel van deze cursus is de student bekend en vertrouwd te maken met een aantal basisbegrippen uit de discrete wiskunde die gebruikt worden om op abstract niveau de werking van computers en programmatuur te beschrijven en te begrijpen. Speciale nadruk wordt gelegd op wiskundige bewijzen, als correcte redeneermethode over wiskundige begrippen en uitspraken.
Eindtermen De student • heeft kennis van en inzicht in een aantal begrippen uit de verzamelingenleer en de discrete wiskunde: verzameling, functie, relatie, kardinaliteit, gehele en rationale getallen, graaf, boom, ordening, Boole-algebra; • kan bewijzen opstellen van eenvoudige eigenschappen van deze begrippen; • is bekend met diverse bewijsvormen, zoals bewijs uit het ongerijmde en bewijs met volledige inductie; • kan eenvoudige recurrente betrekkingen oplossen, bv. de rij van Fibonacci; • heeft inzicht in het verband tussen de propositielogica en de Boole-algebra, en kan beide toepassen bij het analyseren en ontwerpen van eenvoudige logische netwerken.
Onderwerpen • Elementaire getaltheorie: deelbaarheid, priemgetallen, ggd, kgv. • Elementaire verzamelingenleer: verzameling-notatie, doorsnede, vereniging, complement, verband met propositionele connectieven, cartesisch product, eindige kardinaliteit, paradox van Russell, relaties, functies (injectief, surjectief, bijectief). • Oneindigheid: definitie van gelijkmachtigheid en aftelbaarheid, aftelbaarheid van de verzameling der rationale getallen, diagonaalmethode van Cantor. • Relaties: eigenschappen (reflexief, symmetrisch, transitief, antisymmetrisch, lineair, functioneel), equivalentierelaties, equivalentieklassen, partities, partiële ordeningen, grootste / kleinste / maximaal / minimaal element, kleinste bovengrens, grootste benedengrens. • Wiskundige √ bewijzen: rol van logische redeneerprincipes, bewijzen uit het ongerijmde (irrationaliteit van 2, oneindigheid van het aantal priemgetallen), bewijzen met volledige inductie. • Recurrente betrekkingen: oplossen van lineaire rcurrenties van diepte 2. • Grafen: knopen en kanten, gericht en ongericht, paden, samenhang, graad, ingraad, uitgraad, isomorfie, Eulerpaden, bomen, opspannende bomen. • Boole-algebra’s: atomen, Boole’se expressies, logische netwerken.
Onderwijsvormen Per week 4 uur hoorcollege en 4 uur werkcollege.
Toetsing Schriftelijk tentamen.
Literatuur Kenneth A. Ross & Charles R.B. Wright, Discrete Mathematics (of een vergelijkbaar leerboek) Aanvullende syllabus
14
Functioneel Programmeren
11
Functioneel Programmeren
Positionering van het vak Jaar 2. Omvang 5 EC.
Doelstelling Een programma in een functionele programmeertaal kan ruwweg tien keer zo kort zijn als een imperatief programma met dezelfde functionaliteit. De executiesnelheid is echter minder. Functionele talen zijn bij uitstek geschikt voor algoritme-ontwikkeling en "rapid prototyping". In een functionele taal heeft een variabele binnen zijn scope overal dezelfde betekenis (referential transparency). Hierdoor zijn functionele programma’s relatief gemakkelijk te analyseren. In Haskell en sommige andere functionele talen wordt de waarde van een expressie pas berekend als dat nodig is (lazy evaluation). Dit maakt het mogelijk met oneindige datastructuren te werken (b.v. de lijst van alle priemgetallen). Functionele talen zijn gebaseerd op het gebruik van functies die desgewenst functies als argument kunnen hebben en functies als resultaat kunnen opleveren. De typering van een functie of expressie is dus van groot belang. Het doel van de cursus is, dat je een scala van functionele programma’s leert ontwerpen en analyseren, waarbij ook inzicht in de efficiëntie en in algemene typeringsaspecten van belang is.
Voorkennis Logica, discrete structuren
Dwarsverbanden Automaten.
Eindtermen De student: • leert een scala aan functionele programma’s ontwerpen • leert functionele programma’s analyseren • verkrijgt inzicht in de efficiëntie van functionele programma’s • verkrijgt inzicht in de algemene typeringsaspecten van functionele programma’s
Onderwijsvormen Practicum en werkcolleges; indien nodig hoorcollegesessies. De nadruk bij dit vak ligt sterk op zelfstudie.
Weekschema week
onderwerp
1
Ch. 1 t/m Ch. 7 uit het cursusboek met de nadruk op de praktijk van Haskell plus standaardfuncties. In aanvulling op de praktijkgerichte zelfstudiestof van cursusweek 1: par. 17.4 (pp. 344– 349), nogmaals over lijstcomprehensie. Verder op theorieniveau: Ch. 8, met name m.b.t. inductie op lijsten, en het stukje uit par. 10.9 (p. 139) over extensionaliteit. Ch. 9, Ch. 10 en Ch. 13 Oneindige lijsten en lazy evaluation: Ch. 17, alles behalve par. 17.5, par. 17.8 en par. 17.9. Aanvullende tekst over "sparser"("simple parsers") als opstap naar par. 17.5 over parsers en parser combinators. Ch. 14, enkel: par. 14.1, 14.2, 14.3, uit Ch. 17: alsnog par. 17.5 Uit Ch. 12, "Overloading and Type classes", enkel: par. 12.1, par. 12.2 en par. 12.4 t/m Ord, Uit Ch. 19, "Complexity", enkel: par. 19.1, par. 19.2 en par. 19.6 t/m fibs. Bovendien, bij wijze van herhaling: Ch. 13. Algehele theorie, mede opgaven-gerelateerd, over "(line-by-line) calculations", zoals die in het cursusboek te vinden is op de volgende pagina’s: 17–18, 23–24, 37, 41, 60–61, 255, 340–344, 344–346, 418–420.
2
3 4
5 6
7
15
Functioneel Programmeren
Toetsing Practicumopdrachten en tentamen. Het eindcijfer is een gewogen gemiddelde van het practicumeindcijfer en het tentamencijfer. Als randvoorwaarde voor een voldoende eindcijfer gelden tevoren meegedeelde ondergrenzen.
Literatuur "Haskell: the craft of functional programming"van Simon Thompson (Addison-Wesley, 2nd ed., first published 1999, ISBN 0-201-34275-8). Extra materiaal betreft een tekst over "sparsers", of wordt aangeboden via het web.
16
Imperatief Programmeren
12
Imperatief Programmeren
Positionering van het vak Jaar 1, 1e semester. Omvang 5 EC.
Inleiding Het vak Imperatief Programmeren vormt samen met de vakken Objectgeoriënteerd Programmeren A en Objectgeoriënteerd Programmeren B de brede basiscursus imperatief en objectgeoriënteerd programmeren. In deze eerste cursus komen de gebruikelijke controlestructuren uit imperatieve talen aan de orde (keuze, herhaling, recursie); methoden worden in eerste instantie geïntroduceerd als mechanisme om structuur aan te brengen in het programma. Omdat de programma’s worden genoteerd in Java, zal er ook aandacht zijn voor objecten; klasse-hiërarchieën en overerving vallen buiten het bereik van dit vak. Omdat dit het eerste vak is dat de studenten volgen, wordt er ook enige aandacht besteed aan het practicumsysteem en de daarop aanwezige (standaard) programmatuur.
Doelstelling De bedoeling van dit vak is om een begin te maken met het ontwikkelen van de vaardigheid van studenten om vanuit een (informele) probleemstelling te komen tot een correct programma. Naast het behandelen van de syntax en semantiek van een aantal constructies uit de taal java, is er expliciet aandacht voor probleem-oplossen: hoe kom je van een vraagstelling tot een algoritme/programma in java.
Voorkennis Als voorkennis wordt niet anders verondersteld dan de verplichte stof uit het profiel Natuur en Gezondheid uit de tweede fase van het vwo (of daarmee vergelijkbaar). In het bijzonder zal enige vertrouwdheid met onderwerpen uit het wiskunde-programma nodig zijn.
Einddoelen • De student is in staat om op confortabele manier om te gaan met het practicumsysteem en de daarop aanwezige (standaard) programmatuur (Linux, emacs, javac, java) • De student kent de begrippen variabele en toekenning; • De student heeft een (informele) notie van het begrip toestand en kan aangeven hoe een opeenvolging van toekenningen de toestand verandert. • De student kent de basistypen in java en de onderlinge verhoudingen tussen deze typen; • De student kent de syntax en semantiek van de java-constructies if, for, while, do; • De student kent één- en meerdimensionale arrays; • De student kent de begrippen type en variabele; de student kent de begrippen klasse en object; • De student kent het begrip methode en kent het mechanisme van parameteroverdracht in java; • De student kent het begrip recursie en weet dit mechanisme in te zetten; • De student kan de orde van tijdcomplexiteit van een programma met herhalingsstructuren aangeven en beargumenteren; • De student is in staat om op adequate wijze gebruik te maken van de online API-documentatie van java, voorzover dit behandelde klassen betreft; • De student kan een probleemstelling herformuleren tot een programmeerprobleem (modelleren); • De student kan helder verslag doen van het traject van een (informele) probleemstelling tot de uitwerking in de vorm van een java-programma.
Werkvormen Hoorcollege Tijdens de hoorcolleges worden systematisch constructies uit de taal java gepresenteerd, steeds geïnpireerd vanuit een probleemstelling. Werkcollege Tijdens het werkcollege krijgen de deelnemers de gelegenheid om onder begeleiding van een docent de leerstof te verwerken aan de hand van min of meer elementaire oefeningen.
Practicum Daar waar het werkcollege bedoeld is om elementaire vaardigheden te ontwikkelen is het practicum bedoeld om de diverse vaardigheden te integreren en toe te passen in iets complexe17
Imperatief Programmeren
re probleemstellingen. Verder zal bij een aantal problemen de gevonden oplossing moeten worden gepresenteerd in een (kort) verslag.
Zelfwerkzaamheid Per week in de collegeperiode 7 uur met daarna 20 uur voor de afsluitende keuzeopdracht.
Literatuur Walter Savitch, Absolute Java 3e ISBN 13: 9780321505040 ISBN 10: 0321505042.
Collegeschema Hoorcollege twee uur, werkcollege twee uur, practicum twee per week. week 1
2
3
4 5 6
7
8
onderwerp Wat is programmeren?; editen, compileren, uitvoeren; Het practicum-systeem: Linux, emacs, javac, java; athena; (basis-)structuur van een javaprogramma; Het type int; variabelen, toekenning en sequentie; in- en uitvoer met Extractor; het if-statement. De primitieve types in java; operatoren; type-casting; de klasse Math; de klasse String; (statische) methoden met (primitieve) parameters; parameter-overdracht. Het for-statement; arrays. Klassen en objecten; de overeenkomst met typen en variabelen; objecten als bundeling van data-elementen en operatoren (methoden). Het while-statement; het do - while statement; ’oneindige’ herhaling; het break-commando. Recursie: recursieve functies uit de wiskunde; generalisatie; recursieve oplossingen bij array-problemen. Complexiteit van algoritmen: tel het aantal elementaire operaties dat het programma (maximaal) moet uitvoeren om de oplossing te berekenen (als functie van de lengte van de invoer).
Toetsing • Elke week is er een verzameling opgaven die op het practicumsysteem uitgewerkt moeten worden. De uitwerkingen moeten voor het verstrijken van de deadline door het electronisch controle systeem zijn geaccepteerd. De geaccepteerde uitwerkingen worden van commentaar voorzien; er worden geen beoordelingen gegeven. • Bij een aantal opgaven moeten de studenten (in tweetallen) een schriftelijk verslag maken; dit verslag wordt besproken met en beoordeeld door een van de begeleiders. • Tweemaal wordt er een verplicht individueel toetspracticum georganiseerd, eenmaal halverwege en eenmaal aan het eind van de college periode. De ingeleverde werkstukken worden door de begeleiders voorzien van een beoordeling. • De afsluiting wordt gevormd door een wat grotere programmeeropdracht (keuzeopdracht) die individueel wordt uitgewerkt en wordt nabesproken met een begeleider. Deze keuzeopdracht valt buiten de collegeperiode. De eindbeoordeling wordt gevormd door een gewogen gemiddelde van de gegeven beoordelingen. Een student die één of meer van de genoemde onderdelen heeft gemist krijgt geen voldoende beoordeling. Door middel van een tentamen krijgt zo’n student alsnog de mogelijkheid dit vak met een voldoende af te sluiten.
18
Inleiding Informatiesystemen
13
Inleiding Informatiesystemen
Positionering van het vak Jaar 2, omvang 5 EC.
Voorkennis Gewenst: Objectgeorienteerd Programmeren
Doelstellingen De student leert een database ontwerpen en implementeren met behulp van een database management system (DBMS). Hij kan queries en transacties plegen met behulp van Structured Query Language (SQL). Hij heeft kennis gemaakt met enkele algoritmen en datastructuren die het DBMS daartoe inzet. Een praktisch doel is het leren samenwerken met een partner uit een ander soort opleiding.
Eindtermen • Inzicht verkrijgen in het ontwerpen en het gebruik van (relationele) databases • Vaardigheid verkrijgen in de (Extended) Entity-Relationship methode van analyse en ontwerp van een database • Vaardigheid verkrijgen in het opstellen van vragen en transacties in de taal SQL • Kennis opdoen van onderliggende theorie: functionele afhankelijkheden, normaalvormen, normalisatie • Kennis van het netwerkmodel (legacy software) • Kennis van in het DBMS gebruikte datastructuren: hashtables, indexen, B + -bomen • Kennis van concurrency control in een DBMS: locking, timestamps • Leren samenwerken met studenten van een andere opleiding (TBK/TM)
Onderwerpen week 1 week 2 week 3 week 4 week 5
week 6 week 7 week 8
overview databases; systeem architectuur; begin ER modelling ER modelling; EER modelling; UML notatie; relationele model, integriteits–constraints afbeelden van EER op het relationele model; SQL 2 (schema definitie) SQL 2 (constraints, queries) SQL 2 (asserties, views, embedded SQL) documentatie eisen vanaf dit punt is de stof alleen voor informatici functionele afhankelijkheden en normaalvormen; relatie decompositie netwerk model; data opslag, hashing; index structuren transaction processing; concurrency control; gedistribueerde databases
Onderwijsvormen Per week 4 uur hoorcollege, eerste 4 weken 2 uur werkcollege, laatste 4 weken 2 uur verroosterd practicum. Zelfwerkzaamheid totaal 92 uur.
Toetsing Het eindcijfer is, onder voorwaarde een als voldoende beoordeeld practicum, het cijfer van het schriftelijk tentamen.
Literatuur De cursus wordt gegeven aan de hand van R. Elmasri en S. B. Navathe, “Fundamentals of Database Systems”, 4th Edition, Addison–Wesley, 2004.
19
Innovative Interfaces
14
Innovative Interfaces
Positionering Periode: Jaar 3, onderdeel van de minor Computing Science. Omvang: 5 EC.
Content (preliminary) Touch-enabled display technology. Large, high-resolution information displays. Collaborative interaction on large tabletop displays. Interactive illustration. Fast high quality rendering. Non-photorealistic illustration. Image buffers.
20
IT-Beroepspraktijk
15
IT-Beroepspraktijk
Positionering van het vak Jaar 2, omvang 5 EC.
Doelstelling Het doel van het vak is de studenten in aanraking te brengen met de aspecten van de IT-beroepspraktijk naast de puur vakinhoudelijke. Aan de studenten wordt de mogelijkheid geboden zich te oriënteren op de IT-arbeidsmarkt en verder — of vooral — nader inzicht te verwerven in hoe zij hun vaardigheden effectief kunnen benutten en vergroten in werksituaties, na hun studie, maar in feite ook al tijdens hun studie.
Inhoud Onderwerpen die aan de orde komen, zijn o.a.: projectplanning, samenwerking, communicatie met niet-specialisten, management, conflicthantering, bedrijfscultuur, beroepsethiek, verkopen, vergaderen, loopbaanplanning.
Voorkennis Een specifieke formulering van voorkennis uit “die en die vakken” is hier niet van toepassing. Het gaat erom dat de student op basis van zijn activiteiten in zijn/haar voorgaande studiejaren een behoorlijk beeld heeft gekregen van de vakinhoudelijke thema’s die aan de orde komen in het eerste en in het tweede studiejaar. Daarnaast wordt verondersteld dat hij/zij een redelijk CV-basis, met “CV” van Communicatieve Vaardigheden, heeft opgebouwd waar het gaat om werken in groepjes en het schrijven van werkstukken.
Einddoelen Een formulering van einddoelen is te geven onder verwijzing naar de eerder geformuleerde dorelstelling van het vak, maar een specifiekere formulering kan enkel gegeven worden onder verwijzing naar de concrete inhouden van de gastpresentaties en van de corresponderende opdrachten. Die inhouden kunnen per jaar wisselen (maar zijn intussen wel altijd in de geest van het vak.)
Werkvormen Gastpresentaties Er zijn gastpresentaties met een aanwezigheidsplicht. In totaal zijn er zeven cursusweken, elk met een gaspresentatie van twee aanslutende collegeuren.
Zelfwerkzaamheid De formele omvang van het vak is: 5 credit points. Dit aantal komt overeen met 5*28 = 140 uren per student. Daarvan gaan er 7*2 = 14 heen aan het bijwonen van de sessies (waarvoor een aanwezigheidsplicht geldt). Blijven over: 140-14 = 126 uren. Per student zijn er per keer dus gemiddeld 126/7 = 18 uren te besteden aan het aanvullende werk, en wel samen met andere leden van een werkgroepje; de aard van dit aanvullende werk wordt verderop beschreven. Literatuur De specifieke literatuur is afhankelijk van de concrete invullingen van de gastpresentaties.
Collegeschema Er wordt, zoals hierboven reeds vermeld is, uitgegaan van één hoorcollege per cursusweek van twee uur.
Toetsing Er wordt aan opdrachten gewerkt, en wel in werkgroepjes. Deze werkgroepjes worden aan het begin van de cursus gevormd. De nagestreefde grootte van elk werkgroepje is 3 personen. Een belangrijk aspect van het hele gebeuren is: "werkgroepjes beoordelen elkaars uitwerkingen". Dit wordt als volgt verwezenlijkt. Direkt nadat, aan het begin van de cursus dus, de werkgroepjes gevormd zijn worden deze ingedeeld in twee even grote (of vrijwel even grote) hoofdgroepen: “hoofdgroep A” en “hoofdgroep B”. De ene week maken de werkgroepjes uit hoofdgroep A een uitwerking van de opdracht die door de gastspreker van die week geformuleerd wordt, de andere weeek de werkgroepjes uit de andere hoofdgroep; dit alterneert. Nadat een werkgroepje (binnen een voorgeschreven termijn) een uitwerking geproduceerd heeft, wordt deze uitwerking (eveneens binnen een voorgeschreven termen) beoordeeld
21
IT-Beroepspraktijk
door een werkgroepje uit de andere hoofdgroep. Dit geschiedt volgens een (per week wisselende) 1-1-koppeling tussen de werkgroepjes uit de ene hoofdgroep aan die van de andere hoofdgroep. Bij de samenwerking binnen de werkgroepjes op zich moeten de leden ervan te werk gaan alsof het werkgroepje de structuur van een berijf heeft. Van hun werkwijze, met wisselende rollen voor de leden van het werkgroepje, moeten ze naderhand ook verslag uitbrengen. De beoordeling omvat dus: beoordelingen van de inzet en de opgeleverde kwaliteiten bij (1) het uitwerken van opdrachten, (2) het beoordelen van uitwerken van opdrachten en (3) het verslag uitbrengen van de bedrijfsmatige werkwijzen. De aard van de opdrachten kan variëren. Het kan gaan om praktijkopdrachten, zoals het schrijven van teksten in de sfeer van acquisitie en van voorstellen voor projecten. Maar ook wordt de mogelijk open gelaten van theoretisch getintere opdrachten. Aan de uitwerking van een opdracht kan “veldwerk” verbonden zijn en/of onderzoekswerk met middelen uit de bibliotheek en/of van www.
22
Kennisrepresentatie & Redeneren
16
Kennisrepresentatie & Redeneren
Positionering van het vak Jaar 3. Omvang 5 EC.
Voorkennis Logica, Discrete Structuren, Programmacorrectheid, Automaten
Doelstelling Deze cursus gaat over logica als gereedschap voor het representeren van kennis en het redeneren daarover. De cursus begint met een behandeling van de predikatenlogica, toegesneden op logische programma’s. Vervolgens wordt de logische programmeertaal Prolog geïntroduceerd en worden diverse toepassingen behandeld. Ten slotte wordt nader ingegaan op het principe negation as failure.
Onderwijsvormen Per week 3 uur hoorcollege en 2 uur werkcollege/verroosterd prakticum
Toetsing Schriftelijk tentamen en prakticumopdrachten.
Literatuur Dictaat/syllabus (reader). PROLOG Programming for Artificial Intelligence, Ivan Bratko.
23
Logica
17
Logica
Positionering 1e jaar, 1e semester, 5 EC. Dit vak is onderdeel van het gemeenschappelijke 1e semester met Kunstmatige Intelligentie.
Doelstelling Doel van deze cursus is de student kennis te laten maken met de predikatenlogica, een wiskundig instrument voor het formuleren van en redeneren over allerhande begrippen.
Eindtermen De student • heeft kennis van en inzicht in de propositie- en de predikatenlogica (syntax, semantiek en afleidingssysteem); • kan formules van deze logica’s lezen, interpreteren en vertalen van en naar informele beweringen; • kan formele afleidingen voor formules van deze logica’s opstellen; • kan formules omzetten in normaalvormen; • heeft kennis van en inzicht in de begrippen soundness (gezondheid) en volledigheid.
Onderwerpen • Propositielogica: connectieven, propositionele variabelen, waarheidswaarden, waarheidstafels, axioma’s bewijsregels, formele afleidingen, onderlinge definieerbaarheid van connectieven, disjunctieve en conjunctieve normaalvorm. • Predikatenlogica: individuele variabelen, constanten, gelijkheid, predikaten, kwantoren, modellen, interpretaties, axioma’s, bewijsregels, formele afleidingen. • Tevens voor beide logica’s de begrippen geldig, vervulbaar, weerlegbaar, soundness (gezondheid) en volledigheid, en het vertalen van zinnen en redeneringen in de logica’s. • In het prakticum wordt gewerkt met het leerprogramma’s Tarski’s World en Fitch.
Onderwijsvormen Per week 4 uur hoorcollege, 4 uur werkcollege/computerprakticum.
Toetsing Prakticumopdrachten en schriftelijk tentamen.
Literatuur J. Barwise & J. Etchemendy, Language, Proof and logic, Stanford, CSLI Publications, 2002, ISBN 157586374X Aanvullende syllabus
24
Netcomputing
18
Netcomputing
Positionering van het vak Jaar 3, studielast 5 EC.
Doelstelling en eindtermen Dit vak bouwt voort op Computerarchitectuur en Netwerken, waarin de fysieke- en datalinklaag uit het OSI-model zijn behandeld. Aan de hand van dit model wordt de opbouw en werking van complete netwerken afgerond, waarbij de nadruk ligt op de middleware, de infrastuctuur die het mogelijk maakt om netwerktoepassingen effectief te ontwikkelen. Dit wil zeggen ontwikkelen juist zonder met het complexe onderliggende netwerken rekening te hoeven houden. Het doel van dit vak is het goed doorgronden van de werking, opbouw en toepassing van gedistribueerde netwerk systemen met name ten behoeve van de genoemde middleware laag.
Voorkennis • Computerarchitectuur en Netwerken. • Operating Systems
Onderwerpen • Medium access sublaag: MAC protocollen, ethernet (wireless) LAN’s, switches. • Netwerk laag: routerings algoritmen, congestie controle, Quality of Service, internetwerking, het Internet. • Transport laag: elementaire transport protocollen: TCP, UDP. • client/server en multitier architecturen. • Remote object invocation, code migration. • Naming, resolution, locating entities, garbage collection. • Synchronization, lamport timestamps, distributed transactions. • Consistency models, replication, • Fault tolerance, reliable client-server communication. • Security, cryptografie, authenticatie, access control, authenticatie. • Voorbeelden: distributed object en file systems: CORBA, NFS, Coda. • XML toepassingen in het Internet.
Literatuur • Wordt nog bekend gemaakt.
Werkvormen Hoorcollege 2 uren, practicum 4 uren, zelfwerkzaamheid (totaal) 98 uur
Toetsing Schriftelijk tentamen en practicum verslagen.
25
Introduction Neural Networks
19
Introduction Neural Networks
Positionering van het vak Onderdeel minor Computing Science. Omvang 5 EC.
Doelstelling The aim of the course is to provide the students with a basic knowledge of neural computation and related machine learning techniques. It serves as a preparation for more detailed studies or concrete practical applications.
Voorkennis Niet vereist.
Dwarsverbanden Pattern Recognition, Machine Learning.
Eindtermen At the end of the course, students should be familiar with • the essential ideas of neural computation and its applications • the most widely used network architectures • the basic training strategies and the implementation of the most important algorithms • the problems of model selection, overfitting and regularization and their treatment in practical situations • alternative paradigms in machine learning, e.g. unsupervised learning or alternative concepts for classification
Onderwijsvormen Een mengvorm van hoorcollege (2u p.w.) verplicht practicum (6u p.w.), en presentaties (1u p.w.) totaal 63u. Dit bestaat uit een aantal sessies met opdrachten. Zelfwerkzaamheid totaal 77u.
Weekrooster Week 1 Week 2, 3 Week 4
Week 5 Week 6 Week 7
Introduction, neurons and networks, basic ideas and architectures The Pereptron. linearly separable functions, storage capacity, perceptron algorithms, stabilty criterion, learning a rule and generalization ability Classification beyond linear separability. non-linear threshokd functions, support vector machines, multilayer networks, storage capacity, constructive and other training algorithms Regression with continuous networks. gradient based learning, backpropagation of error, universal approximators Model selection and regularization bias variance dilemma, overfitting, methods of regularization, cross-validation etc. Other topics in machine learning Bayesian classification, unsupervised learning, alternative architectures, etc.
Toetsing The final grade is based on a written exam and the project work (reports and presentations)
Literatuur Lecture notes and additional hand-outs, no text book required
26
Objectgeoriënteerd Programmeren
20
Objectgeoriënteerd Programmeren
Positionering van het vak Jaar 1. omvang 5 EC.
Inleiding Samen met het voorafgaande vak Imperatief Programmeren en het volgende vak Objectgeoriënteerd Programmeren B vormt dit vak de brede basiscursus imperatief en objectgeoriënteerd programmeren. In Imperatief Programmeren zijn objecten alleen ter sprake gekomen als mechanisme om bij elkaar horende data (samen met operatoren hierop) te clusteren. In deze cursus ligt de nadruk meer op de objectgeoriënteerde aspecten van java: overerving, grafische userinterfaces, threads. Daarnaast is er aandacht voor het exceptiemechanisme als gereedschap om de robuustheid van software te vergroten.
Doelstelling De bedoeling van dit vak is de student in te wijden in objectgeorienteerde technieken, ondersteund door de faciliteiten die de taal java biedt. Het objectgeoriënteerd ontwerpen valt buiten de scope van deze cursus.
Voorkennis De student wordt verondersteld een programmeervaardigheid te hebben die overeenkomt met het eindniveau van het vak Imperatief Programmeren.
Einddoelen • De student is in staat om in UML-notatie gegeven klassehiërarchieën te interpreteren en om te zetten in java. • De student kent de java-begrippen klasseuitbreiding, abstracte klasse en interface en kan deze op adequate wijze gebruiken bij het implementeren van een klassestructuur. • De student kent het begrip overriding en kan dit effectief gebruiken. • De student kent de betekenis van de modifiers final, static, public, private en protected, en gebruikt ze op correcte wijze in de code. • De student is in staat om gebruikmakend van een (klein) aantal faciliteiten uit de Swing-bibliotheek een eenvoudige grafische userinterface te implementeren. • De student heeft weet van een aantal java klassen voor collecties en kan met behulp van de documentatie bij een gegeven probleem een passende keus maken voor een van deze klassen. • De student kent het begrip exceptie en kent de manier waarop in java excepties worden afgehandeld. • De student kent de manier waarop in java invoer en uitvoer wordt afgehandeld, in het bijzonder hoe invoer uit en uitvoer naar bestanden wordt gerealiseerd. • De student kent het begrip thread en weet hoe hij dit mechanisme in java-programma’s kan inzetten. De student kent de begrippen lock en synchronisatie.
Werkvormen Hoorcollege Tijdens de hoorcolleges worden systematisch constructies uit de taal java gepresenteerd, steeds geïnpireerd vanuit een probleemstelling.
Werkcollege Tijdens het werkcollege krijgen de deelnemers de gelegenheid om onder begeleiding van een docent de leerstof te verwerken aan de hand van min of meer elementaire oefeningen. Practicum Daar waar het werkcollege bedoeld is om elementaire vaardigheden te ontwikkelen is het practicum bedoeld om de diverse vaardigheden te integreren en toe te passen in iets complexere probleemstellingen. Het practicum wordt uitgevoerd in tweetallen. De uitwerkingen worden door een electronisch controlesysteem aan een aantal tests onderworpen. Uitwerkingen die niet door dit systeem worden geaccepteerd worden als niet-gemaakt beschouwd. Geaccepteerde oplossingen worden van commentaar voorzien. Verder zal bij een aantal problemen de gevonden oplossing moeten worden gepresenteerd in een (kort) verslag.
27
Objectgeoriënteerd Programmeren
Zelfwerkzaamheid Per week in de collegeperiode 7 uur met daarna 30 uur voor tentamenvoorbereiding.
Literatuur Walter Savitch, Absolute Java 3e ISBN 13: 9780321505040 ISBN 10: 0321505042.
Collegeschema Er wordt uitgegaan van één hoorcollege van twee uur, één werkcollegezitting van twee uur en één practicumsessie van twee klokuren per week. Week Week Week Week
1 2 3 4
Week 5 Week 6 Week 7
Overerving: klasse-uitbreidingen Overerving: abstracte klassen en interfaces Eenvoudige GUIs met Swing Toepassing objecten: dynamische datastructuren (gelinkte lijsten en binaire bomen) Java klassen voor collecties Exceptiemechanisme in java; Input en output Threads; synchronisatie; wederzijdse uitsluiting
Toetsing • Elke practicumopgave moet vóór het verstrijken van de aangegeven deadline zijn ingeleverd. Het ontbreken van één of meer uitwerkingen leidt tot uitsluiting van het tentamen. • Bij een aantal opgaven moeten de studenten (in tweetallen) een schriftelijk verslag maken; dit verslag wordt besproken met en beoordeeld door een van de begeleiders. • De cursus wordt afgesloten met een schriftelijk tentamen. De eindbeoordeling wordt gevormd door een gewogen gemiddelde van de gegeven beoordelingen (30% practicum, 70% tentamen).
28
Operating Systems
21
Operating Systems
Positionering van het vak Jaar 2, studielast 5 EC.
Doelstelling en eindtermen Het in grote lijnen doorgronden van de werking en opbouw van Operating Systems.
Voorkennis Computerarchitectuur en Netwerken
Onderwerpen • Historie, ontwerpstrategieën, afwegingen • Processen, threads, scheduling • Proces synchronisatie en communicatie, deadlocks • Geheugenbeheer, swapping, paging, segmentatie • Virtueel geheugen, copy on write, page replacement • File systems, toegangsmethoden, directory structuur, file sharing • Massageheugen, harde schijf structuur, RAID systemen • I/O systemen, polling, interrupts, direct memory access • Bescherming en beveiliging, toegangsrechten, capabilities, authenticatie • Linux, procesbeheer, geheugenbeheer, communicatie
Literatuur A. Silberschatz, G. Gagne & P.B. Galvin, Operating System Concepts, Seventh Edition, John Wiley & Sons, 2005, ISBN 0-471-69466-5
Werkvormen Per week: hoorcollege 2 uren, werkcollege 2 uren en zelfwerkzaamheid. Totaal: 112 uur
Toetsing Schriftelijk tentamen.
29
Oriëntatie Informatica
22
Oriëntatie Informatica
Positionering van het vak Jaar 1. Onderdeel major Informatica en major K.I. (gemeenschappelijk 1e semester) Omvang 5 EC.
Doelstelling Zoals de naam van het vak zegt, wordt een brede oriëntatie op het vak Informatica gegeven, zowel wat betreft het onderzoekveld als toepassingsgebieden. Het vak geeft antwoord op vragen als: • Wat is de geschiedenis van de informatica? • Hoe is het vakgebied ingedeeld in subdisciplines, aan de hand van ACM/IEEE, maar ook volgens de Nationale Onderzoeksagenda Informatie- en Communicatietechnologie (NOAG-ICT) 2005-2010 ? • Wat zijn de “grand challenges” in de informatica, en waar liggen dus grote onderzoeksvragen? • Waar ligt in Nederland, dan wel in Groningen de nadruk op het gebied van onderzoek? • Wat voor kennisgebieden heb ik nodig om deze grote vragen te beantwoorden, en hoe zijn die in het curriculum verwerkt? • Hoe zien (globaal) carrière-paden eruit (in bedrijfsleven of academisch)? Daarnaast moet het vak ook fungeren als verdere kennismaking met informatica-docenten in Groningen.
Voorkennis Imperatief programmeren
Dwarsverbanden Vanuit het kaleidoscopische karakter van het vak, legt het dwarsverbanden met alle andere vakken in bachelor en master, maar doet dit op een inleidend niveau. Ook fungeren de presentaties hier als extra oefening voor die bij Wetenschappelijke Basisvaardigheden.
Eindtermen De student: • heeft globale kennis van de geschiedenis van de informatica. • heeft inzicht in de indeling van het vakgebied in subdisciplines • weet wat de “grand challenges” in de informatica zijn, en waar de grote onderzoeksvragen liggen. • heeft (enige) praktische ervaring met problemen uit één van de thema’s van de Nationale Onderzoeksagenda Informatie- en Communicatietechnologie (NOAG-ICT) • heeft (enige) theoretische kennis van één van de NOAG-ICT thema’s, niet gelijk aan het voornoemde thema. • heeft inzicht in de structuur van het studie programma, en weet waar vakken voor dienen. • bezit vaardigheid in het mondeling en schriftelijk verslag doen van praktikumopdrachten
Onderwijsvormen Een mengvorm van hoorcollege (2u p.w.) en praktikumproject (40u totaal), en discussiegroepen, totaal (2u p.w.). Zelfwerkzaamheid totaal 86u. Tijdens de hoorcolleges wordt door verschillende docenten ingegaan op de verschillende belangrijke onderwerpen van de informatica. In het praktikumproject schrijven de studenten in groepjes van twee één groter programma, aan de hand ven een probleemomschrijving waarin een belangrijk onderwerp uit één van de NOAG-ICT thema’s wordt belicht. In de discussiegroepen moeten de studenten individueel een presentatie geven over een overzichtsartikel (typisch uit IEEE Computer), en daarna een discussie hierover voeren.
30
Oriëntatie Informatica
Weekrooster Week 1
Week 2 Week 3/6
Week 7
Inleiding, presentatie structuur van het vak, bespreking project onderdelen, NOAG-ICT en ACM/IEEE visie op indeling vakgebied, met koppeling naar overzichtsartikelen uit de vakliteratuur Gechiedenis van de informatica, keuzes projectonderwerpen en overzichtsartikelen gemaakt Themalezingen aan de hand van NOAG-ICT thema’s en de visies van diverse stafleden daarop; parallel hieraan geven studenten in de discussiegroepen presentaties over review artikelen, en wordt hierover gediscussieerd. Presentaties projecten
Toetsing Beoordeling vindt plaats op basis van een schriftelijk (open boek) tentamen waarin 3 of 4 essay-vragen worden beantwoord uit een groter aantal (ca 12), het praktikumproject, en de presentaties en deelname aan de discussies. Bij dit laatste wordt bedoeld dat de studentassistenten die de discussiegroepen begeleiden bijhouden wie actief deelnemen aan discussies. De mate van deelname wordt gebruikt om cijfers naar boven of beneden af te ronden. Tentamen, praktikumproject en discussiegroep bijdragen worden gemiddeld, waarbij ieder onderdeel tenminste een 5 moet zijn om een voldoende te halen.
Literatuur De cursus wordt gegeven aan de hand van: • Syllabus Oriëntatie Informatica
31
Oriëntatie Kunstmatige Intelligentie
23
Oriëntatie Kunstmatige Intelligentie
Positionering van het vak Jaar 1. Onderdeel major Informatica en major K.I. (gemeenschappelijk 1e semester) Omvang 5 EC.
Vakcode KIB.ORKI03
Doelstelling Een overzicht krijgen van de belangrijkste aspecten van de Kunstmatige Intelligentie op een inleidend niveau. Na afloop is de student bovendien bekend met het gebruikte begrippenkader en met enkele toepassingen van de Kunstmatige Intelligentie.
Omschrijving Dit college geeft een overzicht van de onderwerpen die binnen de studie Kunstmatige Intelligentie aan de orde komen. Menselijke en Kunstmatige Intelligentie worden in dit college vanuit verschillende invalshoeken belicht, waarbij de volgende onderwerpen zullen worden behandeld: wat is intelligentie, de anatomie en werking van de hersenen, verschillen en overeenkomsten tussen hersenen en computers, waarneming en gezichtsbedrog, spraakherkenning, onthouden en vergeten, taal en taalstoornissen, redeneren, verschillende vormen van leren, neurale netwerken, cognitief modelleren, bewustzijn en het filosofische lichaam/geest probleem. Ook zullen enkele toepassingen van Kunstmatige Intelligentie worden behandeld op het terrein van de kennistechnologie, de cognitieve ergonomie en de robotica.
Verplichte literatuur Hendriks, P., Taatgen, N. & Andringa, T. (eds), Breinmakers & Breinbrekers. Inleiding Cognitiewetenschap, Amsterdam: Addison Wesley Longman, 1997, ISBN. 90- 6789-893-7. Eventueel aanvullende literatuur welke wordt opgegeven tijdens het eerste college.
Opmerkingen Verzorgd door de opleiding Kunstmatige Intelligentie.
periode semester I a studiepunten (EC) 5 uren per week 4 onderwijsvorm hoorcollege toetsvorm schriftelijk tentamen (essay) vaksoort propedeuse Webpagina
http://www.ai.rug.nl/~hedderik/oki
32
Parallel Computing
24
Parallel Computing
Positionering van het vak Jaar 2, studielast 5 EC.
Doelstelling en eindtermen Achtergrond: de verwachting is dat na 2007 alle computers, ook personaalcomputers, meerdere processoren (multi-core) zullen hebben.
Doelstelling Een inleiding op architecturen, programmeerparadigma’s en andere aspecten van parallelle computers. Eindtermen • leren parallel programmeren in een data-parallelle programmeertaal (F90) en in message passing (MPI) • kennismaken met de bijzonderheden van parallelle computers • verband leggen tussen architectuur en prestatie van parallelle computers
Voorkennis computerarchitectuur; imperatief programmeren
Onderwerpen Hoorcollege • Data-parallel programmeren in Fortran 90 en High Performance Fortran. • Taxonomie: supercomputers, vector computers, parallel computers, PVP, SMP, clusters, SIMD and MIMD, shared and distributed memory, DSM, NUMA. • Opbouw van high performance processoren. Theoretische peak prestatie en efficiëntie. Benchmarks. Processor-geheugen bandbreedte. • Geheugen systemen: memory banks, cache coherence. • Message-passing programmeren in MPI. • Interconnection structures.
Practicum Programeren in F90. Programmeren in MPI. Literatuur Dictaat. Werkvormen Hoorcollege 3 uren per week. Verroosterd practicum 2 uren per week. Zelfverkzaamheid (totaal) 108 uren. Presentaties door studenten (op vrijwillige basis; onderwerp in overleg met de docent).
Toetsing Schriftelijk tentamen en practicumverslagen. Studenten die een presentatie verzorgen krijgen opslag op het eindcijfer.
33
ProgrammaCorrectheid
25
ProgrammaCorrectheid
Plaats in het curriculum Jaar 1. Omvang: 5 EC.
Voorkennis De student wordt verondersteld een vaardigheid te hebben in het programmeren in een imperatieve programmeertaal, overeenkomend met het eindniveau van het vak Imperatief Programmeren. Daarnaast zal de student vaardigheid moeten hebben in het opstellen en manipuleren van logische expressies, overeenkomend met het eindniveau van het vak Logica.
Inleiding In de cursus ProgrammaCorrectheid maakt de student kennis met een aantal technieken waarmee de correctheid van programmafragmenten op formele manier kan worden aangetoond. Uitgaande van de ervaring die de student in voorlopende programmeervakken heeft opgedaan, worden bewijsregels geformuleerd bij het keuze-statement en het herhalings-statement. Deze bewijsregels worden vervolgens toegepast bij het hand in hand ontwikkelen van programmafragmenten samen met hun annotatie.
Doelstelling Van grote stukken software is eenvoudig vast te stellen dat ze correct zijn. Geregeld echter zijn er situaties waarin het lastig is in te zien dat een programmafragment aan zijn specificatie voldoet of waarin de correctheid zo belangrijk is, dat niet vertrouwd kan worden op informele overwegingen. Deze cursus heeft tot doel de student voldoende gereedschap aan te reiken om, op momenten dat dat nodig is, de correctheid van een programmafragment formeel vast te stellen. Om te komen tot een formeel correctheidsbewijs van een programmafragment is het nodig de specificatie in een formele taal te noteren. In deze cursus is de formele specificatie veelal gegeven; op een aantal plaatsen wordt van de student gevraagd om bij een informele beschrijving een formele specificatie te ontwerpen.
Einddoelen • De student kent de bewijsregel voor de toekenning en de compositie en kan deze toepassen; • De student kent de bewijsregel voor het keuze-statement (IF) en kan deze toepassen; • De student kent de bewijsregel voor het herhalingsstatement (WHILE) en weet deze in te zetten om op systematische wijze een herhalingsprogramma af te leiden; • De student is in staat om één van de heuristieken toe te passen om bij gegeven pre- en postconditie een adequate invariant af te leiden; • De student kent de winkelhaak/slope search - methode en kan deze techniek toepassen; • De student kan bij het berekenen van recurrente betrekkingen vaststellen welke hulpinformatie aan de invariant moet worden toegevoegd.
Werkvormen Hoorcollege Tijdens het hoorcollege worden, uitgaande van aanwezige programmeerkennis, bewijsregels afgeleid. Aan de hand van voorbeelden wordt duidelijk gemaakt hoe deze bewijsregels functioneren bij het ontwikkelen van geannoteerde programmafragmenten. Werkcollege Tijdens het werkcollege krijgen de deelnemers de gelegenheid om onder begeleiding van een docent de leerstof te verwerken aan de hand van oefeningen.
Inleveropgaven Bij dit vak is het zorgvuldig noteren van een programmafragment met annotatie een dusdanig belangrijk aspect, dat studenten geregeld feedback moeten krijgen op hun manier van presenteren. Daartoe dienen de inleveropgaven: elke week is er de mogelijkheid de uitwerking van een opgave ter beoordeling in te leveren. De beoordelingen van deze uitwerkingen tellen licht mee in de eindbeoordeling van het vak.
Zelfwerkzaamheid In de collegeperiode 7 uur per week met een reserve van 40 uur voor tentamenvoorbereiding.
34
ProgrammaCorrectheid
Literatuur Programmacorrectheid (auteurs W.H. Hesselink, G.R. Renardel de Lavalette), februari 2007.
Collegeschema Er wordt uitgegaan van eerst vier weken met vier uur hoorcollege en twee uur werkcollege per week. In de resterende weken zijn er twee uur hoorcollege en vier uur werkcollege per week. week Hoorcollege 1 1 De bewijsregels voor de toekenning en de compositie; keuze statement. 2 De bewijsregel voor de herhaling: invariant en variante functie; stappenschema. 3 Kwantificaties en (constante) arrays. 4 Winkelhaakmethode: inleiding; voorbeeld. 5 Winkelhaakmethode: strategie en invariant. 6 Versterken van de invariant: segmentopgaven. 7 Diversen, i.h.b. ontwerpen van invarianten.
Hoorcollege 2 Inleiding op de bewijsregel voor de herhaling. Heuristieken om uit pre- en postconditie een invariant af te leiden; voorbeelden. Logische kwantificaties; zoekproblemen. TOETS (t/m zoekproblemen)
Toetsing De eindbeoordeling wordt voor een belangrijk deel bepaald door het resultaat van het afsluitende schriftelijke tentamen. De beoordelingen van de ingeleverde opgaven tellen licht mee (15%). Halverwege de onderwijsperiode wordt een korte schriftelijke individuele toets afgenomen. Het resultaat hiervan telt mee in de eindbeoordeling (20%). De student heeft de vrijheid om af te zien van het inleveren van uitgewerkte opgaven en/of deelname aan de toets. In alle gevallen worden deelresultaten die lager zijn dan het tentamencijfer vervangen door dat tentamencijfer.
35
Signalen en Systemen
26
Signalen en Systemen
Plaats in het curriculum Jaar 2. Omvang: 5 EC.
Voorkennis Wiskundig Modelleren 1 & 2
Omschrijving Het vak Signalen en Systemen geeft een introductie in de digitale signaalbewerking en systeemtheorie. De student maakt kennis met de in de ingenieurswetenschappen gebruikelijke vocabulaire met betrekking tot het frequentiedomein. Het vak vergt een integratie van vaardigheden uit diverse, tot nog toe in afzondering behandelde, gebieden van de wiskunde om complexere problemen op te lossen. De student maakt kennis met de beschrijving van systemen met gegeven input-output gedrag; in het bijzonder tijdinvariante lineaire systemen. Naast de voor de hand liggende tijddomein beschrijving leert de student ook het werken met een frequentiedomein beschrijving. We beperken ons in het kader van dit vak tot tijddiscrete signalen en systemen. Doelstelling Dit vak heeft een dubbele doestelling. Enerzijds maakt de student kennis met elementaire digitale signaalbewerking en systeemtheorie. Anderzijds leert de student problemen uit de werkelijkheid mathematisch te modelleren met als doel een praktisch probleem op te lossen. Daarnaast maakt de student naast de tijddomein representatie kennis met de frequentiedomeinrepresentatie.
Voorkennis De vak verlangt een algemene mathematische basisvaardigheid. Onderwerpen die als voorkennis verondersteld worden zijn: • Complexe getallen • Vector-Matrix calculus • Eerste en tweede orde lineaire differentiaalvergelijkingen • Integreren en differentiëren • Algabraïsche manipuleervaardigheid, i.h.b. met betrekking tot exponentiële functies en logaritmen Deze basisvaardigheden komen overeen met het eindniveau van de vakken Wiskundig Modelleren 1 & 2.
Einddoelen • De student verwerft een basisvaardigheid in het werken met Matlab • De student leert kleine praktische problemen op te lossen met behulp van een mathematisch (signaal-)model • De student verwerft de elementaire kennis met betrekking tot digitale filters • De student verwerft vaardigheid in het redeneren in frequentiedomein • De student leert dat een goed gekozen representatie (bijv. de frequentiedomein benadering) het probleem kan vereenvoudigen
Werkvormen Hoorcollege Tijdens de hoorcolleges wordt de leerstof gepresenteerd. De behandeling loopt grotendeels parallel aan de hoofdstukken uit het boek. Het tempo is ongeveer 1 hoofdstuk per week. Werkcollege Het werkcollege richt zich voornamelijk op het verhogen van de mathematische manipuleervaardigheid in een signaalbewerkingscontext.
36
Signalen en Systemen
Practicum Tijdens het practicum maakt de student per week in tweetallen een practicumopdracht. Bij het boek horen opgavensets die bestaan uit inleidende opdrachten en een eindopdracht. De opdrachten kunnen met behulp van de verworven theorie en Matlab worden gemaakt. De student levert een schriftelijk verslag van de eindopdracht in. Per week worden de twee beste verslagen als voorbeeld op WWW gezet. Tijdens dit practicum leert de student om in een praktische context de verworven theoretische vaardigheid te integreren en toe te passen in iets complexere probleemstellingen. Voorzover mogelijk worden hiervoor reëele technische problemen gebruikt.
Literatuur De colleges worden gegeven aan de hand van het boek J.H. McClellan, R.W. Schafer, M.A. Yoder: Signal Processing First.
Collegeschema Per week wordt 2 uur hoorcollege, 2 uur werkcollege en 2 uur practicum gegeven. Opmerking: Een extra practicum van 1 uur ongeveer een dag voor de deadline valt te overwegen. Van de student wordt per week 7 uur zelfwerkzaamheid verlangd. Inclusief de voorbereiding voor het tentamen komt dat neer op 90 uur zelfwerkzaamheid.
week 2 week 3
Onderwerpen Introductie en Harmonische functies (boek hst. 1 en 2) Spectrale representatie (boek hst. 3) Bemonstering en aliasing (boek hst. 4)
week 4
FIR filters (boek hst. 5)
week 5 week 6
Frequentie response van FIR filters (boek hst. 6) Z-transformatie (boek hst. 7)
week 7
IIR-filters (boek hst. 8)
week 1
Practicum Richting bepalen met microfoons (boek lab 2b) Muziek synthese (boek lab 3) Digitale beelden: A/D en D/A conversie (boek lab 5) FIR filters: convolutie en deconvolutie (boek lab 7) Bandfilters (boek lab 8) Telefoon: DTFM codering en decodering (boek lab 9) Polen en nulpunten (boek lab 11)
Toetsing De eindbeoordeling wordt voor 75% bepaald door het afsluitende schriftelijke tentamen en voor 25% door de beoordeling van de ingeleverde huiswerkopgaven en verslagen van computerpractica.
37
Software Construction
27
Software Construction
Plaats in het curriculum Jaar 2. Omvang: 5 EC.
Voorkennis Het vak Software Design is verplichte voorkennis.
Doelstelling Programmeren is meer dan het achter elkaar plaatsen van een aantal algoritmen. Van groot belang is in eerste instantie te achterhalen wat een klant wil dat de uiteindelijke applicatie doet en hoe die wensen zo efficiënt mogelijk (in tijd, in geld, in correctheid) worden gerealiseerd. Daarvoor is het nodig de zg. requirements van de uiteindelijke applicatie zo goed mogelijk boven tafel te krijgen uit de vaak heel vaag geformuleerde wensen van de klant. Vervolgens kan het ontwerp van de applicatie vorm krijgen en uiteindelijk kan de code worden geschreven. Middelgrote en grote applicaties vereisen een interatief proces, waarbij de weg van requirements naar uiteindelijk werkende code vele malen wordt afgelegd, en eindresultaat langzaam groeit van een applicatie met alleen wat elementaire onderdelen tot een volwaardige applicatie. Alleen middels zo’n iteratief proces zijn wijzigingen in requirements en ontwerp nog redelijk in de hand te houden. Het college beschrijft een in de praktijk veel gebruikte iteratieve methode van applicatieontwikkeling, namelijk het Unified Process. Het ontwikkelproces is minstens zo belangrijk als de realisatie van de verschillende onderdelen daarin zoals een goed ontwerp. Daarom wordt in dit college ook aandacht besteed aan het projectmatig werken in grotere teams om op een zo efficiënt mogelijke manier te komen van een opdracht tot een werkende implementatie. Het vak behandeld de theorie die in de minor Computing Science nog eens uitgebreid in de praktijk wordt getoetst.
Einddoelen De student: • heeft kennis van de OO technologie m.b.t. analyse en ontwerp • heeft kennis van UP en kan dit toepassen op niet al te grote casussen • kan een middelgroot probleem in een interatief proces analyseren en ontwerpen. • heeft kennis van UML en kan gebruik maken van de noodzakelijke UML-diagrammen in analyse en ontwerp-fase • heeft kennis van design patterns en is in staat in voorkomende gevallen een aantal patterns te herkennen en/of te gebruiken • heeft elementaire theoretische kennis m.b.t. procesmanagement (deze kennis wordt in de specialistische minor verder uitgediept en in de praktijk gebracht) • kan ontwerpen toetsen aan kwaliteitscriteria zoals performance en reliability en heeft zich een zg. engineering attitude aangeleerd • heeft gevorderde design capabilities
Werkvormen Het vak bestaat uit zowel hoor-, werkcollege’s als practica. Per week is er 1x×3 uur hoorcollege, waarin de theorie wordt uitgelegd, 1 × 3 uur werkcollege waarin op papier met die theorie wordt geoefend. Er is geen practicum. Het werkcollege wordt gegeven in de vorm van een peer-to-peer reviewing: teams van twee studenten bereiden een gedeeltelijke analyse en/of ontwerp voor van een kleine case die dan vervolgens wordt gepresenteerd en bediscussieerd met de andere studenten. Bij analyse en ontwerp is niet altijd meer sprake van goed en fout. Peer-to-peer reviewing leidt in dit geval tot het ontstaan van een zeker smaakgevoel bij analyse en ontwerpvoorstellen. Dit leidt tot 6 verroosterde contacturen per week gedurende 7 weken. Gedurende deze zeven weken en meer intensiever gedurende de laatste weken wordt daarnaast gewerkt aan een iteratieve uitwerking van een grotere case. Opm: Deze case kan mogelijk een opdracht zijn vanuit het bedrijfsleven en kan dan verder worden ontwikkeld en geïmplementeerd tijdens de minor Computing Science.
38
Software Construction
Literatuur Het vak gaat vergezeld van een uitgebreide handout van de slides, voorzien van v eel nuttig extra commentaar. Daarnaast is verplicht: • Applying UML and Patterns, an Introduction to Object-Oriented Analysis and Design, Craig Larman, Prentice Hall. • (Niet verplicht: Design Patterns, Erich Gamma et.al, Addison-Wesley, 1995, ISBN 0-201-63361-2)
Collegeschema De globale opzet is: week 1
2
3
4
5
6
7
8
inhoud OO concepten, domein analyse: - Overzicht OO-analyse en -ontwerp - OO analyse (domein modellering) - Iteratief ontwerpen Requirements analyse: - requirements engineering - activity diagrams - state machine diagrams - use cases - documentatie - risk management - requirements tracing Ontwerpen: - system sequence diagrammen - communicatiediagrammen - visibility Design patterns: - analyse patterns - grasp patterns (verantwoordelijkheden toekennen) - ontwerp patterns (GoF designpatterns) - inleiding architectuur Design by contract - formele aspecten van ontwerp - OCL Unified proces - Iterative development - Inception fase - Elaboration fase - Construction fase - Project management - estimation - lifecyclemodellen (zoals UPEDU) UP, Projectplan Software Quality - quality metrices - quality estimation - quality maturity models (zoals CMM, SPICE, PSI) Afronden eindopdracht
oefeningen
Domeinmodel
Use cases
Ontwerpfase
Patterns, Responsibility signment
as-
OCL
eindopdracht
Toetsing Het vak wordt afgesloten met een eindopdracht die in groepjes van 2 a 3 studenten wordt gemaakt. De eindopdracht is een volledig uit te werken casus, waarbij het projectplan in het werkcollege van week 7 besproken en voorbereid kan worden. De eindopdracht wordt in groepjes van 2 à 3 studenten gemaakt en aan het eind individueel met de studenten mondeling nabesproken en beoordeeld.
39
Software Design
28
Software Design
Plaats in het curriculum Jaar 1. Omvang: 5 EC.
Voorkennis Elementaire kennis van OO-programmeren.
Doelstelling Programmeren volgens het OO-principe is meer dan het simpel toepassen van classehierarchiën en overerving. Het OO-principe gaat uit van goed hergebruik van eerder gemaakte classes, van nette en leesbare code en kent een aantal veelgebruikte methodieken en handelswijzen. Het vak OOO zal een aantal van die specifieke OO-principes behandelen en studenten krijgen (praktische) oefeningen hiermee. De nadruk in dit vak ligt dan ook niet op formele aspecten, maar veel meer op praktische aspecten en heeft tot doel het aanleren van een engineering attitude met betrekking tot die OO-principes. Daarnaast wordt in het vak een inleiding gegeven in ontwerpen van grotere applicaties. Daarbij spelen zaken als verdelen van verantwoordelijkheden over de classes, hergebruik, realiseerbaarheid e.d. een veel grotere rol dan allerlei formele aspecten. In het vak zal gebruik worden gemaakt van gangbare ontwikkelomgevingen (Eclipse), waarbij zowel het ontwikkelen van de software (met elementair gebruik van ontwerptools en -diagrammen zoals uit UML) als het gebruik van GUI-builders aan bod komen.
Einddoelen De student • kent het OO-paradigma en heeft praktische kennis m.b.t. het OO-programmeren. • is in staat met een IDE (bijv. Eclipse) te werken en software te ontwikkelen • kent methoden en ideeën voor kwaliteitsverbetering van software (zoals test first programming, event driven programming, refactoring en code smells) en kan deze in de praktijk toepassen. • heeft implementatietechnieken gezien (zoals exception handling, gui, mvc, threads, applets, beans e.d.) en kan deze in voorkomende situaties goed hanteren en in de praktijk toepassen. • heeft kennis van elementaire design patterns en is in staat in voorkomende gevallen een aantal elementaire patterns te te gebruiken • kan in objectgeoriënteerd denken en is in staat bij een grotere applicatie een geschikt ontwerp met objecten te maken en verantwoordelijkheden over de verschillende objecten toe te kennen • heeft elementaire engineering attitude (kan op elementair niveau zijn software ontwerpen toetsen aan kwaliteitsattributen zoals performance en reliability) • heeft elementaire design capabilities
Werkvormen Het vak bestaat uit zowel hoor-, werkcollege’s als practica. Per week is er 1 x 2 uur hoorcollege, waarin de theorie wordt uitgelegd, 1 x 2 uur werkcollege waarin op papier met die theorie wordt geoefend en 1 x 2 uur verroosterd practicum, waarin de theorie van die week wordt geoefend in de praktijk. Dit leidt tot 6 verroosterde contacturen per week gedurende 7 weken. De resterende tijd is bedoeld voor zelfwerkzaamheid (voorbereiding werkcolleges en practica) en voor het maken van de eindopdracht.
Literatuur Het vak gaat vergezeld van een uitgebreide handout van de slides, voorzien van veel nuttig extra commentaar. Daarnaast wordt aanbevolen: • P.H. Winston, S. Narasimham, On to Java 1.2 (3rd ), Addison-Wesley, Reading, MA, 0-201-72593-2 • Bruce Eckel, Thinking in Java (2nd ed.), online te downloaden: http://www.mindview.net/Books/TIJ/
40
Software Design
Collegeschema De globale opzet is: week 1
2
3 4
5
6 7
8
inhoud Herhaling OO-concepten: class, object; interface, implementatie; properties, methods; encapsulation, private, public ; documentatie, javadoc; javacode standards; valkuilen (type bij constructor, == vs. isEqual, etc.); eenvoudige UML notatie; inheritance en delegation; single vs. multiple inheritance; dynamic binding Nested en innerclasses ; inner classes, anonymous classes Test first programming: bouwen van classes met de stoplichtmethode; testen van oo-software; een testframework; packages Persistance en serialisable Exception handling en Event driven programming: events; event handling Gui en Model View Controller: gebruik van gui’s, frames, swing package; scheiden van gui en model; patterns en gui; MVC-concept Multithreading: parallelle uitvoering van programma’s; threads; synchronisatieproblemen; synchronisatieprimitieven Refactoring en code smells: refactoring van OO software; refactoring en unit testen; code smells Ontwerpen: functioneel ontwerpen; OO-design; toekennen van verantwoordelijkheden aan classes; elementaire designpatterns Aanverwante onderwerpen: java applets; java beans; java en het net
oefeningen Oefenen met inheritance
unit testing
automatische pilot, client server systeem property editor
Threads, de Stopwatch
Code smells en refactoring Ontwerp van grotere applicatie
Toetsing De toetsing van dit vak vindt plaats middels een (individuele of in groepen van twee te maken) eindopdracht waarin alle in het vak geleerde begrippen nodig zijn om een applicatie te maken. Bij deze applicatie dient ook verslaglegging plaats te vinden, waaronder een handleiding voor het gebruik van de applicatie, een installatiehandleiding en een programmeurshandleiding waarin wordt uitgelegd hoe de applicatie in elkaar steekt. Het feitelijke ontwerp van de applicatie is ook een wezenlijk onderdeel van de rapporage. De eindopdracht dient in een mondeling gesprek te worden verdedigd. Het eindcijfer wordt gevormd door de beoordeling van deze eindopdracht (waarbij op verschillende aspecten wordt getoetst, zoals codering, ontwerp, handleidingen, juist gebruik van de behandelde methodieken, OO ontwerp). De practicumopdrachten zijn verplicht en worden met een onv, vold of goed beoordeeld. Een eindcijfer wordt alleen bepaald als alle practicumopgaven minstens voldoende zijn gescored. Een onv kan hierbij met drie vold of twee goed worden gecompenseerd.
41
Software Engineering
29
Software Engineering
Plaats in het curriculum Jaar 2. Omvang: 5 EC.
Voorkennis Software Engineering majorvakken.
Inleiding Dit vak geeft een verdieping van de stof zoals besproken in het majorvak Software Management. Inhoud en collegeschema zijn feitelijk hetzelfde als bij dat vak met die aantekening dat de stof verder zal worden verdiept en de inhoud aangepast aan het masterniveau. Belangrijkste onderwerpen in dit vak zijn: • Software engineering life cycle • Requirements • Software quality management
Doelstelling Software engineering is de toepassing van een systematische, gedisciplineerde en kwantificeerbare benadering van ontwikkeling, beheer en onderhoud van software. Dit omvat verschillende activiteiten, nl. requirements engineering, architectuur ontwerp, gedetailleerd ontwerp, implementatie, validatie en evolutie. Echter ook ondersteunende activiteiten zoals configuratiemanagement en documentatie. Dit vak zal verschillende aspecten van al deze zaken verder belichten. Een meer praktische benadering en verdere toepassing van deze theorie komt terug in de specialistische minor Computing Science. De cursus is opgedeeld in een theorie- en praktijkgedeelte. In het theoriegedeelte worden de bovenstaande activiteiten behandeld. Het praktijkdeel is georganiseerd in combinatie met de vakken Afstudeerproject deel 1 en Afstudeerproject deel 2. Hierin wordt een software-consultancy bedrijf gesimuleerd waarin projectgroepen worden gevormd die voor een industriële opdrachtgever een software ontwikkel- of onderhoudsproject uitvoeren.
Werkvormen Hoorcollege 3 uren per week, werkcollege 2 uren per week en zelfwerkzaamheid (totaal) 110 uur.
Literatuur • Sommerville, Software Engineering (7th edition ), Pearson/Addison Wesley, 0321210263 • Robillard, Kruchten, d’Astous, Learning Software Processes with the UPEDU (1st edition ), Addison Wesley, 0201754541
Toetsing Toetsing van het vak vindt plaats middels een theoretisch tentamen, alsmede via door de studenten te verzorgen presentaties.
Collegeschema week 1 2 3 4 5 6 7
8
inhoud Overview, Software Processes Requirements, Requirements Engineering; Overview of RFI’s Quality; Practice of QM; Development Processes Project Management; Requirements Architecture; Reuse; Quality Verification, validation, testing Project Management Configuration management; How will you deliver?; Different platforms, DLL versions etc; Completeness of documentation; Bug handling Uitloop, afronding
42
literatuur SOM ch. 1,4,17 ROB ch. 2 SOM ch. 6 - 8 SOM SOM SOM SOM
ch 27, 28 Ch 5, 26 Ch 11-13, 18 Ch 22, 23 (4, 17)
Software Engineering Project
30
Software Engineering Project
Positionering Periode: Jaar 3, onderdeel van de minor Computing Science. Omvang: 5 EC.
Voorkennis Object Georiënteerd Ontwerpen
Omschrijving Bij het vak Productontwikkeling is het de bedoeling dat de student in een verkort traject de gehele ontwikkelingscyclus van een embedded product mee maakt. Het centrale product is de Logistic Assistent, een mobile embedded product voor de logistieke dienstverlening (koeriersdiensten). Het product wordt ontworpen op basis van een Java programmeerbare mobiele telefoon. De student zal software op de mobiele telefoon downloaden om de gewenste additionele functionaliteit van de Logistic Assistent te realiseren. De student zal onder tijdsdruk tal van vaardigheden moeten integreren om tot het gewenste resultaat te komen. Daarnaast maak de student kennis met de imperfecte buitenwereld met: eindige resources, onvolledige specificaties, onvolledige documentatie, ruis en meetfouten etc. Een belangrijk deel van de tijd zal besteed worden aan kwaliteitscontrole en beoordelen van andermans werk.
Doelstelling • De doorlopen van het ontwikkelingstraject van een product • Het maken van een klein haalbaarheidsonderzoek • Het formuleren van requirements • Het maken van een testplan op basis van de requirements • Het testen op basis van het testplan • Kennismaking met randapparatuur GPS, bleu-tooth, camera, buttons in een mobiele omgeving • Programmeren in een omgeving met beperkte resources • Kwaliteitscontrole d.m.v. applicatie testen en documentatie reviewen • Keuzes maken tussen zelf geprogrammeerde en extern vervorven software • Het leren informatie te vergaren en te beoordelen • Het omgaan met te ambitieuze doelstelligen en het zich concentreren op de essentials • Het leren omgaan met ruis, storing en andere imperfecties • het leren omgaan met interrupts en timingsproblemen • Het omgaan met ontwikkeltools en simulatoren • Het beoordelen van andermans werk
Voorkennis Dit vak verlangt een kennisniveau met betrekking tot programmeren in Java zoals verkregen na Object Georiënteerd Ontwerpen. Daarnaast worden algemene basisvaardigheden verondersteld • Algemene schrijfvaardigheid m.b.t. verslagen en technische documentatie • Algemene basisvaardigheid m.b.t. wiskunde
Einddoelen • de student krijgt zicht op de complexiteit van productontwikkeling; • de student leert systematisch werken volgens het traject haarbaarheidstudie, requirements, testplan, implementatie en testen; • de studente leert omgaan met de imperfecte buitenwereld met: eindige resources, onvolledige specificaties, onvolledige documentatie, ruis en meetfouten etc. • de student krijgt een gevoel voor kwaliteit;
43
Software Engineering Project
Beoordeling Tijdens het gehele vak is een een overdaad aan beoordelingsmomenten. Bij het testen en reviewen werkt de student zelfstandig en is hij individueel beoordeelbaar. Hierbij wordt het reviewrapport of het testrapport beoordeeld. Bij het ontwikkelen en de rapportage werkt de student in koppels en worden de studenten per koppel beoordeeld. Ontwikkelde componenten en geschreven documenten worden pas na het testen respectievelijk reviewen gecorrigeerd en definitief ingeleverd. Het gecorrigeerde werkt wordt beoordeeld.
Werkvormen Het vak kent een strikte weekcyclus waarbij iedere week een component voor het gehele project wordt afgeleverd.
Hoorcollege Het eerste hoorcollege (2 uur op de maandagochtend) heeft een meerledige functie. Het hoorcollege levert de kick-off voor de component van deze week. Daarnaast wordt een overzicht gegeven van de voor deze week benodigde technieken en theorieën. Het tweede hoorcollege (1 uur op de vrijdagmiddag) heeft een duidelijk evaluerende functie.
Brain-storm-sessie Na het eerste hoorcollege is er 2 uur tijd voor de studenten om na te denken over de opdracht van de week. Tijdens deze sessie is er begeleiding aanwezig om eventuele vragen te beantwoorden.
Practicum Er is tweemaal 2 uur tijd gereserveerd voor een begeleid practicum. Op maandagmiddag is het een practicum om de student op gang te brengen. Daarna wordt de student geacht om zelfstandig verder te werken. Tot slot is er een practicum voor de deadline om studenten met de laatste problemen te helpen.
Literatuur Een uitgebreide web-site met verwijzing naar diverse bronen. Daarnaast het boek Developing Scalable Series 40 Applications, A guide for Java Developers, M.J. Yuan and K. Sharp.
Collegeschema Het collegeschema wordt gedicteerd door de te ontwikkelen componenten:
1 2 3 4 5 6 7 8 9
Component Hello World User Interface Blue-tooth GPS; data capture GPS; tracking Camera; image capture Camera; image interpretation Integration en Server communication
44
Software Requirements Engineering
31
Software Requirements Engineering
Positionering Periode: Jaar 3, onderdeel van de minor Computing Science. Omvang: 5 EC.
Content Software requirements engineering plays a critical and fundamental role within the software development process. The goal of this course is to introduce the activities, concepts, methods and techniques needed in eliciting, modeling, analyzing, documenting, validating, and managing requirements for software-intensive systems. It explains how requirement engineering fits into the broader software development process, and provides an understanding of the main challenges in requirements engineering.
Objectives The course aims in teaching students how to to systematically establish, define, and manage the requirements for a large, complex, changing, software-intensive system. After successful completion of this course, the students should be able to • identify stakeholders and work with them effectively • apply a range of elicitation techniques • document requirements using templates and modeling techniques • analyze requirements by negotiation and prioritization • validate and prototype requirements specifications • manage changing requirements
Prerequisite Knowledge Requirement engineering is a multidisciplinary field and closely related to areas such as software development and software engineering etc. Students should have successfully completed the following courses: • Software Construction • Software Engineering • Software Development Project
Evaluation The grade will be composed of the following components: • 50%: Result of the course project (a concrete software project, whose result is presented in the classroom and documented in a report) per group, weighted by the quality of project deliverables and individual contributions. • 50%: Written examination.
Pedagogical Approach The course will include the following sections:
Class Teaching Class lectures last for 6 weeks, where fundamental knowledge about requirement engineering will be taught with short seminar discussions.
Project Presentation by Group Presentations of the project results will be held in week 4 and week 8 by each group.
Project Report by Group In the end of this course, students are required to submit a requirements report based on an concrete software project.
45
Software Requirements Engineering
Literature Mandatory • Axel van Lamsweerde. Requirements Engineering: From System Goals to UML Models to Software Specifications. John Wiley & Sons, 2007. Additional • Leszek A. Maciaszek. Requirements analysis and system design. Pearson Addison-Wesley, 2005 • Dean Leffingwell and Don Widrig. Managing software requirements: A Use Case Approach. Addison-Wesley, 2003. • Gerald Kotonya and Ian Sommerville. Requirements Engineering: Processes and Techniques. John Wiley & Sons, 1998. • I. Sommerville and P. Sawyer. Requirements Engineering: A Good Practice Guide. John Wiley & Sons, 1997. • R.J. Wieringa. Requirements Engineering: Frameworks for Understanding. Wiley, 1996.
Course Arrangement 8 weeks of lectures
1 2 3 4 5 6 7 8
Course Introduction to Requirement Engineering Basics of Requirement Engineering Project Initiation Elicitation Techniques and 1st Presentation Requirement Documentation and Modeling Requirement Analysis Requirement Validation Requirement Management and 2nd Presentation
46
Software Quality Assurance and Testing
32
Software Quality Assurance and Testing
Positionering van het vak Jaar 3. Omvang 5 EC.
Aim of the course • Create awareness for software quality improvement by testing • Teach the basic elements of software testing
Way of working The course consists of a number of lectures that explain the problems and methods of software testing. Between the lectures, the students work in groups on small assignments. The deliverables of these assignments must be submitted to the lecturer before the next lecture and will be discussed there.
Material • Course book: To be defined. • Answers to the assignments.
Foreknowledge • Principles of software project management • Principles of software development life cycles • Principles of (software) requirements management
Detailed information 1. Testing concepts • Systems Development Life Cycle • What is software testing? • How does software testing differ from quality assurance? • Quality control techniques 2. Black-box (functional) and white-box (structural) testing • Defects • Black-box testing: Testing against requirements, API testing • White-box testing: Path testing, state models • Coverage analysis 3. Testing approaches • Alpha-, beta, and gamma testing • Unit, integration testing and system testing • Regression testing 4. Risk management • Background • Definitions • Sources of Risks • Component and project Level Risks • Risk analysis • Using Risks to your Advantage 5. Test planning and design • Software Testing Process • Test Planning • Test Design 6. Test development and execution • Software Testing Process • Test Development • Unit Testing • System Testing • User Acceptance Testing
47
Software Quality Assurance and Testing
7. Testing metrics • Defect Management • Defect Recording • Defect Reporting • Defect Evaluation • Quality Metrics • Test Process Maturity 8. Test automation • Testing tools for the different software lifecycle phases • Testing environments • Pitfalls in automatic testing
Evaluation Written test, including one or more small assignments.
48
Statistiek
33
Statistiek
Plaats in het curriculum Jaar 2. Omvang: 5 EC.
Doelstelling Het verkrijgen van theoretisch inzicht in kansrekening en statistiek en het verwerven van praktische kennis voor het oplossen van statistische problemen.
Inhoud Wekelijks wordt een hoorcollege en een werkcollege gegeven. De inhoud van het college omvat globaal: basisbegrippen uit de kansrekening, enkele meest voorkomende discrete en continue kansverdelingen, schattingstheorie met de nadruk op meest aannemelijke schatters, hypothesetoetsing, het opstellen van betrouwbaarheidsintervallen en regressie-analyse. Verder wordt beknopt behandeld: beschrijvende statistiek, variantie-analyse, niet-parametrische statistiek en robuuste statische procedures.
Onderwijsvorm hoorcollege, werkcollege
Toetsing schriftelijk tentamen (essay), schriftelijk tentamen (meerkeuze), schriftelijke opdrachten (Huiswerkopgaven, een schriftelijk tussententamen en een afsluitend schriftelijk tentamen.)
Literatuur Wordt nog bekendgemaakt.
49
Talen en Automaten
34
Talen en Automaten
Positionering van het vak Jaar 2. Omvang 5 EC.
Doelstelling Twee methoden voor het specificeren van formele talen worden apart en in onderlinge verband bestudeerd: (1) via automaten voor het herkennen van talen, (2) via grammatica’s voor het genereren van talen. De volgende soorten automaten komen aan de orde: eindige automaten, stapelautomaten en Turingmachines. Bij de thematiek van eindige automaten hoort ook die van de reguliere expressies. Wat grammatica’s betreft gaat het bij dit vak vooral om de contextvrije grammatica’s en de aanverwante thematiek van parsers en normaalvormen (i.h.b. Chomsky-normaalvormen). Tot de te bestuderen eigenschappen van de klassen van reguliere en contextvrije talen behoren in het bijzonder: geslotenheidseigenschappen (onder bepaalde operaties) en pomplemma’s. Onder verwijzing naar Turingmachines wordt een nadere precisering gegeven van de begrippen beslisbaarheid en berekenbaarheid. Er zal ook aandacht besteed worden aan de thematiek van onbeslisbaarheid.
Voorkennis Logica, discrete structuren
Dwarsverbanden Functioneel Programmeren
Eindtermen De student: • beheerst de basistheorie van eindige automaten, stapelautomaten, Turingmachines, en contextvrije grammatica’s • heeft basisvaardigheid in het werken met reguliere expressies en normaalvormen • heeft elementair begrip van (on)beslisbaarheid, berekenbaarheid, tijdcomplexiteit en de klassen P, NP en NPC.
Onderwijsvormen Hoorcolleges en werkcolleges.
Toetsing Schriftelijk tentamen.
Literatuur De cursus wordt gegeven aan de hand van: "An Introduction to the Theory of Computer Science: Languages and Machines [3d ed]", Thomas A. Sudkamp, Pearson / Addison Wesley, 2006, ISBN 0-321-32221-5. Aanvullende teksten worden aangeboden ter ondersteuning van het zich meer eigen maken van de redeervaardigheden die een belangrijke rol spelen bij dit vak, b.v. homepages.cwi.nl/~jve.
50
Talen en Automaten
Weekschema week 1 2
3
4
5 6
7
onderwerp "Mathematical preliminaries"; basisbegrippen formele talen; reguliere expressies; beginselen contextvrije grammatica’s. Vervolg beginselen van contextvrije grammatica’s: reguliere grammatica’s, bewijstechnieken voor "L = L(G)"met L een gegeven taal en G een gegeven contextvrije grammatica; ambigue grammatica’s. Normaalvormen van contextvrije grammatica’s; efficiënt algoritme voor het probleem "w in L(G)?"Basistheorie eindige automaten, alsmede varianten hiervan; nondeterminisme, epsilon-overgangen; equivalenties van eindige automaten en deze varianten. Uitloop basistheorie van eindige automaten. Eigenschappen reguliere talen: equivalentie eindige automaten en reguliere expressies; equivalentie van eindige automaten en reguliere grammatica’s; geslotenheidseigenschappen van de klasse der reguliere talen. Rest van theorie van reguliere talen: pomplemma en toepassing in bewijzen van nietregulariteit. Theorie van stapelautomaten: basisbeginselen, equivalentie van stapelautomaten en contextvrije grammatica’s. Eigenschappen van de klasse van de contextvrije talen (pomplemma, geslotenheidseigenschappen). Basisbeginselen Turingmachines. TM-berekenbare functies (en onberekenbare functies). (Rest van) Chomsky hiërarchie; equivalentie van TMs en onbeperkte grammatica’s. Beslisbaarheid: problemen, gezien als talen, en recursieve talen; reduceerbaarheid (als hulpmiddel bij aantonen van beslisbaarheid); de these van Church-Turing; de universele TM. Onbeslisbaarheid: (bewijs van onbeslisbaarheid van) Halting probleem; verdere voorbeelden van onbeslisbare problemen (en reduceerbaarheid als hulpmiddel bij aantonen van onbeslisbaarheid). Tijdcomplexiteit en de klassen P, NP, NPC.
51
Vertalerbouw
35
Vertalerbouw
Positionering van het vak Jaar 3. Omvang 5 EC.
Inhoud Een vertaler is een ingewikkeld softwareproduct, daarom loont het om deze op te delen in onderdelen. Eerst wordt input gelezen m.b.v. een scanner, die we construeren middels een standaard techniek. Vervolgens wordt de structuur ontdekt d.m.v. een parser. We behandelen daarbij zowel topdown als bottom-up strategieën. We zullen zien dat we bij deze twee onderdelen gebruik maken van de theoretische resultaten van het vak Talen en Automaten. Daarna kijken we naar een systematische afhandeling van gevonden fouten. Een volgende taak van de compiler is type-controle en genereren van tussencode. Deze tussencode moet afgebeeld worden op de doelmachine (processor). We bekijken speciaal hoe we procedures moeten implementeren, en behandelen verschillende parameter-mechanismen. Heel kort wordt ingegaan op verbetering van code (optimalisatie).
Voorkennis Werkvormen hoorcollege 2+2 uren praktikum (totaal) 40 uur zelfwerkzaamheid (totaal) 120 uur
Literatuur “Compiler Design”, Reinhard Wilhelm, Dieter Maurer, Addison-Wesley, 1995.
Toetsing Schriftelijk + practicum
Collegeschema 1. Inleiding, structuur vertaler (8 fasen); strings, grammatica’s, talen 2. reguliere expressies, (aangepaste) eindige automaten; nullable, first, follow; systematische generatie van de scanner 3. foutafhandeling in de scanner; gereduceerde grammatica’s, getransformeerde grammatica’s; afleidingen, topdown, bottomup, ambigue CFG’s; aangepaste stapelautomaat; predictive PDA; 4. nullable, first, follow, lookahead sets, LL(1); table driven topdown parser, expliciete stack parser, recursive descent 5. foutafhandeling in de parser; bottom-up parsing, sets of items, parsing action table, LR(0), SLR(1), LR(1), LALR(1) 6. attributen-grammatica’s, synthesized/inherited attributes; foutafhandeling in de semantische fase; implementatie van blocks en procedures, activation records, naming, scope rules, display, static chain; 7. systematische generatie code voor proc_entry, proc_exit, proc_call, parameter overdracht, formele procedure parameters; codegeneratie voor array-indicering
52
Wiskundig Modelleren 1 (Wiskunde A)
36
Wiskundig Modelleren 1 (Wiskunde A)
Positionering van het vak Periode 1.2, omvang 5 EC. Voorkennis: VWO Wiskunde
Doelstelling De algemene doelstelling van het vak Wiskundig Modelleren 1&2 is ervaring opdoen met het wiskundig modelleren, analyseren, implementeren en interpreteren van een (informeel beschreven) proces uit natuur- of levenswetenschap, economie, enz.; het vergroten van de hierbij benodigde wiskundige kennis; het verkrijgen van vaardigheid in het gebruiken van deze kennis voor het analyseren van wiskundige modellen; en het verkrijgen van vaardigheid in het hanteren van bijbehorende softwaretools. Belangrijke elementen hierbij zijn het plaatsen van de benodigde wiskunde in een duidelijke probleemcontext en een combinatie van werkvormen zoals traditionele hoorcolleges en projecten. Er wordt veel zelfwerkzaamheid van de student verwacht. Eén van de belangrijkste doelen van de in Wiskundig Modelleren 1 aangeboden wiskunde is om de VWOervaring met functies van één variabele op te rekken naar (vector)functies van meerdere variabelen. Voor de analyse van deze functies speelt de lineaire algebra een belangrijke rol, waaruit een aantal onderwerpen wordt behandeld. Verder worden de reële getallen uitgebreid naar de complexe getallen en zullen enkele eenvoudige functies hierop geïntroduceerd worden, o.a. de complexe e-macht.
Eindtermen • Vaardigheid in het doordringen tot de kern van een informeel gespecificeerd (fysich, economisch, biologisch) proces • Vaardigheid in het kiezen van een geschikt wiskundig formalisme en/of model voor het betreffende proces • Vaardigheid in opsporen en verwerken van relevante literatuur op het gebied van het betreffende proces • Kennis opdoen van de analyse van (vector)functies van meerdere variabelen, het rekenen met complexe getallen en elementaire lineaire algebra • Vaardigheid in de toepassing van de behandelde wiskundestof bij het analyseren van een eenvoudig wiskundig model • Vaardigheid in het vertalen van een eenvoudig wiskundig model naar een computerimplementatie of simulatie • Vaardigheid in gebruiken van tools zoals Matlab en Mathematica bij de implementatie en analyse van het betreffende probleem • Vaardigheid in het interpreteren en analyseren van de resultaten in termen van het oorspronkelijke proces • Vaardigheid in het samenwerken met medestudenten in projecten • Vaardigheid in het schriftelijk en mondeling presenteren van de resultaten van projecten
Onderwijsvormen Een mengvorm van hoorcollege, werkcollege, en project.
Onderwerpen De onderwerpen bij het ‘klein project’ worden zo gekozen dat de benodigde wiskundekennis op VWOniveau ligt. Bij het ‘groot project’ zijn de onderwerpen iets geavanceerder, waarbij de benodigde wiskunde tijdens de cursus wordt opgebouwd. De lijst van projectonderwerpen kan jaarlijks variëren. Mogelijke onderwerpen: mechanische systemen (slinger, snaar), populatiedynamica (roofdier-prooi systemen, ecosysteem-modellen), elektrische circuits, chemische reacties, speltheorie. Onderwerpen uit de wiskunde die aan bod komen: • Uit boek, secties:
53
Wiskundig Modelleren 1 (Wiskunde A)
– vectoren, vectorfuncties en krommen: 8.1-8.3 (niet "scalar triple product"), 8.4-8.6 – complexe getallen: 12.1, 12.2, 12.6 (niet ëntire function") – lineaire algebra: 6.1-6.7, 7.1, 7.2, 7.5 – functies van meerdere variabelen: 8.8, 8.9, 9.3 • Uit dictaat, secties: – limieten, differentiëren, integreren: 1.1-1.7 – Taylorontwikkeling: 1.9 – functies van meerdere variabelen, extrema, lineaire benaderingen: 5
Weekschema week 1-2
week 3-8
week 9-10
inleidend college (doelstelling, voorbeelden, richtlijnen). projectgroepen maken (tweetallen). Klein project modelleren–programmeren–analyseren. Oplossingen in mathematica/matlab uitwerken twee werkcolleges waarin VWO-wiskunde (differentiëren) wordt opgehaald. Groot project modelleren–programmeren–analyseren. Parallel hieraan de wiskundestof, omvang lineair aflopend naar eind van projectperiode. Tussenrapportages. Toetsperiode. Wiskunde via individueel tentamen; project via eindverslag en mondelinge presentatie (per tweetal).
Toetsing Het eindcijfer is het gemiddelde van het cijfer voor de projecten en het cijfer voor het schriftelijk tentamen.
Literatuur De cursus wordt gegeven aan de hand van: 1. E. Kreyszig: Advanced Engineering Mathematics (8th ed.), New York: John Wiley and Sons Ltd (1999) 2. R. Verstappen: Wiskunde 1 (dictaat). 3. Studiewijzer met informatie over de werkwijze bij de projecten, onderwerpen, literatuur, enz.
54
Wiskundig Modelleren 2 (Wiskunde B)
37
Wiskundig Modelleren 2 (Wiskunde B)
Positionering van het vak Periode 1.4, omvang 5 EC. Voorkennis: Wiskundig Modelleren 1
Doelstelling De algemene doelstelling van het vak Wiskundig Modelleren 1&2 is ervaring opdoen met het wiskundig modelleren, analyseren, implementeren en interpreteren van een (informeel beschreven) proces uit natuur- of levenswetenschap, economie, enz.; het vergroten van de hierbij benodigde wiskundige kennis; het verkrijgen van vaardigheid in het gebruiken van deze kennis voor het analyseren van wiskundige modellen; en het verkrijgen van vaardigheid in het hanteren van bijbehorende softwaretools. Belangrijke elementen hierbij zijn het plaatsen van de benodigde wiskunde in een duidelijke probleemcontext en een combinatie van werkvormen zoals traditionele hoorcolleges en projecten. Er wordt veel zelfwerkzaamheid van de student verwacht. De in Wiskundig Modelleren 2 aangeboden wiskunde gaat over differentiaalvergelijkingen, reeksen, vectoranalyse, partiele differentiaalvergelijken en iteratieve methoden. Bij de differentiaalvergelijkingen komen aan de orde: richtingsveld, scheiden van variabelen, exacte differentiaal, lineaire differentiaalvergelijkingen, superpositie, beginwaardeprobleem, randwaardeprobleem, tweede-orde differentiaalvergelijkingen met constante coëfficiënten, harmonische oscillator, stelsels differentiaalvergelijkingen, fasevlak, kritieke punten. Bij reeksen staan de begrippen convergentie/divergentie, machtreeks en Fourierreeks centraal. Bij de vectoranalyse draait het om begrippen als gradiënt, potentiaal, niveau-oppervlak, parametriseren van oppervlakken. Daarnaast worden lijnintegralen behandeld, hierbij komen de begrippen arbeid, potentiaal, afhankelijkheid van integratie-weg, exacte differentiaalaan de orde. Tenslotte volgt een inleiding tot iteratieve methoden voor het oplossen van vergelijkingen (o.a. de Newton-methode) en differentiaalvergelijkingen (Picard-iteratie).
Eindtermen • Vaardigheid in het doordringen tot de kern van een informeel gespecificeerd eenvoudig (fysich, economisch, biologisch) proces • Vaardigheid in het kiezen van een geschikt wiskundig formalisme en/of model voor het betreffende proces • Vaardigheid in opsporen en verwerken van relevante literatuur op het gebied van het betreffende proces • Kennis opdoen van de analyse van differentiaalvergelijkingen, reeksen, vectoranalyse, partiele differentiaalvergelijken en iteratieve methoden • Vaardigheid in de toepassing van de behandelde wiskundestof bij het analyseren van een wiskundig model • Vaardigheid in het vertalen van een wiskundig model naar een computerimplementatie of simulatie • Vaardigheid in gebruiken van tools zoals Matlab en Mathematica bij de implementatie en analyse van het betreffende probleem • Vaardigheid in het interpreteren en analyseren van de resultaten in termen van het oorspronkelijke proces • Vaardigheid in het samenwerken met medestudenten in projecten • Vaardigheid in het schriftelijk en mondeling presenteren van de resultaten van projecten
Onderwijsvormen Een mengvorm van hoorcollege, werkcollege, en project. Zelfwerkzaamheid totaal xx uur.
Onderwerpen De onderwerpen bij het project worden zo gekozen dat ze aansluiten bij de wiskundekennis op het niveau van Wiskundig Modelleren 1 en de nieuwe wiskunde die tijdens deze cursus wordt opgebouwd. De lijst van projectonderwerpen kan jaarlijks variëren. Mogelijke onderwerpen: mechanische
55
Wiskundig Modelleren 2 (Wiskunde B)
systemen (meerdere deeltjes, gekoppelde oscillatoren), populatiedynamica (roofdier-prooi systemen, ecosysteem-modellen), economische modellen, diffusieprocessen, warmtegeleiding, stromingen, speltheorie. De wiskundestof betreft de volgende onderwerpen uit het cursusboek: • gewone differentiaalvergelijkingen: 1.1-1.6, 2.1-2.3, 2.5, 2.7 • 2de-orde differentiaalvergelijkingen: 2.8, 2.9, 2.11, 2.12 • stelsels differentiaalvergelijkingen: 3.0 t/m 3.4 • reeksen: 14.1, 4.1, 4.2, 10.1 t/m 10.4 • vector-analyse: 8.4, 8.9, 8.10, 9.1, 9.2 • iteratieve methoden: 17.1, 17.2, 18.3, 1.9
Weekschema week 1
week 2-8
week 9-10
inleidend college (doelstelling, voorbeelden, richtlijnen). projectgroepen maken (tweetallen). 1e hoorcollege wiskunde. Project modelleren–programmeren–analyseren. Parallel hieraan de wiskundestof, omvang lineair aflopend naar eind van projectperiode. Tussenrapportages. Toetsperiode. Wiskunde via individueel tentamen; project via eindverslag en mondelinge presentatie (per tweetal).
Toetsing Het eindcijfer is het gemiddelde van het cijfer voor het projecten en het cijfer van het schriftelijk tentamen.
Literatuur De cursus wordt gegeven aan de hand van: 1. E. Kreyszig: Advanced Engineering Mathematics (8th ed.), New York: John Wiley and Sons Ltd (1999) 2. Studiewijzer met informatie over de werkwijze bij het project, onderwerpen, literatuur, enz.
56