Αναδρομη

(Α) Χρησιμοποιείστε επαγωγή για να αποδείξετε την ορθότητα του αλγόριθμου insertion sort

(Β) Δίνεται η αναδρομική σχέση Τ(n)=2T(n/2)+nlogn

Εφαρμόζοντας  τη μέθοδο της επανάληψης (τόμος Α, ενότητα 2.3.2, σελ 50) αρκετές φορές, «μαντέψτε» τη γενική μορφή της σχέσης που προκύπτει μετά από k επαναλήψεις, για οποιοδήποτε k. Να αποδείξετε κατόπιν αυστηρά, με επαγωγή στο k, ότι η διαίσθηση για τη γενική μορφή της σχέσης είναι πράγματι σωστή.

ΣΧΟΛΙΟ: Για παράδειγμα, ξεκινώντας με την αναδρομική σχέση Τ(n)=2T(n/2)+n

μετά από k επαναλήψεις μαντεύουμε ότι η σχέση είναι  .

 Τ(n)=2^kT(n/2^k)+kn

(Γ)  Δίνεται ο εξής αλγόριθμος:

procedure PATH(G,s,t)     %G πεπερασμένο γράφημα, s,t κορυφές του G

E:=E(G);                            % E πίνακας που περιέχει τις ακμές του G

Marked = {s};

while there is an edge (a,b)ÎE with aÎMarked, bÏMarked do

Marked:=Marked È {b};

E:= E \ {(a,b)};

return tÎMarked  ;

Για να αποδείξετε την ορθότητα του αλγόριθμου αποδείξτε τους ακόλουθους δύο ισχυρισμούς:

(Γ.1 Συνοχή/Εγκυρότητα) Όταν ο αλγόριθμος τερματίζει, με είσοδο (G,s,t), επιστρέφοντας TRUE, τότε υπάρχει μονοπάτι από s σε t.

ΥΠΟΔΕΙΞΗ: Χρησιμοποιείστε ισχυρή επαγωγή.

(Γ.2 Πληρότητα) Αν υπάρχει μονοπάτι από s σε t, τότε ο αλγόριθμος τερματίζει επιστρέφοντας TRUE.
-------------------------------------------------------------------
ΑΠΑΝΤΗΣΗ

< Απάντηση>

<Α>

Ο αλγόριθμος :

Insertion Sort (A).

1.      For j=2 to A[length]

2.      Key=A[j] // insertion Sort A[j} into the store sequence A[a… j-1]

3.      I:=j-1

4.      While i>0 and A[i]> Key

5.             A[i+1]=A[i]

6.              i=i-1

7.      A[i+1]=Key.

Ο Αλγόριθμος insertion Sort είναι ένα αποδοτικός αλγόριθμος για ταξινόμηση και ο τρόπος που ταξινομεί τους αριθμούς θυμίζει τον τρόπο που άνθρωποι ταξινομούν τραπουλόχαρτα όταν τα κρατάμε στα χέρια μας όπου ξεκινάμε από το πρώτο φύλλο στα χέρια μας το συγκρίνουμε με το διπλανά τοποθετώντας  το μικρότερο στα αριστερά και αυτό επαναλαμβάνετε κάθε φορά για κάθε χαρτί , στο τέλος θα έχουμε όλα τα φυλά ταξινομημένα.  Βλέποντας τον αλγόριθμο ξεκινά με έναν βρόχο που ξεκινά από το 2 ως το μήκος του πίνακα Α. Έπειτα στην βοηθητική μεταβλητή Key καταχωρεί το πρώτο στοιχείο του πίνακα και στην μεταβλητή i την τιμή του j-1 στοιχείου του πίνακα. Στην 4 γραμμή προσθέτουμε έναν ακόμη βρόγχο όπου πρέπει το I να είναι μεγαλύτερο του μηδενός και το στοιχείο A[j] μεγαλύτερο της προσωρινής μεταβλητής Key, εάν αληθεύει η διπλή συνθήκη τότε γίνεται swap το A[i+1] με το A[i] και μειώνει τον μετρητή κατά 1 . Η 7 γραμμή καταχωρεί στην A[i+1] την  προσωρινή μεταβλητή Key.

ΘΑ δούμε ένα παράδειγμα πως ταξινομεί  ο αλγόριθμος insertion sort.

Έστω έχουμε τον πίνακα A=[6 3 5 7 1]. H ταξινόμηση ξεκινά από αριστερά συγκρίνει το 3 με το 6και το 3<6 nbsp="" span="">swap) και θα μετακινηθεί το 3 στην θέση του 6 και ο πίνακας θα γίνει A=[3 6 5 7 1]. Έπειτα θα συγκρίνει το 5 με το 6 και το 5 θα αλλάξει θέση με το 6. Ακόμα το 5 θα συγκριθεί με το 3  και δεν θα αλλάξει θέση γιατί 5>3. Έτσι ο πίνακας θα είναι A=[3 5 6 7 1]. Συνεχίζουμε με το 4 στοιχείο του πίνακα που είναι ο αριθμός 7 και συγκρίνεται με το 6 που είναι μεγαλύτερο του . Έτσι ο πίνακας δεν μεταβάλετε. Τέλος με το τελευταίο στοιχείο του πίνακα ο αριθμός 1 θα συγκριθεί με το 7 και θα αλλάξει  θέση , έπειτα με το 6 και θα αλλαγή ξανά θέση έπειτα με το 5 και θα γίνει ξανά αλλαγή και τέλος με το 3 όπου θα αλλάξει  και εκεί θέση. Τελικά ο πίνακας θα είναι A=[1 3 5 6 7 ].

Το πλεονέκτημα του αλγορίθμου είναι ότι η ταξινόμηση πραγματοποιείται στον πίνακα χωρίς να χρειαστεί επιπλέον χώρο στην μνήμη, χρειάζεται μόνο μια βοηθητική μεταβλητή (key) για να πραγματοποιούνται  οι συγκρίσεις και οι αντικαταστάσεις.

Θα αποδείξουμε με την μέθοδο της επαγωγής την ορθότητα του αλγορίθμου

Για n=1 (δηλαδή Α[n])

Για ένα στοιχείο. Το στοιχείο που έχουμε να ταξινομήσουμε είναι 1 και ο πίνακας έχει μήκος 1 και ο υποπίνακας Α[1..j-1] είναι στην πραγματικότητά ο Α[1]   παράδειγμα Α=[5]  ο πίνακας Α  έχει ένα στοιχείο και  είναι ταξινομημένο  διότι δεν έχει να συγκριθεί με δεύτερο στοιχείο.

Ισχύει για n.

ΘΑ δείξουμε οτι για n στοιχεία ο βρόγχος επανάληψης συντηρείται ως ότι ταξινομηθούν τα στοιχεία στον πίνακα Α[1..j].

 Στο σώμα της For  επανάληψης λειτουργάει μετακινώντας το A[j-1], A[j-2], A[j-3].. μετακινώντας δεξιά στην κατάλληλη θέση του στοιχείου του πίνακα ώσπου να βρει την κατάλληλη  θέση για το Α[j] , . ο Υποπίνακας Α[1… j] αποτελείται από στοιχεία που είναι ταξινομημένα στον πίνακα Α[1..j]. Αυξάνοντας το j για κάθε επανάληψη του βρόγχου for μεγαλώνουμε τον το μήκος του υποπίνακα Α[1..j]συντηρώντας τον βρόγχο (ώσπου το j=n).

Για n+1

ΘΑ δείξουμε πότε τερματίζει ο βρόγχος (όταν n=n+1). Η συνθήκη τερματισμού είναι όταν  το j>A.length=n. Επειδή κάθε φορά  που εκτελείται ο βρόγχος αυξάνουμε το j κατά 1  θα φθάσει μια  στιγμή το n (j=n) και έπειτα μέσα στο βρόγχο θα εκτελεστεί το for και θα γίνει n+1 και ο πίνακας θα έχει στοιχεία A[1..n] και όλα τα στοιχεια του θα είναι ταξινομημένα όμως ο βρόγχος θα έχει σταματήσει γιατί j>n.

Η μέθοδος που ακολουθήσαμε είναι λίγο διαφορετική  από το προκαθορισμένο στο επαγωγικό βήμα σταματήσαμε τον βρόγχο for και αποδείξαμε ότι όλα τα στοιχεία του πίνακα Α[1..n] είναι ταξινομημένα.

<Β>

Αρχικά θα υπολογίσουμε η καλυτέρα θα κάνουμε  μερικές εφαρμογές του αναδρομικού κανόνα δηλαδή θα υπολογίσουμε  τιμές T(n) για να δούμε πως εξελίσσεται ο αλγόριθμος  ώστε να «μαντέψουμε « την μορφή του. Η Σχέση είναι

σχεση0

Για n/2 θα γίνει

σχεση1

Μπορούμε να αντικαταστήσουμε το Τ(n/2) και από την σχέση 1.

σχέση (2).

Υπολογίζω το Τ(n/4) από την σχέση 0 εχουμε

σχέση(2.0)

Μπορούμε να αντικαταστήσουμε στην σχέση 2 το Τ(n/4) με την σχέση (2.0). 

Υπολογίζω το Τ(n/8) από την σχέση 0

Αντικαθιστούμε το Τ(n/2³) με την σχέση (3.0)

Σχέση (4.0).

Από σχέση 0, σχέση 1 , σχέση 3 και  σχέση (4.0) έχουμε το Τ(n)

Κάναμε 3 βήματα ώστε να δούμε πως εξελισηται η αναδρομή έπειτα από 3 βήματα

 μπορούμε να εκτιμήσουμε την  αναδρομή.

Παρατηρούμε ότι η αναδρομή είναι

Σχέση f

Το κομαματι της αναδρωμης που είναι γραμμένη με κοκκινο χρωμα διακρινουμε από την επαγωγικη υποθεση δηλαδη  

Και ισχύει διότι το μέρος της εξίσωσης που είναι γραμμένο μωβ ισχειει από επαγωγική υπόθεση και είναι η αναδρομή με βάθος l ενώ αυτό που είναι με κοκκκινο xρωμα είναι απο την επαγωγικλη υποθεση το  δηλαδη +1 στον τυπο της