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

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Καλώς ήρθατε

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

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

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

Εισαγωγή - Πίνακες
Στοίβες
Ουρές
Λίστες
Δένδρα
Β-Δένδρα
Γράφοι
Αναζήτηση
Κατακερματισμός
Ταξινόμηση
Τεχνικές αρχείων
Ανασκόπηση - επανάληψη

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

Δε θα μοιράζονται
Βασίζονται στο βιβλίο Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. Εκδόσεις Νέων Τεχνολογιών, 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.

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

Οι αφηρημένοι τύποι δεδομένων (abstract data types) μας επιτρέπουν να διαχωρίσουμε τον τύπο των δεδομένων από την υλοποίησή του.

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

Πίνακες

Οι πίνακες (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;

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

Πρόσβαση στα στοιχεία πίνακα μιας διάστασης:
```
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

Σε ένα σύστημα εξισώσεων μπορούμε να πραγματοποιήσουμε τις παρακάτω πράξεις χωρίς μεταβολή της λύσης:

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

Με τη χρήση των παραπάνω μπορούμε να επιλύσουμε συστήματα εξισώσεων με τη μέθοδο Μηδενισμού κατά Gauss (Gaussian Elimination).

Παράδειγμα

( 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

Να γραφεί πρόγραμμα σε Pascal το οποίο να λύνει το παρακάτω σύστημα εξισώσεων με τη μέθοδο του μηδενισμού κατά Gauss.
```
( 1  3 -4 ) (x1)   ( 8)
( 1  1 -2 ) (x2) = ( 2)
(-1 -2  5 ) (x3)   (-1)
```
Το πρόγραμμα μπορεί να χωριστεί σε τρεις διαδικασίες:
- Assign: Εκχώρηση στον πίνακα των τιμών.
- Eliminate: Τριγωνισμός του πίνακα με μηδενισμό.
- Substitute: Αντικατάσταση τιμών και εκτύπωση των λύσεων.

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

Περιεχόμενα