DM091 - 3. semesterUgeplan for Softwarearkitektur og Distribuerede ProgrammerTema: Træer og Grafer (datastrukturer og algoritmer) - Gå til uge: 45, 46, 47, |
Sidst ændret: 2010.11.24
Uge 45 | |||
Dag | Tidspunkt | Emne | Litteratur / Opgaver |
Mandag | 08:30 - 11:50 | Projektarbejde (projekt 2) - grupperne præsenterer i løbet af dagen løsningen for Bjørk | |
- 14:00 | Projektarbejde (projekt 2) - grupperne præsenterer i løbet af dagen løsningen for Bjørk | ||
Tirsdag | 08:30 - 10:00 | Vi tager fat på nyt tema med
datastrukturer og algoritmer, hvor hoved temaet vil være træer og grafer Tirsdagen vil i stor udstrækning foregå som traditionel tavle-undervisning, der skal illustrere de forskellige datastrukturers opbygning og skitsere algoritmer på disse Fokus i emnet vil blive på træer og grafer |
Wikipedia: om datastrukturer::
http://en.wikipedia.org/wiki/List_of_data_structures Microsoft: om træer: http://msdn.microsoft.com/en-us/library/ms379572.aspx
Noter til binære træer Supplerende materiale: |
Opgaver med binære træer (løs opgave BT01,BT02,BT03 og BT04 til torsdag) | |||
Torsdag | 08:30 - 11:50 | Træer fortsat Generiske datastrukturer og interfaces Visitor pattern |
Materiale se mandag Generiske datastrukturer (template baserede) - her en dårlig stak 173_StackTemplate |
Introduktion til grafer |
http://msdn.microsoft.com/en-us/library/ms379574.aspx Note om grafer af Niels Otto Knudsen |
||
- 14:00 | Opgaver: Opgaver med binære træer (løs opgave BT05)
Oplæg til bredere obligatorisk opgave i sproglære og grafer
- opgaven vil blive opdelt i delopgaver over de næste uger,
så der til sidst gerne skulle kunne ses en samlet løsning. GrafOpgaver - programmering - (ekstra opgaver- ruteopgave er primære) |
Afleveringsopgaver
(obligatoriske) denne uge: Opgave BT05 - (BT01-04 skal laves til torsdag, men ikke afleveres) - Obligatorisk køreplansopgave - delopgave 1) færdig til mandag aflevering? |
(*) Core C# and .NET,
Stephen C. Perry - se Fronter (**) .Net Application Development with C#..., Hanspeter Mössenböck - se Fronter (***) C# To the point -.., Hanspeter Mössenböck - - se Fronter |
Uge 46 | |||
Dag | Tidspunkt | Emne | Litteratur / Opgaver |
Mandag | 08:30 - 11:50 | Opdamling på Obligatorisk
køreplansopgave - delopgave 1) Graf algoritmer |
Note om grafer af Niels Otto Knudsen Gennemgang af datastrukturen graf ift. implementering
|
- 14:00 | Arbejde med graf-projekt - se under afleveringsopgaver | ||
Tirsdag | 08:30 - 10:00 | Graf algoritmer - evt. repetition af bredde- og dybde-traverserin, samt Prims - minimum spanning tree - Kruskals |
Kruskals algoritme på graf - minimum spanning tree
|
Torsdag | 08:30 - 11:50 | Graf algoritmer - dybdetraversering (kode uden recursion men med brug af stak) - shortest path (incl. opsamling på øvrige) |
Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf Simulerings af Dijkstra's algoritme |
- 14:00 | Lærerstøttet arbejde med graf-projekt - se under afleveringsopgaver |
Afleveringsopgaver
(obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 2 -
Bredde først traversering
Oplæg til bredere obligatorisk opgave i sproglære og grafer
- opgaven vil blive opdelt i delopgaver over de næste uger,
så der til sidst gerne skulle kunne ses en samlet løsning.
|
Uge 47 | |||
Dag | Tidspunkt | Emne | Litteratur / Opgaver |
Mandag | 08:30 - 11:50 | Grafer fortsat Oplæg til datastruktur / objektmodel for ruteplanen i den stillede opgave. - modellen skal kunne indeholde informationer fra ruteplanen, men i denne del sættes den konkrete plan direkte ind i strukturen uden indlæsning og tolkning fra tekstfilen. |
|
- 14:00 | Opgaveløsning uden lærerstøtte | ||
Tirsdag | 08:30 - 10:00 | Grafer fortsat | |
Torsdag | 08:30 - 11:50 | Introduktion til sproglære - Grammatikker og sprog - Compiler - regulære udtryk - BNF + EBNF
|
Noter/litteratur se tidligere
udleverede kopier (Hvordan virker en Compiler, Compiler design
og Note om EBNF grammatik) De første 2 vil være primære for
mandagen - den sidste inddrages undervejs i forløbet.
Compilering_af_symbolsk_maskinsprog med brug af
Symboltabel Om Context frie grammatikker (wikipedia) - se specielt på
eksemplerne:
EBNF eksempler Leksikalsk analyse ( scanner til tokens ): Om programmeringssprog, parsertree og tokenization
(wikipedia): Om state pattern: For dem der gerne vil lidt dybere i emnet Om hvad er en compiler er og forskellige typer (wikipedia): |
Opgave med EBNF - EBNFOpgave01 | |||
- 14:00 | Fortsættelse af formiddagens emner / opgave |
Afleveringsopgaver
(obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 4
Oplæg til bredere obligatorisk opgave i sproglære og grafer
- opgaven vil blive opdelt i delopgaver over de næste uger,
så der til sidst gerne skulle kunne ses en samlet løsning. |