Build-Heap < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 09:42 Do 11.05.2006 | | Autor: | Moe007 |
| Aufgabe | Betrachte die beiden Implementierungen von BUILD-HEAP:
BUILD-HEAP(A)
heap-size[A] = 1
for i=2 to length[A]
do HEAP-INSERT(A,A[i])
BUILD-HEAP(A)
for i= heap-size[A]/2 downto 1
HEAPIFY(A,i)
Frage: Erzeugen die erste Prozedur bei jeder Eingabe dieselbe Ausgabe wie die zweite? Beweise das oder gebe ein Gegenbeispiel an. |
Hallo,
ich hoffe, es kann mir jemand einen Tipp geben, wie ich das beweisen soll.
Ich hab mir zu beiden Prozeduren Beispiele angeschaut, und festgestellt, dass beide tatsächlich dieselbe Ausgabe erzeugen. Also vermute ich mal, dass die Prozeduren dasselbe machen. Aber ich weiß leider nicht, wie ich das formal beweisen soll. ich hab so was noch nie gemacht. Daher weiß ich überhupt nicht, wie ich das ansetzen soll.
Mit Beispielen allein reicht es nicht zum Beweisen oder? Ein Gegenbeispiel hab ich bis dato noch nicht gefunden.
Ich hoffe, es kann mir jemand einen Tipp geben.
LG, Moe
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Mi 17.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
