DM11x - 3. semesterUgeplan for Softwarearkitektur og Distribuerede ProgrammerTema: Træer og Grafer (datastrukturer og algoritmer) samt sprogteori |
Sidst ændret: 2012.10.20
Uge 39 | |||
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 Supplerende materiale: |
||
- 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 |
||
- 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)
|
||
Fredag | 08:30 - 10:00
|
Opsamling på Obligatorisk
køreplansopgave - delopgave 1) Graf - implementering / datastrukturer Graf algoritmer |
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 40 | |||
Dag | Tidspunkt | Emne | Litteratur / Opgaver |
Tirsdag | 08:30 -
|
Opsamling på Obligatorisk
køreplansopgave - delopgave 1) Graf algoritmer |
Note om grafer af Niels Otto Knudsen Gennemgang af datastrukturen graf ift. implementering
Prims algoritme på graf - minimum spanning tree |
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
|
- 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 |
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 41 | |||
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 -
|
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.
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): For dem der gerne vil lidt dybere i emnet |
- 14:00 | Opgaver med EBNF (løs opgave 1-5) | ||
Fredag | 08:30 - 10:00
|
Torsdagens emner fortsat Opgaver med EBNF (løs opgave 1-5) |
se torsdag |
Afleveringsopgaver
(obligatoriske) denne uge: - Ruteplansopgave - frem til og med delopgave 2c skal afsluttes inden torsdag - Ruteplansopgave - frem til og med delopgave 4 (hvis du er bagud så drop denne frem for andre opgaver) |
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 43 | |||
Dag | Tidspunkt | Emne | Litteratur / Opgaver |
Tirsdag | 08:30 -
|
Sproglære fortsat Scanner / Leksikalsk analyse - vi skal "bygge" første del af inputbehandlingen
|
Note om EBNF grammatik og syntakstyret indlæsning (se tidligere udleverede kopier)
Scanner / Leksikalsk analyse: |
- 13:30 | Delopgave 5) og 6) færdiggøres til onsdag |
Se Token klassen i
TokenLibrary (se ovenfor) |
|
Onsdag | 12:30 - |
Scanner / Leksikalsk analyse
fortsat fra tirsdag (Bemærk
der er SDP Onsdag over middag - SKEMAÆNDRING) Det vil denne dag være opgaveløsning - med støtte fra underviser |
|
- 14:00 - 15:00 |
Opgave 7a og efterfølgende 7b
Vi
vil desuden samle op på opgaver fra tidligere (kode/gennemgå
løsninger..... primært fokus denne dag er grafopgaverne) |
Se evt. mit bud på graf med algoritmer Graf_Matrix.zip |
|
Torsdag | 08:30 -
|
Scanner / Leksikalsk analyse
fortsat
Bemærk der er kun lærerstøtte på til ca 10:30, så vi kommer muligvis til at skulle skubbe lidt teori til fredag. |
Om state pattern:
http://en.wikipedia.org/wiki/State_pattern
Scanner / Leksikalsk analyse: |
- 14:00 | Opgave 7a og efterfølgende 7b | ||
Fredag | 08:30 - 10:00
|
Evt. resten fra torsdag. Introduktion til parseren
- for de der er færdige med scanneren er her gennemgået en regelstyret parser |
Bottom-up parsing: |
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. |
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 |
Uge 44 | |||
Dag | Tidspunkt | Emne | Litteratur / Opgaver |
Tirsdag | 08:30 -
|
I skal arbejde selv med parser, der
her er gennemgået - der er ingen lærerstøtte denne tirsdag Sprogteori / parser |
Evt. supplement hvis nogen føler særlig trang. Løsning
med tabel-styret parser tættere på beskrivelser i KBH note) |
- 14:00 |
Opgave 8a |
||
Onsdag | 12:30 - - 14:00 |
Opsamling på parser - opgaveløsning
(Bemærk der er SDP Onsdag over
middag - SKEMAÆNDRING) Det vil denne dag være opgaveløsning - med støtte fra underviser |
|
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 |
Opgave 8b |
||
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 8b) Der skal laves en Parser analysator med brug af
Lex/Flex værktøjet - du tilretter medlemsliste syntaksen til
ruteplanssyntaksen 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 |