DM10x - 3. semester

Ugeplan for Softwarearkitektur og Distribuerede Programmer

Tema: Træer og Grafer (datastrukturer og algoritmer) samt sprogteori
- Gå til uge: 38, 39, 40, 41, 43, 44

Sidst ændret: 2011.12.25

 

Uge 38
Dag Tidspunkt Emne Litteratur / Opgaver
Tirsdag  08:30 -

 

 Præsentation og feedback på projektarbejde

 

  
  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
- 14:00 Opgaver med binære træer (løs opgave BT01,BT02,BT03 og BT04 til torsdag)

 
Torsdag  08:30 -  

 

 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)

 
Fredag  08:30 -  10:00

 

 Opsamling på Obligatorisk køreplansopgave - delopgave 1)

Graf - implementering / datastrukturer

Graf algoritmer
- bredde- og dybde-traversering
 

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

 
Afleveringsopgaver (obligatoriske) denne uge: opgave BT05 - (BT01-04 skal laves til torsdag, men ikke afleveres) - Køreplansopgave delopgave 1 laves til fredag, men afleveres ikke
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 (behøver ikke at kunne udskrive i formatet som beskrevet i projekt-oplæg)
  -  2a) grafklassen skal kunne indeholde en graf.
  -  2b) metode for brede-først traversering.
  -  2c) metode for minimum spanning tree
  -  2d) du er velkommen til at udvide med ekstra metoder for fx shortest path (Dijkstra)
 


 

Uge 39
Dag Tidspunkt Emne Litteratur / Opgaver
Tirsdag  08:30 -

 

 Opsamling på Obligatorisk køreplansopgave - delopgave 1)

Graf algoritmer
- bredde- og dybde-traversering (opsamling)
- 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
Prims algoritme: javakode og applet for simulering af algoritme
  Opsamling på binære søgetræer - indsættelse og sletning
- 14:00 Arbejde med graf-projekt - se under afleveringsopgaver

 
Torsdag  08:30 -  

 

 Graf algoritmer
- evt. repetition af bredde- og dybde-traverserin, samt Prims
- minimum spanning tree - Kruskals

evt. Dijkstras shortest path

Kruskals algoritme på graf - minimum spanning tree
Kruskals algoritme: javakode og applet for simulering af 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    
 
- 14:00
Fredag  08:30 -  10:00

 

 Graf algoritmer
- Dijkstras shortest path
 

 

 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  
Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 2b - 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 (behøver ikke at kunne udskrive i formatet som beskrevet i projekt-oplæg)
  -  2a) grafklassen skal kunne indeholde en graf.
  -  2b) metode for brede-først traversering.
  -  2c) metode for minimum spanning tree
  -  2d) du er velkommen til at udvide med ekstra metoder for fx shortest path (Dijkstra)
 


 

 

Uge 40
Dag Tidspunkt Emne Litteratur / Opgaver
Tirsdag  08:30 -

 

 Opsamling på grafer og algoritmer på disse

Fra domain-model med data til graf

  
 
- 14:00
Torsdag  08:30 -  

 

 Fra domain-model med data til graf

 

  
  Introduktion til sprogteori
- 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(kbh. uni)) De første 2 vil være primære for denne dag - den sidste inddrages undervejs i forløbet.

Slides om Sprog og compiler

Compilering_af_symbolsk_maskinsprog med brug af  Symboltabel
Bjarnes modelmaskine til VirtualBox med dokomentation og 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/)
Ebnf-Visualizer_bjbu.exe.zip - udgave kører under windows7

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

- 14:00 Opgave med EBNF - EBNFOpgave01
Fredag  08:30 -  10:00

 

 Torsdagens emner fortsat 
 

Opgave med EBNF - EBNFOpgave01

 se torsdag
Afleveringsopgaver (obligatoriske) denne uge: 
  -  Ruteplansopgave - frem til og med delopgave 2c skal afsluttes inden torsdag
  -  Ruteplansopgave - frem til og med 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 (behøver ikke at kunne udskrive i formatet som beskrevet i projekt-oplæg)
  -  2a) grafklassen skal kunne indeholde en graf.
  -  2b) metode for brede-først traversering.
  -  2c) metode for minimum spanning tree
  -  2d) du er velkommen til at udvide med ekstra metoder for fx shortest path (Dijkstra)
delopgave 3) Der skal laves en datastruktur/domaine-model, 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(domain-modellen) kan danne grafen. 
 


 

Uge 41
Dag Tidspunkt Emne Litteratur / Opgaver
Tirsdag  08:30 -

 

 Sproglære fortsat

Scanner / Leksikalsk analyse - vi skal "bygge" første del af inputbehandlingen

  • beskrivelse  med regulære udtryk
  • design med DFA (tilstandsdiagram med overgang og effekt)
  • kode med brug af state-pattern

Note om EBNF grammatik og syntakstyret indlæsning (se tidligere udleverede kopier)

Scanner / Leksikalsk analyse:
- eksempel på simpel scanner / leksikalsk analyse
- eksempel på scanner / leksikalsk analyse baseret på statepattern
 
 
- 14:00 Delopgave 5) og 6) færdiggøres til torsdag morgen Se Token klassen i TokenLibrary (se ovenfor)
 
