Αλγόριθμοι - Δομές Δεδομένων

Εισαγωγή - Πίνακες

Καλώς ήρθατε

Αλγόριθμοι και Δομές Δεδομένων

• Διομήδης Σπινέλλης <dspin@kerkis.math.aegean.gr (mailto:dspin@kerkis.math.aegean.gr)>
• Βασικές δομές δεδομένων και αντίστοιχοι αλγόριθμοι
• Θεωρητική διδασκαλία
• Εργαστήριο
• Ασκήσεις
• Πρόοδος
• Εξετάσεις
• Τρίτη 9:00-11:00, Τετάρτη 10:00-12:00

Τι περιλαμβάνει το μάθημα

1. Εισαγωγή - Πίνακες
2. Στοίβες
3. Ουρές
4. Λίστες
5. Δένδρα
6. Β-Δένδρα
7. Γράφοι
8. Αναζήτηση
9. Κατακερματισμός
10. Ταξινόμηση
11. Τεχνικές αρχείων
12. Ανασκόπηση - επανάληψη

Οι σημειώσεις

• Δε θα μοιράζονται
• Βασίζονται στο βιβλίο Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. Εκδόσεις Νέων Τεχνολογιών, 1993.
• Προσβάσιμες από το WWW:http://kerkis.math.aegean.gr/~dspin/ads (http://kerkis.math.aegean.gr/~dspin/ads)
• Δεν καλύπτουν όλο το μάθημα

Οι ασκήσεις

Χρόνος παράδοσης

• Οι ασκήσεις πρέπει να παραδίδονται μέχρι τα μεσάνυχτα της Δευτέρας που ακολουθεί το πρώτο εργαστήριο μετά το αντίστοιχο μάθημα.
• Ως χρόνος παράδοσης ορίζεται ο τοπικός χρόνος του συστήματος (local system time) του μηχανήματος στο οποίο στέλνονται οι ασκήσεις.

Τρόπος παράδοσης

• Οι ασκήσεις παραδίδονται με τη χρήση ειδικού προγράμματος που υπάρχει στο μηχάνημα athena ως πηγαίος κώδικας Pascal σε μορφή απλού κειμένου (όχι MIME ή uuencoded). Αφού μεταφερθεί το αρχείο με το πρόγραμμα σε Pascal στο athena τρέχουμε την εντολή "perl ~dspin/submit" και απαντάμε στις ερωτήσεις που εμφανίζονται.
• Ασκήσεις που παραδίδονται με άλλο τρόπο δε θα λαμβάνονται υπόψη.

Περιεχόμενο

• Συντακτική ορθότητα. (Περνάει το πρόγραμμα από το μεταγλωττιστή χωρίς λάθη;)
• Συμμόρφωση με τις προδιαγραφές. (Υλοποιεί το πρόγραμμα τις προδιαγραφές της άσκησης;)
• Καθαρή δομή. (Επιλογή δομών δεδομένων, δομών ελέγχου, τύπων, συναρτήσεων και διαδικασιών.)
• Αναγνωσιμότητα. (Σχόλια, ονομασία τύπων, μεταβλητών, διαδικασιών και συναρτήσεων, στοίχιση.)
• Αμυντικός προγραμματισμός. (Συμπεριφορά του προγράμματος σε λάθη.)

Συνεργασία

• Συζητήσεις και ανταλλαγή απόψεων πάνω στο αντικείμενο της άσκησης επιτρέπονται και ενθαρρύνονται.
• Υλοποίηση των ασκήσεων από ομάδες μεγαλύτερες των δύο φοιτητών δεν επιτρέπεται.
• Σε περίπτωση που μια άσκηση έχει υλοποιηθεί από ομάδα θα πρέπει να σταλεί από τους λογαριασμούς και των δύο φοιτητών. Το πρόγραμμα στην περίπτωση αυτή θα πρέπει να περιέχει σε σχόλιο τους Α.Μ. των δύο μελών της ομάδος.
• Ασκήσεις στις οποίες δεν τηρούνται τα παραπάνω δε θα λαμβάνονται υπόψη.

Γενική βιβλιογραφία

• Ελληνική Εταιρία Επιστημόνων Ηλεκτρονικών Υπολογιστών και Πληροφορικής. Ελληνικό γλωσσάριο πληροφορικής. ΕΠΥ 1985.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
• David Harel. Algorithmics: the Spirit of Computing. Addison-Wesley, 1987.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms. Addison-Wesley, second edition, 1973.
• Donald E. Knuth. The Art of Computer Programming, volume 3 / Sorting and Searching. Addison-Wesley, 1973.
• William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, 1986.
• Robert Sedgewick. Algorithms in C. Addison-Wesley, 1990.
• Niklaus Wirth. Algorithms + Datastructures = Programs. Prentice–Hall, 1976.
• Niklaus Wirth. Algorithms and Data Structures. Prentice–Hall, 1986.

Αφηρημένοι τύποι δεδομένων

• Δεδομένα
• Μέθοδοι πρόσβασης
• Μέθοδοι μεταβολής

Πίνακες

• Οι πίνακες (arrays) επιτρέπουν τη χρήση πολλών ομοίου τύπου στοιχείων.
• Συνήθως το στοιχείο i ενός πίνακα A προσδιορίζεται ως A[i] ή A(i).
• Μπορούν να οριστούν και πίνακες πολλαπλών διαστάσεων με στοιχεία αντίστοιχα προσδιορισμένα ως A[i,j] κ.λπ.
• Συνήθως υλοποιούνται με τη διαδοχική φύλαξη των στοιχείων τους στη μνήμη.

Παράδειγμα

(* Άθροισμα στοιχείων του πίνακα n στοιχείων a *)
var
   a : array [1..10] of integer;
   n, i, sum : integer;

begin
     sum := 0;
     for i := 1 to 10 do
     begin
          sum := sum + a[i];
     end;
end.

Υλοποίηση πινάκων

• Πίνακες μιας διάστασης υλοποιούνται με τη διαδοχική φύλαξη των στοιχείων στη μνήμη.
• Πίνακες δύο διαστάσεων υλοποιούνται με τη διαδοχική φύλαξη των στοιχείων κάθε γραμμής (C, Pascal) ή κάθε στήλης (Fortran) στη μνήμη.
• Ανάλογα υλοποιούνται και πίνακες με περισσότερες από δύο διαστάσεις.
• Έτσι το στοιχείο i,j ενός πίνακα Ν*Μ στοιχείων μεγέθους Κ βρίσκεται στη θέση μνήμης Κ * (i * M + j).
• Πίνακες δύο και παραπάνω διαστάσεων μπορούν ακόμα να υλοποιηθούν με τη χρήση πινάκων μιας διαστάσης και δεικτών (C).

Πίνακες στην Pascal

• Ορισμός

  type
  	colors = (red, green, blue);
  var
     grades : array [1..120] of integer;
     temperatures : array [-5..5] of real;
     table : array [0..10,0..20] of real;
     screen : array [0..479,0..639] of array [red..blue] of integer;
  

• Χρήση

     grades[15] := 9;
     temperatures[-2] := 37.8;
     table[3,2] := 12.3;
     screen[5,7][red] := 12;
  

Ειδικές μορφές πινάκων

• Συμμετρικός (Symmetric)
• Τριγωνικός (Triangular)
• Τριδιαγώνιος (Tridiagonal)
• Αραιός (Sparse)

Πρόσβαση στα στοιχεία ενός πίνακα

• Πρόσβαση στα στοιχεία πίνακα μιας διάστασης:

  for i := 0 to 10 do
  	vector[i] := 5;
  

• Πρόσβαση στα στοιχεία πίνακα δύο διαστάσεων:

  for i := 0 to numrows do
  	for j := 0 to numcols do
  		sum := sum + table[i, j];
  

Μηδενισμός κατά Gauss

• Αλλαγή των εξισώσεων μεταξύ τους.
• Μετονομασία των μεταβλητών.
• Πολλαπλασιασμό των εξισώσεων με σταθερά.
• Πρόσθεση δύο εξισώσεων και αλλαγή μιας από αυτές με το σύνολο.

Παράδειγμα

( 1  3 -4 ) (x1)   ( 8)
( 1  1 -2 ) (x2) = ( 2)
(-1 -2  5 ) (x3)   (-1)

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 33-44 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 243–248. Addison-Wesley, second edition, 1973.
• William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes in C, pages 37–39. Cambridge University Press, 1988.
• Robert Sedgewick. Algorithms in C, pages 535–543. Addison-Wesley, 1990.
• Niklaus Wirth. Algorithms and Data Structures, pages 30–32. Prentice–Hall, 1986.

Ασκήσεις

Άσκηση ADS01

