|
| Udgave: |
Forår 2013 NAT |
| Point: |
7,5 |
| Blokstruktur: |
4. blok |
| Skemagruppe: |
B |
| Fagområde: |
dat |
| Varighed: |
9 uger |
| Institutter: |
Datalogisk Institut |
| Uddannelsesdel: |
Bachelor niveau |
| Kontaktpersoner: |
Pawel Winter, e-mail: pawel@diku.dk , tlf.: 3532 1427 |
| Andre undervisere: |
Christian Wulff-Nilsen |
| Skema- oplysninger: |
 Vis skema for kurset
Samlet oversigt over tid og sted for alle kurser inden for Lektionsplan for Det Naturvidenskabelige Fakultet Forår 2013 NAT |
| Undervisnings- form: |
Forelæsninger: 2*2, Øvelser: 2*2 |
| Formål: |
Kursets formål er at præsentere en række algoritmiske paradigmer (herunder del-og-hersk, det grådige princip og dynamisk programmering), samt at introducere en række analyseværktøjer (korrekthed, køretid, pladsbehov).
Fokus er på polynomielle problemer. |
| Indhold: |
Del og hersk, dynamisk programmering, grådige algoritmer, sortering, grafalgoritmer, algoritmisk geometri.
|
| Målbeskrivelse: |
Ved kursets afslutning skal den studerende kunne:
1. Beskrive udvalgte paradigmer og kunne identificere disse på passende problemstillinger.
2. Foretage asymptotisk kompleksitetsanalyse af simple algoritmer.
3. Beskrive alment anvendte datastrukturer, asymptotisk køretid for de tilhørende operationer samt anvende datastrukturer på passende problemstillinger.
4. Beskrive udvalgte sorterings- og grafalgoritmer, samt deres kompleksitetsanalyse og korrekthed.
5. Gennemføre korrekthedsbeviser for udvalgte algoritmer som primært baserer sig på induktion (herunder formulering af løkkeinvarianter) samt direkte og modstridsbeviser.
6. Demonstrere ovenstående kompetencer i skrift og tale.
|
| Lærebøger: |
Forventes at være:[CLRS] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd. Edition, The MIT Press (2009)
|
| Tilmelding: |
15. november - 1. december, 2012, via KUnet, www.kunet.dk |
| Faglige forudsætninger: |
Diskrete matematiske strukturer eller Mat. Intro og Linær Algebra. De studerende forventes bl.a. at have kendskab til grafer, induktionsbeviser og "Store-O" notation. Studerende med manglende forudsætninger bør kontakte den kursusansvarlige. |
| Eksamensform: |
Kurset afsluttes med en mundtlig, karaktergivende eksamen, 30 min. med forberedelse. Ekstern censur. En forudsætning for at gå op til eksamen er en godkendelse af 75% af de skriftlige ugentlige opgaver. De skriftlige ugentlige opgaver kan danne grundlag for spørgsmål ved den mundtlige eksamen.
Reeksamen: Samme som ordinær eksamen.
|
| Eksamen: |
Mundtlig prøve d. 17-21. juni 2013.
Reeksamen: Mundtlig prøve d. 19-21. og 23. august 2013. |
| Kursus hjemmeside: |
 |
| Undervisnings- sprog: |
Dansk og et andet fremmedsprog
|
| Sidst redigeret: |
31/10-2012 |