|
| Udgave: |
Forår 2013 NAT |
| Point: |
7,5 |
| Blokstruktur: |
4. blok |
| Skemagruppe: |
A |
| Fagområde: |
dat |
| Institutter: |
Department for Computer Science |
| Studieordning: |
Computer Science Master |
| Uddannelsesdel: |
Kandidat niveau |
| Kontaktpersoner: |
Pawel Winter |
| Andre undervisere: |
Stephen Alstrup, Christian Wulff-Nilsen, Martin Zachariasen |
| 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 |
| Indhold: |
• Linear programming,
• Max Flow,
• NP-completeness,
• Branch-and-Bound + Heuristics,
• Approximation Algorithms,
• Ramdomized Algorithms,
• Computational Geometry
|
| Målbeskrivelse: |
After completing this course, students should be able to: formulate and solve linear optimization problems using the simplex algorithm, describe selected max-flow algorithms, describe various heuristic problem-solving methods, describe the shortcomings of brute-force algorithms, become familiar with the classes P and NP and with the NP-completeness, solve NP-hard problems using branch-and-bound, heuristics and approximation algorithms, prove correctness of algorithms, prove approximation factors, explain and use various metaheuristic problem-solving methods, explain the use of randomization in the design of an algorithm for a problem where a deterministic algorithm is unknown or much more difficult.
|
| Tilmelding: |
November 15 to December 1, 2012, via KUnet, www.kunet.dk |
| Faglige forudsætninger: |
It is assumed that the students are familiar with basic algorithms (sorting, selection, minimum spanning trees, shortest paths) and data structures (lists, stacks, binary trees, search trees, heaps). |
| Eksamensform: |
Oral exam with preparation (30 minutes) in course curriculum. Grade: 7-point scale. External grading. In order to qualify for the exam the student must complete 2 mandatory exercises.
Re-exam: same as ordinary exam.
|
| Eksamen: |
Mundtlig prøve d. 11-14. juni 2013.
Reeksamen: Mundtlig prøve d. 22. august 2013. |
| Kursus hjemmeside: |
 |
| Bemærkninger: |
Students who passed the bachelor course "videregående algoritmik" will not receive any credits by following this course. |
| Undervisnings- sprog: |
Kun engelsk
|
| Sidst redigeret: |
28/11-2012 |