Suche Home Einstellungen Anmelden Hilfe  

 
UNI Didaktik der 
Informatik
DdI
 Projekttage zum Erwerb eines Scheins zur
Vorlesung Algorithmen, Daten und Programme II, SS 98

Programmierung elementarer Algorithmen

Aufgabe 4
"Stadtmauer"

In den letzten Jahre hat sich gezeigt, dass der Planet Erde2 doch nicht unbewohnt war. Zum Schutz der Siedlungen sollen diese mit einer Stadtmauer minimaler Länge umgeben werden.

Schreiben Sie Programme in ML, welche ausgehend von den ganzzahligen Koordinaten der Mittelpunkte der Häuser die Reihenfolge der Häuser bestimmt,  die mittels Mauern verbunden die Stadtmauer bilden. Vergleichen Sie die unterschiedlichen Algorithmen!

Beispiel für eine Siedlung:
 
x-Koordinate
y-Koordinate
Hausnr.
8
17
1
9
16
2
12
18
3
9
19
4
10
17
5
7
16
6
9
15
7

 
Stadtmauer: 3,4,6,7

Stichworte: Konvexe Hülle, Package-Wrapping, Divide&Conquer, Graham-Scan, Interior Elimination
Literatur: Duden Informatik,  Algorithmen-Sedgewick S. 411ff, Mehlhorn Bd. 3 S. 79f
sowie: Turing-Omnibus S. 242  

Ergebnisse der Projektgruppe  

Benutzer: Gast • Besitzer: mthomas • Zuletzt geändert am: