|
| Udgave: |
Forår 2013 NAT |
| ECTS points: |
7,5 |
| Point: |
7,5 |
| Point: |
7,5 |
| Blokstruktur: |
3. blok |
| Skemagruppe: |
C |
| Fagområde: |
dat |
| Varighed: |
5 weeks lectures, 2 weeks group work, 2 weeks paper presentations |
| Omfang: |
Lectures (20 hours), Discussions (8 hours), Student presentations (8 hours) |
| Institutter: |
Datalogisk Institut |
| Studieordning: |
Datalogi kandidat |
| Uddannelsesdel: |
Kandidat niveau |
| Kontaktpersoner: |
Pawel Winter, pawel@diku.dk, tlf.: 35321427 |
| 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: |
Lectures (5 weeks), discussions (2 weeks), Student presentations (2 weeks in the exam period) |
| Formål: |
The purpose of this course is to introduce the students to the methods for solving problems where geometrical properties are of particular importance. We will look at some basic problems, at algorithmic paradigms especially suited to solve such problems, and at geometric data structures. We will also look at the applications of computational geometry to the problems of molecular biology in particular. No a priori knowledge of molecular biology is required. During the course, the students will be asked to make a project proposal (7.5 or 15 ETCS) which they will have the opportunity to work on in the following block). |
| Indhold: |
Computational Geometry is concerned with the design
and analysis of algorithms and heuristics exploiting
the geometrical aspects of underlying problems
(i.e., routing problems, network design,
localization problems and intersection problems).
Applications can be found in VLSI-design,
pattern recognition, image processing,
operations research and statistics and molecular biology. |
| Kompetence- beskrivelse: |
By following this course, students will be able to:
- Describe, implement and use selected basic algorithms for solving geometric problems (e.g., convex hulls, localization, searching, visibility graphs.
- Apply geometric paradigms (e.g., plane sweep, fractional cascading, prune and search) and data structures (e.g., Voronoi diagrams, Delaunay triangulations, visibility graphs) to solve geometric problems.
- Present a scientific paper where computational geometry play crucial role (focus will be on molecular biology problems).
- Read computational geometry papers in scientific journals. |
| Målbeskrivelse: |
To obtain the grade 12, students must be able to:
- Describe selected basic algorithm for solving geometric problems (e.g., convex hulls, localization, searching, visibility graphs), argue for their time and space complexity, recognize their underlying general paradigms and data structures.
- Solve weekly (theoretical and implementational) exercise assignments.
- Present to other students a computational geometry paper.
- Formulate a project description (7.5 ETCS). The students will have the opportunity to work on the project in the following block. |
| Lærebøger: |
Is expected to be: M. de Berg et al. "Computational Geometry", 3-rd edition, Springer 2008. |
| Tilmelding: |
November 15 to December 1, 2012, via KUnet, www.kunet.dk. |
| Faglige forudsætninger: |
Introductory algorithms course. |
| Eksamensform: |
Oral examination without preparation (20 minutes), internal grading 7-point scale.
Reexam: as ordinary exam
|
| Eksamen: |
Mundtlig prøve d. 10. april 2013.
Reeksamen: Mundtlig prøve d. 26. juni 2013. |
| Kursus hjemmeside: |
 |
| Undervisnings- sprog: |
Kun engelsk
|
| Sidst redigeret: |
31/10-2012 |