1. Να γραφεί πρόγραμμα σε Pascal το οποίο να λύνει το παρακάτω σύστημα εξισώσεων με τη μέθοδο του μηδενισμού κατά Gauss.

   ( 1  3 -4 ) (x1)   ( 8)
   ( 1  1 -2 ) (x2) = ( 2)
   (-1 -2  5 ) (x3)   (-1)
   

   Το πρόγραμμα μπορεί να χωριστεί σε τρεις διαδικασίες:
   • Assign: Εκχώρηση στον πίνακα των τιμών.
   • Eliminate: Τριγωνισμός του πίνακα με μηδενισμό.
   • Substitute: Αντικατάσταση τιμών και εκτύπωση των λύσεων.

Στοίβες

Ορισμός

• Η στοίβα (stack) είναι μια γραμμική διάταξη στοιχείων στην οποία κάθε πρόσθεση και αφαίρεση στοιχείων γίνεται μόνο στην κορυφή της.
• Στοιχεία εισάγονται με την ώθηση (push).
• Στοιχεία εξάγονται με την απώθηση (pop).
• Η μέθοδος φύλαξης που υλοποιεί η στοίβα λέγεται LIFO (Last In First Out).

Υλοποίηση στη μνήμη

• Τα στοιχεία φυλάσσονται σε διαδοχικές θέσεις.
• Ένας δείκτης ή καταχωρητής δείχνει την κορυφή της στοίβας.
• Το μέγεθος της στοίβας ορίζεται με σύμβαση.
• Πολλοί επεξεργαστές περιέχουν ειδικές εντολές για υλοποίηση στοίβας.

Υλοποίηση σε Pascal

• Η στοίβα υλοποιείται με τη μορφή πίνακα.
• Μια ξεχωριστή μεταβλητή δείχνει την κορυφή της στοίβας ή το επόμενο ελεύθερο στοιχείο.
• Απαραίτητοι οι έλεγχοι για υπερχείλιση και υποχείλιση.

Αφηρημένος τύπος

{ Αρχικοποιείται η στοίβα }

procedure stackInitialize;

{ Το στοιχείο i εισάγεται στην κορυφή της στοίβας }

procedure stackPush(i : integer);

{ Το στοιχείο από την κορυφή της στοίβας αφαιρείται και επιστρέφεται }

function stackPop : integer;

{ Επιστρέφεται αληθές αν η στοίβα είναι κενή }

function stackIsEmpty : boolean;

Εφαρμογές

• Κλήση υποπρογραμμάτων
• Χειρισμός διακοπών
• Γραφικά (τρισδιάστατη απεικόνιση)
• Λεκτική και συντακτική ανάλυση
• Αναδρομικές τεχνικές

Πολωνικός συμβολισμός

• Ο πολωνικός συμβολισμός (polish notation) προτάθηκε από τον Jan Lukasiewicz ως τρόπος συμβολισμού παραστάσεων χωρίς παρενθέσεις.
• Η τελεστές αντί να τοποθετηθούν ένθετα (infix) σε σχέση με του τελεστέους, τοποθετούνται προθεματικά (prefix)
• Ο αντίστροφος πολωνικός συμβολισμός (reverse polish notation) τοποθετεί τους τελεστές μεταθεματικά (postfix).
• Με τον τρόπο αυτό μπορεί να γίνει ο υπολογισμός αριθμητικών παραστάσεων λαμβάνοντας υπόψη την ιεραρχία των τελεστών.

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 45-55 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Dasta Structures and Algorithms, pages 53–55. Addison-Wesley, 1983.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 234–238. Addison-Wesley, second edition, 1973.
• Robert Sedgewick. Algorithms in C, pages 25–30. Addison-Wesley, 1990.

Ασκήσεις

Άσκηση ADS02

1. Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της στοίβας ακεραίων σύμφωνα με τις παρακάτω συναρτήσεις:

   { Αρχικοποιείται η στοίβα }

   procedure stackInitialize;

   { Το στοιχείο i εισάγεται στην κορυφή της στοίβας }

   procedure stackPush(i : integer);

   { Το στοιχείο από την κορυφή της στοίβας αφαιρείται και επιστρέφεται }

   function stackPop : integer;

   { Επιστρέφεται αληθές αν η στοίβα είναι κενός }

   function stackIsEmpty : bool;

2. Με βάση τον αφηρημένο αυτό τύπο να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει ακεραίους μέχρι να διαβάσει 0 και να τους τυπώνει με αντίστροφη σειρά.

Ουρές και δείκτες

Ορισμός

• Η ουρά (queue) είναι μια γραμμική διάταξη στοιχείων στην οποία κάθε πρόσθεση στοιχείων γίνεται στο τέλος της και κάθε αφαίρεση στοιχείων γίνεται από την αρχή της.
• Η μέθοδος φύλαξης που υλοποιεί η ουρά λέγεται FIFO (First In First Out).
• Συνδιασμός ουράς και στοίβας (επιτρέπει την εισαγωγή και εξαγωγή και από τα δύο άκρα) καλείται ουρά με δύο άκρα (dequeue (double ended queue)).

Υλοποίηση στη μνήμη

• Τα στοιχεία φυλάσσονται σε διαδοχικές θέσεις.
• Ένας δείκτης ή καταχωρητής δείχνει την αρχή της ουράς.
• Ένας δείκτης ή καταχωρητής δείχνει το τέλος της ουράς.
• Το μέγεθος της ουράς ορίζεται με σύμβαση.
• Μπορούμε να ορίσουμε ότι η ουρά είναι άδεια όταν η αρχή είναι ίδια με το τέλος.
• Όταν η αρχή ή το τέλος φτάσουν το μέγεθος της ουράς πρέπει να επιστρέψουν στην αρχή της (κυκλική ουρά).

Υλοποίηση σε Pascal

• Η ουρά υλοποιείται με τη μορφή πίνακα.
• Δύο ξεχωριστές μεταβλητές δείχνουν την αρχή και το τέλος της ουράς.
• Απαραίτητοι οι έλεγχοι για υπερχείλιση και υποχείλιση.

Αφηρημένος τύπος

{ Αρχικοποιείται η ουρά }

procedure queueInitialize;

{ Το στοιχείο i εισάγεται στο τέλος της ουράς }

procedure queuePut(i : integer);

{ Το στοιχείο από την αρχή της ουράς αφαιρείται και επιστρέφεται }

function queueGet : integer;

{ Επιστρέφεται αληθές αν η ουρά είναι κενή }

function queueIsEmpty : boolean;

Εφαρμογές

• Υλοποίηση ουράς προτεραιότητας
• Επίσκεψη κλάδων δέντρου κατά βάθος
• Αναγνώριση συμβολοσειρών
• Εύρεση στοιχείων σε γράφο με ανίχνευση κατά πλάτος

Δείκτες

Ορισμός

var
	p, q : ^integer;

Αρχικοποίηση

• με τη χρήση της διαδικασίας new, ή
• με την εκχώρηση στο δείκτη της τιμής ενός άλλου δείκτη.

	new(p);
	q = p

Χρήση

	p^ := 3;
	writeln(p^)

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 56-62, 72-75 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 56–60. Addison-Wesley, 1983.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 235–241. Addison-Wesley, second edition, 1973.
• Robert Sedgewick. Algorithms in C, pages 30–31, 300–301, 431, 457. Addison-Wesley, 1990.

Ασκήσεις

Άσκηση ADS03

1. Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της ουράς ακεραίων σύμφωνα με τις παρακάτω συναρτήσεις:

   { Αρχικοποιείται η ουρά }

   procedure queueInitialize;

   { Το στοιχείο i εισάγεται στο τέλος της ουράς }

   procedure queuePut(i : integer);

   { Το στοιχείο από την αρχή της ουράς αφαιρείται και επιστρέφεται }

   function queueGet : integer;

   { Επιστρέφεται αληθές αν η ουρά είναι κενή }

   function queueIsEmpty : boolean;

2. Με βάση τον αφηρημένο αυτό τύπο και μονοτονικά αυξανόμενη μεταβλητή να υλοποιηθεί πρόγραμμα το οποίο να υλοποιεί ουρά εξυπηρέτησης πελατών ως εξής:
   1. Όταν εισάγεται ο χαρακτήρας I (In) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του νέου πελάτη.
   2. Όταν εισάγεται ο χαρακτήρας O (Out) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του επόμενου πελάτη που θα εξυπηρετηθεί.
   Παράδειγμα:

   I
   1
   I
   2
   I
   3
   O
   1
   I
   4
   O
   2
   ...
   

Συνδεδεμένες λίστες

Ορισμός

