DM091 - 3. semester

Ugeplan for Softwarearkitektur og Distribuerede Programmer

Tema: 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
C# eksempel på dele af binært træ
Induktionsbeviser

Supplerende materiale:
- Binær søgetræ: http://en.wikipedia.org/wiki/Binary_search_tree
- Begreber i forbindelse med binærer træer
- IComparable og IComparer interfaces:- Eksempel med brug af IComperable og Collections.Comparer til sortering af varer i list på forskellige kriterier (varenr, betegnelse og pris)
- Binære søgetræer i med visitor pattern i CSharp

  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

Gennemgang af datastrukturen graf ift. implementering

- 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.
Opgaven foreslås som projektarbejde

delopgave 1) Med udgangspunkt i oplæggets bilag med ruteplan skal du finde frem til hvilke knuder og kanter og tegne en graf, der svarer til ruteplanen. Når du får lavet et grafprogram, kan du bruge ruteplan-grafen som testdata.

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
- bredde- og dybde-traversering
- minimum spanning tree - Prims algoritme

Note om grafer af Niels Otto Knudsen
Gennemgang af datastrukturen graf ift. implementering


Prims algoritme på graf - minimum spanning tree  - YouTube-video
Prims algoritme: javakode og applet for simulering af algoritme

     
- 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
Kruskals algoritme: javakode og applet for simulering af algoritme

 
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

Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf, herunder opsamling på dybde og bredde gennemløb samt Prims minimum spanning tree - gennemgået at Bjørk Boye Busch 2010-11-18 - YouTube-video

     
- 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.
delopgave 1) Med udgangspunkt i oplæggets bilag med ruteplan skal du finde frem til hvilke knuder og kanter og tegne en graf, der svarer til ruteplanen.
delopgave 2) Du skal have lavet en grafklasse og et program, der med brug af denne kan løse grafspørgsmålene med brug af ruteplan-grafen som testdata.
delopgave 3) Der skal laves en datastruktur, der kan indeholde informationen fra den beskrevne ruteplan (oplæg/idé gennemgås næste uge)
delopgave 4) Der skal laves en rutine, der ud fra data i ruteplan-modellen kan danne grafen.

 

 

 

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.

Slides om Sprog og compiler

Compilering_af_symbolsk_maskinsprog med brug af  Symboltabel
Bjarnes modelmaskine - virual floppy for Virtual PC 2007
Selve modelmaskine til dos-box med dokomentation  - tilhørende eksempler

Om Context frie grammatikker (wikipedia) - se specielt på eksemplerne:
- http://en.wikipedia.org/wiki/Context-free_grammar

EBNF eksempler
Download EBNF Visualizer (fra http://dotnet.jku.at/applications/Visualizer/)

Leksikalsk analyse ( scanner til tokens ):
- http://en.wikipedia.org/wiki/Lexical_analysis

Om programmeringssprog, parsertree og tokenization (wikipedia):
- http://en.wikipedia.org/wiki/Parsing#Programming_languages
- vigtigste er: http://en.wikipedia.org/wiki/File:Python_add5_parse.png

Om state pattern:
- http://en.wikipedia.org/wiki/File:State_Design_Pattern_UML_Class_Diagram.png

For dem der gerne vil lidt dybere i emnet

Om hvad er en compiler er og forskellige typer (wikipedia):
- http://en.wikipedia.org/wiki/Compiler

  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.
delopgave 1) Med udgangspunkt i oplæggets bilag med ruteplan skal du finde frem til hvilke knuder og kanter og tegne en graf, der svarer til ruteplanen.
delopgave 2) Du skal have lavet en grafklasse og et program, der med brug af denne kan løse grafspørgsmålene med brug af ruteplan-grafen som testdata.
delopgave 3) Der skal laves en datastruktur, der kan indeholde informationen fra den beskrevne ruteplan (oplæg/idé gennemgås denne uge)
delopgave 4) Der skal laves en rutine, der ud fra data i ruteplan-modellen kan danne grafen.