Torsdag  08:30 -  

 

 Scanner / Leksikalsk analyse  fortsat
  • state pattern
  • brug af Lex/Flex værktæj (C# udgave tilpasset brug med Visual Studio)
Om state pattern: http://en.wikipedia.org/wiki/State_pattern


Medlemsliste LexAnalyser med Lex værktøj:  CsLexSolutionMedlemsliste_v1.zip
- i forhold til programmeringsopgave skal værktøjsløsning ikke anvendes i primære løsning, men vise hvordan man kan bruge regulære udtryk næsten direkte til at lave en Leksikalsk analyse
 
- 14:00
Fredag  08:30 -  10:00

 

 Introduktion til parseren

 

 

 

 

- for de der er færdige med scanneren er her gennemgået en regelstyret parser 

Bottom-up parsing:
- http://en.wikipedia.org/wiki/Bottom-up_parsing
Recursive descent parser (top-down):
- http://en.wikipedia.org/wiki/Recursive_descent_parser
Parse tree (resultat fra parser):
- http://en.wikipedia.org/wiki/Parse_tree
Eliminering af vestre-recursion i grammatikken (se tidligere udleverede kopier)
- (man skal kun kende til problematikken ikke kunne omskrive)
Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 7a

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 5) Med udgangspunkt i grammatikken for Ruteplansinputtet skal du fastsætte passende brikker/tokens og herefter omskrive grammatikken med disse som terminaler, du skal endvidere beskrive hvert af disse tokens som regulære udtryk.

delopgave 6) Der skal laves en Token klasse, der kan bruges til scanner (leksikalske analysator) og parser. Du kan evt. også også lave en klasse til udveksle Tokens som i løsningen med medlemssystemet.
du kan tage udgangspunkt i ét af følgende eksempler:
- eksempel på simpel scanner / leksikalsk analyse
- eksempel på scanner / leksikalsk analyse baseret på statepattern

delopgave 7a) Der skal laves en Scanner / Leksikalsk analysator, der kan lave Tokens ud fra en tekstfil og aflevere disse i en passende datastruktur Parseren senere kan bruge som input. Du skal teste med en udskrift af de tokens du finder. Du skal lave passende fejludskrift, hvis der er fejl i den leksikalske analyse (input ikke passer til tokens), hvis du prøve om du kan scanne videre og "komme på sporet igen".
Du kan tage udgangspunkt i ét af følgende eksempler:
- eksempel på simpel scanner / leksikalsk analyse
- eksempel på scanner / leksikalsk analyse baseret på statepattern

delopgave 7b) Der skal laves en Scanner / Leksikalsk analysator med brug af Lex/Flex værktøjet - du tilretter medlemsliste syntaksen til ruteplanssyntaksen  
Du kan tage udgangspunkt i en af følgende eksempler
- Medlemsliste LexAnalyser med Lex værktøj:  CsLexSolutionMedlemsliste_v1.zip
 

Her er total eksempel - indeholder flere løsninger på såvel scanner som parser samt en kobling mellem disse - indeholder flere solution-filer, der kombinerer projekter
- EBNF_Syntaksstyret_Medlemsliste_bjbu


 

 

Uge 43
Dag Tidspunkt Emne Litteratur / Opgaver
Tirsdag  08:30 -

 

 I skal arbejde selv med parser, der her er gennemgået

Sprogteori / parser

 Parser: EBNF_Syntaksstyret_Medlemsliste_bjbu (vælg Parser solution - 2 forskellige løsninger på Parser)

Parser:
- eksempel på recursive decent parser
- eksempel på parser baseret på startepattern

Evt. supplement hvis nogen føler særlig trang. Løsning med tabel-styret parser tættere på beskrivelser i KBH note)
- EBNF_Syntaksstyret_Medlemsliste_nokn_bjbu
 
- 14:00
Torsdag  08:30 -  

 

 Sprogteori / parser Lekikalsk analyse og parsing med brug af værktøj (LALR(1) - Flex+Bisson)

Video om brug af Lex/Flex værktæj (C# udgave tilpasset brug med Visual Studio)   
  Sprogteori / parser Medlemsliste med brug af "Flex" - "Bisson" lignende værktøj til C# for Leksikalsk analyse og parsing - Se hvor nemt det bliver når man "bare" kan beskrive grammatikken med regulære udtryk til leksikalske analysator og BNF til parseren
- 14:00
Fredag  08:30 -  10:00

 

 Afrunding på sprogteori og ruteplansopgave  
Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 8b

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 8a) Der skal nu laves en Parser, der som input kan tage en samling "færdige" tokens og opbygge en regionskøreplan svarende til tidligere definerede struktur (EBNF_Ruteplan_Datamodel_for_Regionskoereplan.ppt)
Du kan tage udgangspunkt i ét af følgende eksempler:
- eksempel på recursive decent parser
- eksempel på parser baseret på startepattern

delopgave 8b) Der skal laves en Parser analysator med brug af Lex/Flex værktøjet - du tilretter medlemsliste syntaksen til ruteplanssyntaksen
Du kan tage udgangspunkt i følgende eksempel
- Lekikalsk analyse og parsing med brug af værktøj (LALR(1) - Flex+Bisson)  eller hvis du vil prøve den mere avancerede hvor der opbygges model direkte i forbindelse med parsingen  CsLexParserSolutionMedlemsliste_Model.zip

delopgave 9) Delene du tidligere har programmeret skal nu sammenkobles, så der kommer en samlet løsning på ruteplansopgaven - scanner+parser til ruteplan-model og fra ruteplan-model til graf med løsning af graf-opgaver.
 
 

Her er total eksempel - indeholder flere løsninger på såvel scanner som parser samt en kobling mellem disse - indeholder flere solution-filer, der kombinerer projekter
- EBNF_Syntaksstyret_Medlemsliste_bjbu


 

 

Uge 44

Projektarbejde og individuelle studiesamtaler

SDP projekt-element:  Færdiggørelse og aflevering af SDP-afleverings-opgaver