• Η συνδεδεμένη λίστα (linked list) είναι μια γραμμική διάταξη στοιχείων των οποίων η σειρά ορίζεται έμμεσα με τη βοήθεια δεικτών.
• Κάθε στοιχείο της λίστας περιέχει και έναν δείκτη (pointer) ο οποίος δείχνει τη θέση του επόμενου στοιχείου.
• Το τέλος της λίστας απεικονίζεται με έναν δείκτη που περιέχει μια ειδική τιμή καθορισμένη με σύμβαση.

Υλοποίηση στη μνήμη

• Κάθε στοιχείο περιέχει εκτός από τα δεδομένα του και ένα δείκτη.
• Τα στοιχεία φυλάσσονται σε τυχαίες θέσεις.
• Ο δείκτης κάθε στοιχείου δείχνει τη διεύθυνση του επόμενου στοιχείου.
• Ένας δείκτης με ειδική τιμή (καθορισμένη με σύμβαση π.χ. 0) δείχνει ότι το τελευταίο στοιχείο δεν ακολουθείται από άλλο.
• Η διαχείριση της μνήμης γίνεται συνήθως από ειδικό υποσύστημα τον κατανεμητή μνήμης (memory allocator).
• Σε περιπτώσεις όπου η μνήμη δεν ελευθερώνεται μέσω του κατανεμητή ένα άλλο υποσύστημα φροντίζει για την αποκομιδή αχρήστων (garbage collection).

Υλοποίηση με πίνακα

• Η συνδεδεμένη λίστα υλοποιείται με βάση δύο πίνακες με ίδιο μήκος.
• Ο ένας πίνακας περιέχει τα στοιχεία και ο δεύτερος περιέχει την επόμενη θέση για κάθε στοιχείο.
• Οι άδειες θέσεις του πίνακα μπορούν να παριστάνονται με μια ειδική τιμή αντί για δείκτη ή με τη χρήση μιας άλλης συνδεδεμένης λίστας.

Υλοποίηση σε Pascal

• Οι δείκτες υλοποιούνται με τη χρήση δεικτών της Pascal.
• Τα στοιχεία ομαδοποιούνται με τους δείκτες ως μια εγγραφή.
• Το τέλος της λίστας συμβολίζεται με την ειδική τιμή δείκτη της Pascal nil.
• Μνήμη για κάθε στοιχείο αποκτούμε με τη χρήση της διαδικασίας new.

program list;

type
    intList = ^intListElem;

    intListElem = record
        val : integer;
        next : intList;
    end;


var
    theList, node : intList;

begin
    new(node);
    node^.val := 5;
    node^.next := nil;
    theList := node;

    new(node);
    node^.val := 12;
    node^.next := theList;
    theList := node
end.

Αφηρημένος τύπος

{ Ορισμός του τύπου της συνδεδεμένης λίστας }

type
    intList = ^intListElem;

    intListElem = record
        val : integer;
        next : intList;
    end;

{ Επιστρέφεται μια άδεια συνδεδεμένη λίστα }

function newIntList : intList;

{ Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i στην αρχή της }

function addIntList(l : intList; i : integer) : intList;

{ Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i διαγραμμένο }

function delIntList(l : intList; i : integer) : intList;

{ Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή i }

function searchIntList(l : intList; i : integer) : intList;

{ Επιστρέφεται αληθές αν η λίστα είναι κενή }

function isEmtyIntList(l : intList) : boolean;

Ειδικές μορφές λιστών

διπλά συνδεδεμένη λίστα (doubly linked list)

Κάθε στοιχείο της λίστας έχει δείκτες στο προηγούμενο και το επόμενο.

κυκλικά συνδεδεμένη λίστα

Το τελευταίο στοιχείο της λίστας δείχνει ξανά το πρώτο. Η δομή αυτή ονομάζεται και δακτύλιος (ring).

κυκλικά διπλά συνδεδεμένη λίστα

Σύνθεση των παραπάνω.

Εφαρμογές

• Υλοποίηση δομών δεδομένων με δυναμικά αυξανόμενο μέγεθος.
• Διαχείριση μνήμης.
• Οργάνωση δεδομένων σε πολλαπλές δομές.

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 63-80 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 37–52. Addison-Wesley, 1983.
• Hans-Juergen Boehm. Garbage collection in an uncooperative environment. Software: Practice & Experience, 18(9):807–820, September 1988.
• Jacques Cohen. Garbage collection of linked data structures. Computing Surveys, 13(3):339–367, September 1981.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 251–258. Addison-Wesley, second edition, 1973.
• Robert Sedgewick. Algorithms in C, pages 17–22. Addison-Wesley, 1990.
• Norihisa Suzuki. Analysis of pointer ``rotation''. Communications of the ACM, 25(5):330–335, May 1982.
• Niklaus Wirth. Algorithms and Data Structures, pages 180–182. Prentice–Hall, 1986.

Ασκήσεις

Άσκηση ADS04

1. Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της συνδεδεμένης λίστας χαρακτήρων σύμφωνα με τις παρακάτω συναρτήσεις:

   { Ορισμός του τύπου της συνδεδεμένης λίστας }

   type
       charList = ...
   

   { Επιστρέφεται μια άδεια συνδεδεμένη λίστα }

   function newCharList : charList;

   { Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο c στην αρχή της }

   function addCharList(l : charList; c : char) : charList;

   { Επιστρέφεται μια συνδεδεμένη λίστα με το πρώτο στοιχείο διαγραμμένο. Κατά την επιστροφή η μεταβλητή c περιέχει την τιμή του. }

   function delCharListHead(l : charList; var c : char) : charList;

   { Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή c }

   function searchCharList(l : charList; c : char) : charList;

   { Επιστρέφεται αληθές αν η λίστα είναι κενή }

   function isEmtyCharList(l : charList) : boolean;

2. Με βάση τον αφηρημένο αυτό τύπο να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει μια σειρά χαρακτήρων μέχρι να συναντήσει μια τελεία και στη συνέχεια να τυπώνει τους χαρακτήρες αυτούς με την αντίστροφη σειρά.
   Παράδειγμα:

   L
   I
   V
   E
   .
   E
   V
   I
   L
   

   Περισσότερες λεπτομέρειες για τις ασκήσεις

   Δένδρα

   Ορισμοί

   • Ένα δένδρο (tree) είναι ένα σύνολο από κόμβους (nodes) που ενώνονται με ακμές (edges) και εκπληρεί την παρακάτω ιδιότητα:
     • Αν ορίσουμε ως μονοπάτι (path) ένα σύνολο κόμβων ενωμένων με ακμές και ένα συγκεκριμένο κόμβο ως ρίζα (root) του δέδρου τότε κάθε άλλος κόμβος ενώνεται με τη ρίζα με ένα και μόνο ένα μονοπάτι.
   • Αν παραστήσουμε το δένδρο με τη ρίζα προς τα πάνω τότε κάθε κόμβος - εκτός από τη ρίζα - θα έχει ακριβώς ένα κόμβο από πάνω του ο οποίος και ονομάζεται πατέρας (father) του.
   • Αντίστοιχα οι κόμβοι που βρίσκονται κάτω από τον πατέρα ονομάζονται παιδιά (children) του.
   • Βαθμός (Degree) ενός κόμβου ορίζεται ως ο αριθμός των παιδιών του.
   • Βαθμός ενός δένδρου είναι ο μεγιστός βαθμός όλων των κόμβων του.
   • Κόμβοι χωρίς παιδιά ονομάζονται τερματικοί κόμβοι (terminal nodes) ή εξωτερικοί κόμβοι (external nodes) ή φύλλα (leaves).
   • Κόμβοι με παιδιά ονομάζονται μη τερματικοί κόμβοι (non-terminal nodes) ή εσωτερικοί κόμβοι (internal nodes) ή κλαδιά (branches).
   • Επίπεδο (Level) ενός κόμβου ορίζεται ως ο αριθμός των κόμβων στο μονοπάτι από τον κόμβο μέχρι τη ρίζα.
   • Το μέγιστο επίπεδο των κόμβων του δδένδρου ονομάζεται βάθος (depth) ή ύψος (height) του δένδρου.
   • Υπόδενδρο (Subtree) είναι ένα δένδρο το οποίο σχηματίζεται έχοντας ως ρίζα κάποιον άλλο κόμβο.
   • Δάσος (Forest) είναι ένα σύνολο από δένδρα και σχηματίζεται αν κόψουμε ένα δένδρο σε έναν κόμβο με παιδιά.
   • Ένα δένδρο του οποίου κάθε κόμβος έχει δύο το πολύ ακμές ονομάζεται δυαδικό δένδρο (binary tree).

   Ιδιότητες

   • Δύο κόμβοι ενώνονται από ένα ακριβώς μονοπάτι
   • Ένα δένδρο με Ν κόμβους έχει Ν - 1 ακμές
   • Ένα δένδρο βαθμού d και ύψους h μπορεί να έχει sum(0, h-1, d^i) κόμβους.
   • Ένα πλήρες δυαδικό δένδρο ύψους h θα έχει 2^h - 1 κόμβους.
   • Ένα πλήρες δυαδικό δένδρο με n κόμβους θα έχει log n ύψος.

   Υλοποίηση σε Pascal

   • Οι ακμές υλοποιούνται με τη χρήση δεικτών της Pascal.
   • Τα στοιχεία ομαδοποιούνται με τους δείκτες ως μια εγγραφή.
   • Οι εξωτερικοί κόμβοι συμβολίζονται με την ειδική τιμή δείκτη της Pascal nil.
   • Μνήμη για κάθε στοιχείο αποκτούμε με τη χρήση της διαδικασίας new.
   Παράδειγμα:

   program bintree;
   
   type
       binTree = ^binTreeElem;
   
       binTreeElem = record
           val : integer;
           left : binTree;
           right : binTree;
       end;
   
   
   var
       theTree, node : binTree;
   
   begin
       new(node);
       node^.val := 5;
       node^.left := nil;
       node^.right := nil;
       theTree := node;
   
       new(node);
       node^.val := 12;
       node^.left := nil;
       node^.right := nil;
       theTree^.right = node;
   end.
   

   Δένδρα αναζήτησης

   • Διατεταγμένο είναι ένα δένδρο στο οποίο η διάταξη των κόμβων έχει σημασία
   • Σε ένα δυαδικό δένδρο αναζήτησης η τιμή κάθε κόμβου είναι μεγαλύτερη ή ίση από τις τιμές των κόμβων του αριστερού υποδένδρου και μικρότερη ή ίση από τις τιμές των κόμβων του δεξιού υποδένδρου.
   • Σε ένα τέτοιο δένδρο η αναζήτηση για μια τιμή απαιτεί τόσες συγκρίσεις όσο είναι και το μέγιστο μήκος μονοπατιού.

   Διάσχιση δένδρων

   Η διάσχιση ενός δένδρου μπορεί να γίνει με τους παρακάτω τρόπους ανάλογα με τη σειρά επίσκεψης των κόμβων:

   Προδιαταγμένη διάσχιση (preorder traversal)

   1. επίσκεψη της ρίζας
   2. επίσκεψη του αριστερού υποδένδρου
   3. επίσκεψη του δεξιού υποδένδρου

   Μεταδιαταγμένη διάσχιση (postorder traversal)

   1. επίσκεψη του αριστερού υποδένδρου
   2. επίσκεψη του δεξιού υποδένδρου
   3. επίσκεψη της ρίζας

   Ενδοδιαταγμένη διάσχιση (inorder traversal)

   1. επίσκεψη του αριστερού υποδένδρου
   2. επίσκεψη της ρίζας
   3. επίσκεψη του δεξιού υποδένδρου

   Επίπεδοδιαταγμένη διάσχιση (level order traversal)

   1. επίσκεψη των κόμβων από πάνω προς τα κάτω

   Εφαρμογές

   • Υλοποίηση δομών αναζήτησης
   • Παράσταση συντακτικών δομών (γλώσσες προγραμματισμού και φυσικές γλώσσες)
   • Παράσταση ιεραρχικών δομών (κατανεμημένες βάσεις, μοντελοποίηση)

   Βιβλιογραφία

   • Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 81-97 Εκδόσεις Νέων Τεχνολογιών, 1993.

   • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 75–106. Addison-Wesley, 1983.
   • Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 305–422. Addison-Wesley, second edition, 1973.
   • Robert Sedgewick. Algorithms in C, pages 35–49. Addison-Wesley, 1990.
   • Niklaus Wirth. Algorithms and Data Structures, pages 196–217. Prentice–Hall, 1986.

   Ασκήσεις

   Άσκηση ADS05

   1. Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο με τη χρήση διατεταγμένου δυαδικού δένδρου διαβάζει από το χρήστη μια σειρά από ονόματα μέχρι να συναντήσει τελεία και τα εκτυπώνει με αλφαβητική σειρά. Παράδειγμα:

      Pascal
      Gauss
      Newton
      Einstein
      .
      Einstein
      Gauss
      Newton
      Pascal
      

   Περισσότερες λεπτομέρειες για τις ασκήσεις

   Γράφοι

   Ορισμοί

   • Ένας γράφος (graph) είναι ένα σύνολο από κόμβους που ενώνονται με ακμές.
   • Ο γράφος ορίζεται πλήρως από τους κόμβους και τη συνδεσμολογία τους.
   • Αν οι ακμές είναι προσανατολισμένες (ορίζονται δηλαδή από διατεταγμένα ζεύγη κόμβων) τότε ο γράφος λέγεται κατευθυνόμενος (directed).
   • Αν οι ακμές δεν είναι προσανατολισμένες (ορίζονται δηλαδή από μη διατεταγμένα ζεύγη κόμβων) τότε ο γράφος λέγεται μη κατευθυνόμενος (undirected).
   • Αν οι ακμές είναι συνδεδεμένς με κάποια αξία (βάρος) τότε ο γράφος λέγεται σταθμισμένος (weighted).
   • Πλήρης (Complete) ορίζεται ο μη κατευθυνόμενος γράφος που περιέχει ακμές που ενώνουν κάθε ζεύγος κόμβων.
   • Αραιός καλείται ο γράφος που περιέχει λίγες σχετικά ακμές (λ.χ. για ν κόμβους ο αριθμός των ακμών < ν log ν).
   • Πυκνός (Dense) καλείται ο γράφος από τον οποίο απουσιάζουν λίγες σχετικά ακμές.

   Παράσταση

   Ένας γράφος μπορεί εύκολα να παρασταθεί με δύο διαφορετικούς τρόπους:
   1. πίνακα γειτνίασης (adjacency matrix).
   2. λίστα γειτνίασης (adjacency list).
   Και οι δύο τρόποι προϋποθέτουν ένα μονοσήμαντο σύστημα αρίθμησης των κόμβων.

   Πίνακας γειτνίασης

   Σε έναν γράφο με ν κόμβους ο πίνακας ν*ν γειτνίασης περιέχει 1 στις θέσεις (κ,λ) όπου υπάρχει ακμή από τον κόμβο κ στον κόμβο λ.

   Λίστα γειτνίασης

   Κάθε κόμβος συσχετίζεται με μια συνδεδεμένη λίστα γειτνίασης η οποία περιέχει τα ονόματα των άλλων κόμβων με τους οποίους συνδέεται ο συγκεκριμένος κόμβος. Οι λίστες για όλους τους κόμβους ν μπορούν να ξεκινούν από έναν μονοδιάστατο πίνακα μήκους ν ή από μια άλλη συνδεδεμένη λίστα.

   Υλοποίηση σε Pascal

   Πίνακας γειτνίασης

   program matrixGraph;
   
   const
       n = 10;	(* Number of nodes *)
   
   var
       graph = array [1..n,1..n] of boolean;
   
   ...
   

   Λίστα γειτνίασης

   program listGraph;
   
   const
       n = 10;	(* Number of nodes *)
   
   type
       adjList = ^adjListElem;
   
       adjListElem = record
           node : integer;
           next : adjList;
       end;
   
   var
       graph = array [1..n] of adjList;
   
   ...
   

   Πρόσθετοι ορισμοί

   • Διαδρομή (path) καλείται μια διάταξη κόμβων οι οποίοι ενώνονται με ακμές.
   • Απλή διαδρομή (simple path) καλείται η παραπάνω διάταξη όταν κάθε κόμβος εμφανίζεται μια μόνο φορά.
   • Κύκλος (cycle) καλείται η διαδρομή δύο ή περισσοτέρων κόμβων που καταλήγει στον κόμβο αρχής.
   • Απόσταση (distance) μεταξύ δύο κόμβων καλείται το μήκος της συντομότερης διαδρομής που τους ενώνει.
   • Διαδρομή Euler (Euler path) καλείται η διαδρομή ή οποία περνάει από όλες τις ακμές του γράφου ακριβώς μια φορά.
   • Διαδρομή Hamilton (Hamilton path) καλείται η διαδρομή ή οποία περνάει από όλους τους κόμβους του γράφου ακριβώς μια φορά.
   • Γράφοι που περιέχουν τις παραπάνω διαδρομές ονομάζονται αντίστοιχα.
   • Συνεκτικός (connected) ονομάζεται ο γράφος για τον οποίο υπάρχει διαδρομή από κάθε κόμβο σε κάθε άλλο κόμβο.
   • Βαθμός ενός κόμβου σε έναν μη κατευθυνόμενο γράφο καλείται ο αριθμός των συνδεδεμένων με αυτόν ακμών.
   • Βαθμός εισόδου (in-degree) σε έναν κατευθυνόμενο γράφο καλείται ο αριθμός των ακμών που καταλήγουν σε αυτόν.
   • Βαθμός εξόδου (out-degree) σε έναν κατευθυνόμενο γράφο καλείται ο αριθμός των ακμών που ξεκινούν από αυτόν.
   • Υπογράφος (subgraph) Β ενός γράφου Α καλείται ο γράφος του οποίου όλες οι ακμές και οι κόμβοι περιέχονται στον Α.
   • Δένδρο σκελετός (spanning tree) ενός γράφου καλείται ο υπογράφος που περιέχει όλους του κόμβους αλλά μόνο όσες ακμές απαιτούνται για να σχηματιστεί δένδρο.

   Προτάσεις σε συνεκτικούς μη κυκλικούς γράφους

   Οι παρακάτω προτάσεις είναι ισοδύναμες για πεπερασμένους γράφους με ν > 0 κόμβους:
   1. Ο γράφος Γ είναι συνεκτικός και μη κυκλικός.
   2. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
   3. Δύο διαφορετικοί κόμβοι συνδέονται από μια και μόνο μια απλή διαδρομή.
   4. Ο γράφος είναι μη κυκλικός και περιέχει ν - 1 ακμές.
   5. Ο γράφος είναι συνεκτικός και περιέχει ν - 1 ακμές.

   Ψάξιμο κατά βάθος

   Για να επισκευθούμε όλους τους κόμβους ενός γράφου με ν κόμβους χρειαζόμαστε έναν πίνακα λογικών μεταβλητών μιας διάστασης και μήκους ν ο οποίος περιέχει την τιμή "αληθές" για τους κόμβους τους οποίους έχουμε επισκευθεί. Η συστηματική επίσκεψη όλων των κόμβων γίνεται σύμφωνα με τα παρακάτω βήματα:
   1. Φυλάμε την τιμή "ψευδές" στον πίνακα επισκέψεων.
   2. Επισκεπτόμαστε όλους τους κόμβους που δεν έχουμε επισκευτεί.

   Η επίσκεψη ενός κόμβου γίνεται σύμφωνα με τα παρακάτω βήματα:
   1. Σημειώνουμε στον πίνακα ότι έχουμε επισκευθεί τον κόμβο.
   2. Επισκεπτόμαστε όλους τους συνδεδεμένους κόμβους που δεν έχουμε επισκευθεί.
   Ο παραπάνω αλγόριμος για γράφο Κ κόμβων και Α ακμών απαιτεί:
   • Για γράφο που παριστάνουμε με πίνακα γειτνίασης χρόνο ανάλογο με Κ * Κ.
   • Για γράφο που παριστάνουμε με λίστα γειτνίασης χρόνο ανάλογο με Κ + Α.

   Εφαρμογές

   • Παράσταση διασυνδέσεων ανάμεσα σε αντικείμενα
     • Ταξίδια ανάμεσα σε πόλεις
     • Συνδέσεις υπολογιστών σε δίκτυο
     • Συνδέσεις σελίδων σε υπερκείμενο
     • Ανθρώπινες σχέσεις
   • Παράσταση ηλεκτρονικών διαγραμμάτων
   • Προγραμματισμός εργασιών

   Βιβλιογραφία

   • Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 98-105 Εκδόσεις Νέων Τεχνολογιών, 1993.

   • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms, pages 172–309. Addison-Wesley, 1974.
   • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 198–252. Addison-Wesley, 1983.
   • Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 362–378. Addison-Wesley, second edition, 1973.
   • Robert Sedgewick. Algorithms in C, pages 415–508. Addison-Wesley, 1990.

   Ασκήσεις

   Άσκηση ADS06

   1. Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο διαβάζει ζεύγη συνδεδεμένων κόμβων ενός γράφου ακεραίων μέχρι να συναντήσει το ζεύγος (0,0) και στη συνέχεια επισκέπτεται κατά βάθος όλους τους κόμβους και τυπώνει τον αριθμό τους στο τέλος της διαδικασίας επίσκεψης.

      Παράδειγμα:

      5 3
      5 2
      0 2
      4 0
      0 5
      1 6
      1 5
      0 0
      
      
      2
      3
      5
      0
      6
      1
      

      Αριθμήστε στην τύχη όλα τα ρούχα σας (π.χ. παπούτσια = 1, κάλτσες = 6) και εκφράστε την έννοια ότι για να φορέσετε το Α πρέπει να έχετε φορέσει το Β ως ένα ζεύγος (Α, Β) (π.χ. 1 6). Δώστε όλα τα ζεύγη που εκφράζουν τις ανάγκες σας για να ντυθείτε με λογικό τρόπο και ελέγξτε την σειρά ενδυμασίας που προτείνει το πρόγραμμα. (Η ταξινόμιση αυτή ονομάζεται τοπολογική ταξινόμιση (topological sorting)).
   Περισσότερες λεπτομέρειες για τις ασκήσεις

   Αναζήτηση

   Εισαγωγή

   • Οι αλγόριθμοι αναζήτησης (searching algorithms) επιτρέπουν την εύρεση ενός στοιχείου σε μια δομή δεδομένων με βάση ένα χαρακτηριστικό του.
   • Αν τα στοιχεία είναι οργανωμένα σε εγγραφές (records) και κάθε μια από αυτές απαρτίζεται από πεδία (fields) τότε το πεδίο με βάση το οποίο γίνεται η αναζήτηση ονομάζεται κλειδί (key) της αναζήτησης.
   • Το κόστος μιας αναζήτησης εκφράζεται ανάλογα με τον αριθμό συγκρίσεων που απαιτούνται κατά μέσο όρο για την εύρεση της αναζητούμενης εγγραφής.

   Σειριακή αναζήτηση

   • Στη σειριακή αναζήτηση (sequential search) η εύρεση της εγγραφής στον πίνακα γίνεται ελέγχοντας μια-μια τις εγγραφές από την αρχή μέχρι το τέλος του πίνακα.
   • Αν ο πίνακας έχει Ν στοιχεία θα απαιτηθούν κατά μέσο όρο N / 2 συγκρίσεις.

   Αναζήτηση κατά ομάδες

   • Στην αναζήτηση κατά ομάδες (group search) η εύρεση της εγγραφής στον πίνακα γίνεται χωρίζοντας τον (ταξινομημένο) πίνακα σε Μ ομάδες και ελέγχοντας πρώτα σε ποια ομάδα ανήκει η εγγραφή και στη συνέχει ελέγχοντας μια-μια τις εγγραφές από την αρχή μέχρι το τέλος της συγκεκριμένης ομάδας.
   • Ο βέλτιστος αριθμός ομάδων είναι sqrt(N).
   • Αν ο πίνακας έχει Ν στοιχεία και Μ ομάδες θα απαιτηθούν κατά μέσο όρο Ν/(2Μ) + Μ / 2 συγκρίσεις.

   Δυαδική αναζήτηση

   • Στη δυαδική αναζήτηση (binary search) η εύρεση της εγγραφής στον (ταξινομημένο) πίνακα γίνεται αναζητώντας το στοιχείο στη μέση του πίνακα, στη συνέχεια στη μέση της μέσης κ.ο.κ.
   • Αν ο πίνακας έχει Ν στοιχεία θα απαιτηθούν κατά μέσο όρο log2 N συγκρίσεις.

   Αναζήτηση παρεμβολής

   • Στη αναζήτηση παρεμβολής (interpolation search) η εύρεση της εγγραφής στον (ταξινομημένο) πίνακα γίνεται υπολογίζοντας την πιθανή θέση της εγγραφής σε σχέση με τις τιμές των στοιχείων στα άκρα της περιοχής αναζήτησης. Ανάλογα με τη σύγκριση της τιμής της εγραφής με την εγγραφή στην πιθανή θέση αναπροσαρμόζεται το αντίστοιχο άκρο.
   • Αν ο πίνακας έχει στοιχεία ομοιόμορφα κατανεμημένα θα απαιτηθούν O(log log n) συγκρίσεις.

   Βιβλιογραφία

   • Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 107-118 Εκδόσεις Νέων Τεχνολογιών, 1993.

   • Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.

   • Niklaus Wirth. Algorithms + Datastructures = Programs. p. 56-72. Prentice-Hall, 1976.

   Ασκήσεις

   Άσκηση ADS07

   1. Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο με δυαδική αναζήτηση σε πίνακα που περιέχει όλα τα φωνήεντα να εκτυπώνει αν ένα γράμμα που έδωσε ο χρήστης είναι φωνήεν ή σύμφωνο.

      Παράδειγμα:

      A
      FONIEN
      G
      SYMFONO
      

   Περισσότερες λεπτομέρειες για τις ασκήσεις

   Ταξινόμηση

   Εισαγωγή

   • Οι αλγόριθμοι ταξινόμησης (sorting algorithms) θέτουν τα στοιχεία μιας δομής δεδομένων σε σειρά σύμφωνα με μια ορισμένη σχέση διάταξης.
   • Αν τα στοιχεία είναι οργανωμένα σε εγγραφές (records) και κάθε μια από αυτές απαρτίζεται από πεδία (fields) τότε το πεδίο με βάση το οποίο γίνεται η ταξινόμηση ονομάζεται κλειδί (key) της ταξινόμησης.
   • Το κόστος μιας ταξινόμησης εκφράζεται ανάλογα με τον αριθμό συγκρίσεων και μετακινήσεων που απαιτούνται κατ' ελάχιστο, μέγιστο και κατά μέσο όρο.
   • Συχνά για να αποφευχθεί το κόστος των μετακινήσεων αντί για τα στοιχεία, ταξινομήται ένας πίνακας με δείκτες στα αντίστοιχα στοιχεία.

   Ταξινόμηση με παρεμβολή

   • Στη ταξινόμηση με παρεμβολή (insertion sort) τα στοιχεία χωρίζονται σε:
     • αυτά τα οποία έχουν ταξινομηθεί,
     • αυτό τα οποία θα ταξινομηθεί, και
     • αυτά τα οποία δεν έχουν ταξινομηθεί.
   • Σε κάθε βήμα το στοιχείο που πρέπει να ταξινομηθεί εισάγεται στη σωστή θέση αυτών που έχουν ταξινομηθεί.
   • Για την εύρεση του σημείου εισαγωγής μπορεί να χρησιμοποιηθεί και ο αλγόριθμος της δυαδικής αναζήτησης.
   • Οι συγκρίσεις που απαιτούνται είνα n-1 ... n*log(n)-exp(n-1) ... (n*n+n)/2-1
   • Οι μετακινήσεις που απαιτούνται είναι n ... 1/4(n*n+n+2) ... (n*n+n)/2

   Ταξινόμηση με επιλογή

   • Στη ταξινόμηση με επιλογή (selection sort) τα στοιχεία χωρίζονται σε:
     • αυτά τα οποία έχουν ταξινομηθεί,
     • αυτά τα οποία δεν έχουν ταξινομηθεί.
   • Σε κάθε βήμα επιλέγεται το ελάχιστο στοιχείο από αυτά τα οποία δεν έχουν ταξινομηθεί και εισάγεται στο τέλος των στοιχείων που έχουν ταξινομηθεί.
   • Οι συγκρίσεις που απαιτούνται είνα (n*n-n)/2
   • Οι μετακινήσεις που απαιτούνται είναι (n-1)/3 ... n*n/4 + (n-1)/3

   Ταξινόμηση με αντιμετάθεση

   • Στη ταξινόμηση με αντιμετάθεση (exchange sort) τα στοιχεία ταξινομούνται με διαδοχική αντιμετάθεση ζευγών που δεν ακολουθούν τη διάταξη της ταξινόμησης.
   • Ο αλγόριθμος μπορεί να βελιτωθεί εναλλάσσοντας σε κάθε πέρασμα τη φορά του ελέγχου.
   • Στην πρώτη περίπτωση ονομάζεται bubble sort (ταξινόμηση φυσαλίδας), στη δεύτερη shake sort.

   Ταξινόμηση με διαμερισμό και αντιμετάθεση

   • Στην ταξινόμηση με διαμερισμό (partition exchange sort) (ή γρήγορη ταξινόμηση (quick sort)) επιλέγεται ένα στοιχείο του πίνακα και τα υπόλοιπα στοιχεία μοιράζονται σε δύο υποπίνακες ανάλογα με τη σχέση τους με το στοιχείο αυτό.
   • Στη συνέχεια ο αλγόριθμος καλείται αναδρομικά για τους δύο υποπίνακες.
   • Οι συγκρίσεις που απαιτούνται είναι n
   • Οι μετακινήσεις που απαιτούνται είναι n*log(n)/6

   Βιβλιογραφία

   • Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 119-132 Εκδόσεις Νέων Τεχνολογιών, 1993.

   • Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.

   • Niklaus Wirth. Algorithms + Datastructures = Programs. p. 73-134. Prentice-Hall, 1976.

   • Sarwar, S. Mansoor, Sarwar, Syed Aqeel, and Brandeburg, Jesse. Engineering Quicksort. Computer Languages, 22(1), 1996.

   Ασκήσεις

   Άσκηση ADS08

   1. Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο διαβάζει σειρά από ακεραίους μέχρι να συνατήσει την τιμή 0 και με ταξινόμηση διαμερισμού τους τυπώνει με αριθμητική σειρά.

      Παράδειγμα:

      4
      6
      1
      3
      0
      1
      3
      4
      6
      

   Περισσότερες λεπτομέρειες για τις ασκήσεις

   Κατακερματισμός

   Εισαγωγή

   • Ο κατακερματισμός (hashing) είναι μια μέθοδος για τη φύλαξη στοιχείων με βάση ένα κλειδί σε γραμμικές δομές δεδομένων (πίνακες, αρχεία) με στόχο τη γρήγορη ανεύρεσή τους.
   • Βασίζεται στη χρήση μιας συνάρτησης απεικόνισης με πεδίο ορισμού το κλειδί των στοιχείων και πεδίο τιμών τους δείκτες της αντίστοιχης δομής δεδομένων (λ.χ. ακέραιοι δείκτες σε πίνακα ή δείκτες θέσης σε αρχείο).
   • Σε κάθε σύστημα κατακερματισμού πρέπει να λαμβάνουμε μέριμνα για την περίπτωση όπου δύο κλειδιά θα συμπίπτουν στην ίδια θέση της δομής μας.

   Ορισμοί

   Σε ένα σύστημα κατακερματισμού μπορούμε να ορίσουμε τα παρακάτω:
   • Ονομάζουμε πυκνότητα κλειδιών (key density) το λόγο του πληθαρίθμου του συνόλου του πεδίου τιμών προς τον πληθάριθμο του συνόλου του πεδίου ορισμού της συνάρτησης κατακερματισμού.
   • Η διεύθυνση στην οποία απεικονίζει η συνάρτηση κατακερματισμού το κλειδί ονομάζεται βασική διεύθυνση (hash address).
   • Ονομάζουμε συντελεστή φόρτισης (loading factor) το λόγο των στοιχείων της δομής που έχουν καταληφθεί προς τα στοιχεία της δομής που παραμένουν ελεύθερα.
   • Συνώνυμα (Synonyms) είναι δύο κλειδιά για τα οποία η συνάρτηση κατακερματισμού δίνει την ίδια τιμή.
   • Η παραπάνω κατάσταση ονομάζεται σύγκρουση (collision).
   • Υπερχείλιση (Overflow) είναι η διαδικασία που εκτελείται για να υπερβούμε το πρόβλημα που δημιουργεί μια σύγκρουση.
   • Η συνάρτηση κατακερματισμού καλείται ομοιόμορφη (uniform) αν είναι ίσες οι πιθανότητες απεικόνισης κάθε πιθανής τιμής του κλειδιού.
   • Τέλος, η συνάρτηση κατακερματισμού καλείται τέλεια (perfect) αν ο αριθμός των δυνατών κλειδιών ταυτίζεται με τον πληθάριθμο του πεδίου τιμών της συνάρτησης χωρίς τη δημιουργία συγκρούσεων.

   Συναρτήσεις κατακερματισμού

   Η συνάρτηση κατακερματισμού πρέπει να εκτελείται γρήγορα και να είναι κατά το δυνατό ομοιόμορφη. Οι παρακάτω είναι μερικές ενδεικτικές μέθοδοι υλοποίησης:
   • Λογικές μέθοδοι βασισμένες σε συναρτήσεις όπως η αποκλειστική διάζευξη.
   • Πολλαπλασιαστικές μέθοδοι βασισμένες στον πολλαπλασιασμό.
   • Χρήση του υπολοίπου.
   • Χρήση του μέσου του τετραγώνου.
   • Μετατροπή βάσης.
   • Διάσπαση του κλειδιού και πρόσθεση των τμημάτων.
   • Αναδίπλωση των άκρων.
   Οι παραπάνω μέθοδοι μπορούν να χρησιμοποιηθούν και σε συνδυασμό.

   Διαχείριση συγκρούσεων

   Σε περίπτωση που σημειωθεί μια σύγκρουση υπάρχουν οι παρακάτω επιλογές:
   • Απευθείας σύνδεση του στοιχείου που καταλαβάνει τη θέση με το νέο στοιχείο το οποίο φυλάσσεται σε μια άλλη περιοχή.
   • Γραμμική εξέταση: το στοιχείο φυλάσσεται στην πρώτη επόμενη κενή θέση του αρχείου.
   • Δευτεροβάθμια εξέταση: αν η θέση κ είναι γεμάτη το στοιχείο φυλάσσεται σε κάποια θέση (κ+i*i) mod β όπου i = 1 ...

   Βιβλιογραφία

   • Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 208-221 Εκδόσεις Νέων Τεχνολογιών, 1993.

   • Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.

   • Niklaus Wirth. Algorithms + Datastructures = Programs. p. 169-280. Prentice-Hall, 1976.

   Ασκήσεις

   Άσκηση ADS09 (προαιρετική)

   1. Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο διαβάζει 5 ακεραίους και τους αποθηκεύει με κατακερματισμό σε πίνακα 50 θέσεων. Στην συνέχεια ζητάει κατ' εξακολούθηση από το χρήστη να δώσει έναν ακέραιο αριθμό και τυπώνει στην οθόνη αν ο αριθμός αυτός ήταν ανάμεσα στους 5 ή όχι. Το ενδεχόμενο της υπερχείλισης να μην εξεταστεί.

      Παράδειγμα:

      454
      3466
      456
      23
      199
      Give number: 123
      Not known
      Give number: 456
      Known
      

   Περισσότερες λεπτομέρειες για τις ασκήσεις

   Τεχνικές αρχείων

   Εισαγωγή

   • Τα δεδομένα στη βοηθητική μνήμη φυλάσσονται ομαδοποιημένα σε αρχεία (files).
   • Η οργάνωση των αρχείων εξαρτάται από την εφαρμογή που τα δημιουργεί και τα διαβάζει. Τα παρακάτω αποτελούν παραδείγματα περιεχομένου ενός αρχείου:
     • Αδόμητο κείμενο
     • Πηγαίος κώδικας (λ.χ. Pascal)
     • Εκτελέσιμο πρόγραμμα
     • Αρχείο βάσης δεδομένων
     • Αρχείο δεδομένων εφαρμογής (λ.χ. Word, Excel)
   • Αρχεία τα οποία περιέχουν ομοειδή στοιχεία οργανώνονται με βάση τις εγγραφές.
   • Κάθε εγγραφή περιέχει έναν αριθμό από πεδία τα οποία χαρακτηρίζονται από το μήκος τους και τον τύπο των δεδομένων που περιέχουν. Για λόγους ευκολίας αναφερόμαστε στα πεδία με βάση κάποιο όνομα ανάλογα με τα δεδομένα που περιέχουν (π.χ. ΟΝΟΜΑ, ΥΠΟΛΟΙΠΟ).
   • Η διάταξη των πεδίων στην εγγραφή καθώς και το είδος των πεδίων ενός αρχείου καλείται γραμμογράφηση (layout) του αρχείου.

   Βοηθητική μνήμη

   • Βασικές τεχνολογίες βοηθητικής μνήμης είναι:
     • οι μαγνητικές ταινίες,
     • οι μαγνητικοί δίσκοι,
     • οι οπτικοί δίσκοι (CD-ROM, DVD),
     • οι μαγνητο-οπτικοί δίσκοι.
   • Ανάλογα με την τεχνολογία βοηθητικής μνήμης στα δεδομένα των αρχείων μπορούμε να έχουμε σειριακή προσπέλαση (serial access) (λ.χ. μαγνητική ταινία) ή τυχαία προσπέλαση (random access) (λ.χ. μαγνητικός δίσκος).
   • Τα δεδομένα στο μαγνητικό δίσκο είναι οργανωμένα σε κυλίνδρους, (cylinders) αυλάκια (tracks), και τομείς (sectors).
   • Πρόσβαση στα στοιχεία ενός αρχείου γίνεται μέσω μιας ιεραρχίας λογισμικού που μπορεί να περιλαμβάνει:
     • το λογισμικό της εφαρμογής,
     • το ενδιάμεσο λογισμικό (middleware),
     • το λογισμικό της βάσης δεδομένων ή αντίστοιχες βιβλιοθήκες,
     • το λειτουργικό σύστημα και συγκεκριμένα το σύστημα αρχείων,
     • τον οδηγό συσκευής,
     • το λογισμικό ελέγχου της συσκευής (firmware).
   • Σημασία στην υλοποίηση του τρόπου χειρισμού των αρχείων έχει η ταχύτητα των μονάδων βοηθητικής μνήμης. Αυτή είναι της τάξης των ms σε αντιπαράθεση με την ταχύτητα της κύριας μνήμης η οποία είναι της τάξης των δεκάδων ns.

   Επεξεργασία σειριακών αρχείων

   • Εφαρμογές που επεξεργάζονται σειριακά αρχεία (λ.χ. αρχεία που φυλάσσονται σε μαγνητικές ταινίες) είναι δομημένες με βάση διεργασίες που διαβάζουν σειριακά ένα ή περισσότερα αρχεία και παράγουν, σειριακά, νέα αρχεία.
   • Ο όγκος των στοιχείων στις εφαρμογές αυτές φυλάσσεται στο κύριο αρχείο (master file) ενώ οι συναλλαγές κάθε ημέρας ή περιόδου φυλάσσονται στο αρχείο μεταβολών (transaction file)
   • Στα αρχεία αυτά διακρίνουμε τις παρακάτω διεργασίες:
     • Σύζευξη (merge): ένωση δύο σειριακών ταξινομημένων αρχείων σε τρίτο ταξινομημένο.
     • Ταξινόμηση (sort): Ταξινόμηση των εγγραφών του αρχείου με βάση κάποιο κλειδί της εγγραφής. Η ταξινόμηση πραγματοποιείται συνήθως στην κύρια μνήμη. Αν τα δεδομένα δε χωράνε στην κύρια μνήμη ταξινομείται το αρχείο ανά τμήματα τα οποία στη συνέχεια ενώνονται με σύζευξη.
     • Ενημέρωση (update): ενημέρωση του ταξινομημένου κυρίου αρχείου με βάση το αρχείο μεταβολών.
     • Ερώτηση (query) δημιουργία αρχείου που περιέχει τα δεδομένα που ικανοποιούν κάποιο κριτήριο.
     • Αναφορά (report): δημιουργία μιας διαμορφωμένης αναφοράς από τα στοιχεία του αρχείου.

   Αρχεία τυχαίας προσπέλασης

   • Τα αρχεία τυχαίας προσπέλασης είναι συνήθως οργανωμένα σε πίνακες με βάση το σχεσιακό μοντέλο.
   • Τα προγράμματα βάσεων δεδομένων επιτρέπουν την οργάνωση μη προκαθορισμένων στοιχείων σε αρχεία τυχαίας προσπέλασης.
   • Για γρήγορη πρόσβαση στα στοιχεία κάθε πίνακα χρησιμοποιούνται βοηθητικές δομές αναζήτησης με δείκτες στους κυρίους πίνακες.
   • Τέτοιες δομές μπορεί να είναι:
     • ταξινομημένοι πίνακες για στοιχεία που δε μεταβάλλονται,
     • πίνακες κατακερματισμού,
     • δένδρα.
   • Στα αρχεία αυτά υπάρχει συνήθως σύστημα το οποίο οργανώνει τη διάθεση του ελεύθερου χώρου που προέρχεται από διαγραφές.
   • Οι αλλαγές στο κύριο αρχείο γίνονται συνήθως άμεσα. Παράλληλα ενημερώνεται και ένα αρχείο συναλλαγών το οποίο επιτρέπει την ακύρωση συναλλαγών ή την επανεκτέλεσή τους σε παλαιότερο αρχείο συναλλαγών.

   Βιβλιογραφία

   • Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 208-221 Εκδόσεις Νέων Τεχνολογιών, 1993.

   • Peter Pin-Shan Chen. The entity-relationship model --- toward a unified view of data. ACM Transactions on Database Systems, 1(1):9-36, March 1976.

   • Henry F. Korth and Abraham Silberschatz. Database System Concepts. McGraw-Hill, second edition, 1991.

   Θέματα εξετάσεων

   Εργαστήριο αυτοαξιολόγησης

   
   ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ
   

   Τμήμα Μαθηματικών
   

   ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ

   (Εργαστήριο αυτοαξιολόγησης)
   

   Διδάσκων: Διομήδης Σπινέλλης

   15 Απριλίου 1997

   Θέμα 1ο:

   1. Για κάθε ένα από τα παρακάτω είδη πινάκων να γραφεί σε ψευδοκώδικα μια συνάρτηση η οποία δέ÷εται ως όρισμα έναν πίνακα Ν*Ν και να επιστρέφει αληθές η ψευδές ανάλογα με τον αν ο πίνακας ανήκει στο συγκεκριμένο είδος:
      • Συμμετρικός
      • Τριγωνικός
      • Τριδιαγώνιος
      • Αραιός (πλήρης κατά λιγότερο από 10%)

   Θέμα 2ο:

   1. Ορίστε σε Pascal τις διαδικασίες και συναρτήσεις πρόσβασης σε μια στοίβα συμβολοσειρών ως αφηρημένο τύπο (μην τις υλοποιήσετε!)
   2. Με δεδομένες τις παραπάνω να γραφεί πρόγραμμα το οποίο να διαβάζει μια σειρά από λέξεις από το ÷ρήστη μέ÷ρι να συναντήσει τελεία και να τις τυπώνει με ανάποδη σειρά.

   Θέμα 3ο:

   1. Ορίστε μια συνδεδεμένη λίστα ÷αρακτήρων σε Pascal.
   2. Υλοποιήστε συνάρτηση η οποία δέ÷εται ως όρισμα την παραπάνω συνδεδεμένη λίστα και επιστρέφει τον αριθμό των στοι÷είων που την απαρτίζουν.

   Θέμα 4ο:

   1. Ορίστε ένα δυαδικό δένδρο ακεραίων σε Pascal.
   2. Υλοποιήστε συνάρτηση η οποία να δέ÷εται ως όρισμα τον παραπάνω δένδρο και έναν ακέραιο και να επιστρέφει αληθές αν ο ακέραιος αυτός αποτελεί στοι÷είο του δένδρου.
   3. Υπολογίστε πόσους το πολύ κόμβους μπορεί να έ÷ει ένα δένδρο βαθμού d και ύψους h.

   
   

   Διάρκεια εξέτασης 1.5 ώρα.

   Καλή επιτυ÷ία!

   Εξεταστική περιόδος Ιουνίου 1997

   
   ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ
   

   Τμήμα Μαθηματικών
   

   ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ Διδάσκων: Διομήδης Σπινέλλης

   Εξεταστική περίοδος Ιουνίου 1997

   Θέμα 1ο:

   Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της στοίβας λογικών τιμών σύμφωνα με τις παρακάτω συναρτήσεις:

        { Αρχικοποιείται η στοίβα }
             procedure stackInitialize; 
        { Το στοιχείο i εισάγεται στην κορυφή της στοίβας }
             procedure stackPush(i :boolean); 
        { Το στοιχείο από την κορυφή της στοίβας αφαιρείται και επιστρέφεται }
             function stackPop : boolean; 
        { Επιστρέφεται αληθές αν η στοίβα είναι κενή }
             function stackIsEmpty : bool;
   

   Η στοίβα να φυλάσσεται σε πίνακα 2000 θέσεων.

   Θέμα 2ο:

   1. Ορίστε ποιο γράφο ονομάζουμε συνεκτικό και ποιο μη κυκλικό.
   2. Σχεδιάστε γραφικά ένα συνεκτικό, μη κυκλικό γράφο με 8 κόμβους και 7 ακμές.
   3. Ποιες από τις παρακάτω προτάσεις είναι αληθείς για έναν συνεκτικό μη κυκλικό γράφο με ν > 0 κόμβους:
   1. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
   2. Δύο διαφορετικοί κόμβοι συνδέονται από τουλάχιστον μια απλή διαδρομή.
   3. Ο γράφος περιέχει ν + 1 ακμές.
   4. Αν προστεθεί οποιαδήποτε ακμή ο γράφος θα αποκτήσει μια τουλάχιστον κυκλική διαδρομή.
   5. Ο γράφος περιέχει λιγότερες από 2ν ακμές.
   6. Αν προστεθεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
   7. Δύο διαφορετικοί κόμβοι συνδέονται από μια και μόνο μια απλή διαδρομή.
   8. Ο γράφος περιέχει ν - 1 ακμές.
   9. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα αποκτήσει μια τουλάχιστον κυκλική διαδρομή.

   Θέμα 3ο:

   1. Ορίστε μια διπλά συνδεδεμένη λίστα ακεραίων σε Pascal.
   2. Υλοποιήστε συνάρτηση η οποία δέχεται ως όρισμα την παραπάνω διπλά συνδεδεμένη λίστα και ένα ακέραιο αριθμό που υπάρχει στη λίστα και επιστρέφει το μέσο όρο: του αριθμού αυτού, του αριθμού που προηγείται από αυτόν στη λίστα και του αριθμού που τον ακολουθεί. Αν δεν υπάρχει προηγούμενος ή επόμενος αριθμός ο μέσος όρος να υπολογιστεί από τους υπόλοιπους αριθμούς.

   Θέμα 4ο:

   Τα ονόματα των κατόχων και τα αντίστοιχα τηλέφωνα των 5.328.690 συνδέσεων που παρέχει ο ΟΤΕ πρέπει να καταχωρηθούν σε δομή δεδομένων που να επιτρέπει την ταχύτερη δυνατή εύρεση του τηλεφώνου με βάση το όνομα. Ποια δομή δεδομένων θα χρησιμοποιήσετε; Ποια δομή δεδομένων θα χρησιμοποιήσετε αν επιπλέον απαιτείται η άμεση ταξινομημένη ανάκτηση των ονομάτων για την εκτύπωση των τηλεφωνικών καταλόγων.
   

   Διάρκεια εξέτασης 2 ώρες

   Καλή επιτυχία!

   Εξεταστική περιόδος Σεπτεμβρίου 1997

   
   ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ
   

   Τμήμα Μαθηματικών
   

   ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ Διδάσκων: Διομήδης Σπινέλλης

   Εξεταστική περίοδος Σεπτεμβρίου 1997

   Θέμα 1ο:

   Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της συνδεδεμένης λίστας χαρακτήρων σύμφωνα με τις παρακάτω συναρτήσεις:

        { Ορισμός του τύπου της συνδεδεμένης λίστας }
             type
                 charList = ...
        { Επιστρέφεται μια άδεια συνδεδεμένη λίστα }
             function newCharList : charList; 
        { Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο c στην αρχή της }
             function addCharList(l : charList; c : char) : charList; 
        { Επιστρέφεται μια συνδεδεμένη λίστα με το πρώτο στοιχείο διαγραμμένο. Κατά
           την επιστροφή η μεταβλητή c περιέχει την τιμή του. }
             function delCharListHead(l : charList; var c : char) : charList; 
        { Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή c }
             function searchCharList(l : charList; c : char) : charList; 
        { Επιστρέφεται αληθές αν η λίστα είναι κενή }
             function isEmtyCharList(l : charList) : boolean;
   

   Θέμα 2ο:

   1. Τι ονομάζουμε βαθμό και τι ύψος ενός δένδρου;
   2. Πότε ένα δένδρο καλείται πλήρες;
   3. Αποδείξτε τις παρακάτω προτάσεις. Στην απόδειξη μπορεί να σας φανεί χρήσιμη η μέθοδος της επαγωγής.
   1. Ένα πλήρες δένδρο βαθμού d και ύψους h θα έχει κόμβους.
   2. Ένα πλήρες δυαδικό δένδρο ύψους h θα έχει κόμβους.
   3. Ένα πλήρες δυαδικό δένδρο με n κόμβους θα έχει ύψος.

   Θέμα 3ο:

   1. Περιγράψτε με πληρότητα έναν αποδοτικό τρόπο ταξινόμησης αρχείου του οποίου τα στοιχεία δε χωράνε στην κεντρική μνήμη.
   2. Περιγράψτε περιληπτικά δομές αναζήτησης που μπορούν να χρησιμοποιηθούν για γρήγορη πρόσβαση στα στοιχεία ενός αρχείου που φυλάσσεται σε βοηθητική μνήμη.

   Θέμα 4ο:

   1. Περιγράψτε με ψευδοκώδικα τη διαδικασία της δυαδικής αναζήτησης για την εύρεση μιας εγγραφής σε ταξινομημένο πίνακα.
   2. Αν ο πίνακας έχει Ν στοιχεία δώστε τον ελάχιστο και το μέγιστο αριθμό συγκρίσεων που μπορεί να απαιτηθούν για την παραπάνω διαδικασία αναζήτησης.

   .

   Διάρκεια εξέτασης 2.5 ώρες

   Καλή επιτυχία!

   • Περιεχόμενα

    Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:30 μμ
    Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».