Τμήμα Πληροφορικής, Χειμερινό Εξάμηνο 2003

Η/Υ 432: Δομές Δεδομένων

Υποχρεωτικό μάθημα 3^ου εξαμήνου

Γενικά | Ανακοινώσεις | Ημερολόγιο | Διαφάνειες Διαλέξεων & Άλλο Υλικό

Η συνολική βαθμολογία των ασκήσεων για τους φοιτητές που δεν έγραψαν βαθμό >=40 στο γραπτό του Ιανουαρίου μπορεί να προσπελασθεί εδώ (σας έχει σταλεί και e-mail μέσω της λίστας).

Γενικές Πληροφορίες

Διδάσκουσα:                                           Παναγιώτα Φατούρου
Γραφείο:                                                  26 (Α´ ορόφου)
Ώρες Γραφείου:                                      Δευτέρα: 19:00-20:00, Πέμπτη: 13:00 – 15:00
Ηλεκτρονική Διεύθυνση:
Τηλέφωνο:                                               (26510) 98808

Βοηθοί Μαθήματος:                                 Νικόλαος Τσάπανος & Παναγιώτης Παπαπέτρου
Γραφείο Βοηθών:                                      Α25
Ώρες Γραφείου Βοηθών:                          Τετάρτη 1-3 & Παρασκευή 5-7.
Ηλεκτρονική Διεύθυνση Μαθήματος:

Ώρες και Αίθουσες Διδασκαλίας

Δευτέρα, 17:00-19:00, στο αμφιθέατρο.
Τετάρτη, 17:00-19:00, στο αμφιθέατρο.

Ώρες και Αίθουσα Φροντιστηρίου

Πέμπτη, 12:00-14:00, στην αίθουσα Ι-2 ή στο εργαστήριο UNIX του 1ου ορόφου.

Σύνοψη Μαθήματος

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

Βιβλία

q Harry Lewis and Larry Denenberg, “Data Structures and Their Algorithms”, HarperCollins Publishers, Inc., New York, 1991.

q Γεώργιος Φ. Γεωργακόπουλος, Δομές Δεδομένων: Έννοιες, Τεχνικές, Αλγόριθμοι, Πανεπιστημιακές Εκδόσεις Κρήτης, Ηράκλειο 2002.

Το βιβλίο που θα μοιραστεί στους φοιτητές είναι το 2^ο από τα παραπάνω. Ωστόσο, το μάθημα θα βασιστεί σε μεγάλο βαθμό στο 1^ο βιβλίο της παραπάνω λίστας. Οι διαφάνειες του μαθήματος μαζί με τις σημειώσεις που μπορούν οι φοιτητές να κρατάνε κατά την παράδοση και οποιοδήποτε άλλο υλικό θα μοιρασθεί θα είναι αρκετά για να διεκπεραιώσουν οι φοιτητές επιτυχώς το μάθημα.

Πρόγραμμα

1^η εβδομάδα	Εισαγωγή, Ανάλυση Αλγορίθμων Δείκτες & Δυναμική Αποθήκευση στη C, Πίνακες
2^η εβδομάδα	Λίστες
3^η εβδομάδα	Δένδρα
4^η εβδομάδα	Λίστες & Δένδρα: Υλοποίηση Συνόλων
5^η εβδομάδα	Λίστες & Δένδρα: Υλοποίηση Συνόλων
6^η εβδομάδα	Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών
7^η εβδομάδα	Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών
8^η εβδομάδα	Κατακερματισμός
9^η εβδομάδα	Κατακερματισμός, Σύνολα που υποστηρίζουν ειδικές λειτουργίες
10^η εβδομάδα	Σύνολα που υποστηρίζουν ειδικές λειτουργίες, Αλφαριθμητικά

Εργασίες και Βαθμολόγηση

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

Το προγραμματιστικό μέρος μπορεί να παραδοθεί καθυστερημένα βάσει του εξής αλγόριθμου:

§ Αν η παράδοση της άσκησης γίνει μέχρι και τρία 24ωρα μετά την προθεσμία, η άσκηση βαθμολογείται με μείωση βαθμού κατά 1.0/10.0 μονάδα για κάθε μέρα καθυστέρησης.

§ Αν η παράδοση της άσκησης γίνει αφού έχουν περάσει τρία 24ωρα μετά τη λήξη της προθεσμίας (και φυσικά πριν την εξέταση της άσκησης), η άσκηση βαθμολογείται με άριστα το 5.0/10.0.

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

Μπορείτε να χρησιμοποιήσετε οποιονδήποτε υπολογιστή για τις προγραμματιστικές ασκήσεις σας. Για τη βαθμολόγηση της άσκησής σας όμως, το πρόγραμμα θα εκτελείται στα μηχανήματα κάποιου εργαστηρίου του Τμήματος. Επομένως, όσοι από εσάς επιθυμούν να εργαστούν σε άλλα μηχανήματα θα πρέπει να σιγουρευτούν ότι ο κώδικας τους τρέχει σωστά και στα παραπάνω μηχανήματα.

Είστε υπεύθυνοι για την κακή χρήση του λογαριασμού σας. Το password σας θα πρέπει να παραμείνει μυστικό και ο λογαριασμός σας να χρησιμοποιείται μόνο από εσάς. Φροντίστε η προστασία του καταλόγου στον οποίο βρίσκονται τα προγράμματά σας να μην επιτρέπει ανάγνωση (ή ακόμη χειρότερα εγγραφή) από άλλους (χρησιμοποιήστε την εντολή chmod).

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

Ο τελικός βαθμός θα εξαρτηθεί τόσο από τη βαθμολογία των ασκήσεων, όσο και από την επίδοση των φοιτητών στην τελική εξέταση, ως εξής:

Σειρές Ασκήσεων: 30%

Τελική Εξέταση: 70%

Προκειμένου να περάσετε με επιτυχία το μάθημα θα πρέπει να γράψετε τουλάχιστον 4.0/10.0 στην τελική εξέταση και να έχετε βαθμό τουλάχιστον 3.5/10.0 στις ασκήσεις σας (συνολικά για το θεωρητικό και το προγραμματιστικό μέρος).

Ο ίδιος αλγόριθμος για την διεξαγωγή της βαθμολογίας ισχύει και στην εξέταση του Σεπτεμβρίου. Φοιτητές που αποτυγχάνουν στο μάθημα και στις δύο εξεταστικές (Ιανουαρίου & Σεπτεμβρίου) πρέπει να παρακολουθήσουν το μάθημα και να κάνουν όλες τις εργασίες εξ αρχής τον επόμενο χρόνο (εργασίες δεν κατοχυρώνονται).

Παρακολούθηση

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

Παρατήρηση

Θα βοηθήσει πολύ αν οι φοιτητές έχουν διεκπεραιώσει με επιτυχία τα μαθήματα της «Εισαγωγής στον Προγραμματισμό» και της «Εισαγωγής στους Η/Υ». H καλή γνώση της γλώσσας Προγραμματισμού C είναι απαραίτητη.

Άλλη σχετική βιβλιογραφία

Ιωάννης Μανωλόπουλος, «Δομές Δεδομένων: Μια Προσέγγιση με την Pascal», Εκδόσεις Art of Text, Θεσσαλονίκη.
Leendert Ammeraal, «Προγραμματισμός και Δομές Δεδομένων στη C», Μ. Γκιούρδας, 1989.
Cormen, Leiserson and Rivest, “Introduction to Algorithms”, MIT Press, 1990.
K. Mehlhorn and S. Näher, “LEDA”, Cambridge University Press, 1999.
Niklaus Wirth, «Αλγόριθμοι & Δομές Δεδομένων», Κλειδάριθμος, 1990.
C. J. Van Wyk, “Data Structures and C Programs”, Addison-Wesley Publishing Company, 1988.
Ομάδα Waite, C: Βήμα-Προς-Βήμα, Εκδότης Γκιούρδας, Αθήνα 1991.
B. Kernighan & D. Ritchie, Η Γλώσσα Προγραμματισμού C, Εκδόσεις Κλειδάριθμος, Αθήνα 1990.

Ανακοινώσεις

H τρίτη άσκηση έχει μοιραστεί και μπορείτε να την πάρετε από το φάκελο που έχει αναρτηθεί στην πόρτα του γραφείου μου. Επίσης, είναι διαθέσιμη μέσω αυτής της ιστοσελίδας (δείτε Ενότητα Διαφάνειες Διαλέξεων και άλλο Υλικό).

H δεύτερη άσκηση έχει μοιραστεί και μπορείτε να την πάρετε από το φάκελο που έχει αναρτηθεί στην πόρτα του γραφείου μου. Επίσης, είναι διαθέσιμη μέσω αυτής της ιστοσελίδας (δείτε Ενότητα Διαφάνειες Διαλέξεων και άλλο Υλικό).
Την Πέμπτη 11/12, ώρα 12-2, θα γίνει μάθημα.
Όσοι είχαν γραφτεί στη λίστα του μαθήματος τον προηγούμενο χρόνο θα πρέπει να ξαναγραφτούν και φέτος (και θα πρέπει να το κάνουν ξανά μέσα σε αυτή την εβδομάδα ακόμη και αν το έχουν ήδη κάνει στην αρχή του μαθήματος). Όλοι οι παλιοί διαγράφτηκαν πρόσφατα από τη λίστα (άρα όλοι οι παλιοί θα πρέπει να ξαναγραφτούν).
Την Πέμπτη 20/11 δεν θα γίνει εργαστήριο ή φροντιστήριο.
Η πρώτη άσκηση έχει μοιραστεί και μπορείτε να την πάρετε από τους φακέλους που έχουν αναρτηθεί στην πόρτα του γραφείου μου. Επίσης, είναι διαθέσιμη μέσω αυτής της ιστοσελίδας (δείτε Ενότητα Διαφάνειες Διαλέξεων και άλλο Υλικό).
Οι διαφάνειες των διαλέξεων έχουν έρθει από το τυπογραφείο και μοιράζονται από την κ. Σουλίου.
Έναρξη μαθημάτων

Το πρώτο μάθημα θα γίνει τη Δευτέρα, 3/11/03 στο αμφιθέατρο του Τμήματος.

E-mailing Λίστα Μαθήματος

Για το μάθημα θα υπάρχει e-mail λίστα η οποία θα χρησιμοποιείται για την αποστολή e-mail σε όλους τους φοιτητές που έχουν δηλώσει το μάθημα. Οι φοιτητές υποχρεούνται να εγγραφούν στη λίστα. Όποιος φοιτητής δεν εγγραφεί στη λίστα, θα διαγράφεται αυτόματα από το μάθημα.

Οι φοιτητές θα πρέπει να εγγραφούν στη λίστα το αργότερο μέχρι τις 15/11/03. Για να εγγραφείτε στη λίστα αρκεί να στείλετε ένα ηλεκτρονικό μήνυμα (e-mail) στη διεύθυνση

με κενό θέμα και σώμα:

Ημερολόγιο

Δευτέρα

Τρίτη

Τετάρτη

Πέμπτη

Παρασκευή

3/11

Syllabus. Εισαγωγή.

Μελέτη διαφανειών & κεφ. 1, Γεωργακόπουλου (επιλεκτικά). Εισαγωγή.
Επανάληψη στη C

Το βάρος πρέπει να δοθεί στην επανάληψη της C.

4/11

5/11

Πίνακες, Εισαγωγή σε Λίστες. Μελέτη διαφανειών.

Το βάρος πρέπει να δοθεί σε επανάληψη της C.

6/11

7/11

10/11

Μελέτη διαφανειών. Σειριακές Στοίβες, Σειριακές Ουρές. Μελέτη διαφανειών.

11/11

12/11

Συνδεδεμένες Στοίβες, Συνδεδεμένες Ουρές. Μελέτη διαφανειών.

13/11

14/11

17/11

Αργία Πολυτεχνείου

18/11

19/11

Μελέτη διαφανειών. Λίστες, Ταξινομημένες Λίστες. Διασχίσεις, Διασχίσεις Zig-Zag.

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

Βάρος στην επίλυση των θεωρητικών ασκήσεων του 1ου σετ.

Η ύλη για την επίλυση όλων των θεωρητικών ασκήσεων έχει καλυφθεί.

20/11

Εργαστηριακή Απασχόληση.

21/11

24/11

Μελέτη Διαφανειών. Διπλά Συνδεδεμένες Λίστες, Δένδρα - Διασχίσεις. Υλοποιήσεις Διασχίσεων Δένδρων.

Βάρος στην επίλυση των θεωρητικών ασκήσεων του 1ου σετ.

25/11

Extra δίωρο

Μελέτη Διαφανειών. Δένδρα, Είδη Δένδρων, Υλοποίηση Δένδρων.

Λήξη προθεσμίας θεωρητικού μέρους 1ης σειράς

26/11

Μελέτη Διαφανειών.

Δένδρα - Υλοποίηση Διασχίσεων Δένδρων - Νηματικά Δένδρα.- Διάσχιση κατά επίπεδα.

27/11

28/11

1/12

Μελέτη Διαφανειών.
Σύνολα - Λεξικά - Υλοποίηση με λίστες - Ευριστικά

2/12

3/12

Μελέτη Διαφανειών. Λίστες Παράλειψης.

4/12

Φροντιστηριακή Απασχόληση

5/12

8/12

Μελέτη Διαφανειών. Ταξινομημένα Δυαδικά Δένδρα

Λήξη προθεσμίας προγραμματιστικού μέρους 1ης σειράς.

9/12

Extra Ώρα

Μελέτη Διαφανειών. AVL Δένδρα.

10/12

Μελέτη Διαφανειών. AVL Δένδρα

11/12

Extra Δίωρο

Μελέτη Διαφανειών. (2,3)-Δένδρα

12/12

15/12

16/12

17/12

Λήξη Προθεσμίας Θεωρητικού Μέρους 2ης Σειράς Ασκήσεων

18/12

Φροντιστηριακή Απασχόληση

19/12

22/12

23/12

24/12

25/12

26/12

5/1

6/1

7/1

8/1

Λήξη Προθεσμίας Προγραμματιστικού Μέρους 2ης Σειράς Ασκήσεων

9/1

12/1

Red-Black Trees & (a,b)-trees - Μελέτη διαφανειών

13/1

14/1

Splay trees - Μελέτη Διαφανειών

15/1

16/1

19/1

Το βάρος πρέπει να δοθεί στη 3η Σειρά Ασκήσεων.

20/1

21/1

22/1

23/1

26/1

27/1

28/1

29/1

Λήξη Προθεσμίας Θεωρητικού Μέρους 3ης Σειράς

30/1

Λήξη Προθεσμίας Προγραμματιστικού Μέρους 3ης Σειράς

Διαφάνειες Διαλέξεων & Άλλο Υλικό

3ο Σετ Ασκήσεων

Προγραμματιστικό Μέρος 2ου Σετ Ασκήσεων
Θεωρητικό Μέρος 2ου Σετ Ασκήσεων.
Πρώτο Σετ Ασκήσεων.
Οι διαφάνειες των διαλέξεων έχουν δοθεί στο τυπογραφείο του Πανεπιστημίου και θα διανεμηθούν δωρεάν στους φοιτητές όταν θα είναι έτοιμες. Η ηλεκτρονική έκδοση των διαφανειών είναι επίσης διαθέσιμη (ps, pdf).

Τελευταία τροποποίηση: 16/1/04
Κατασκευή και συντήρηση των σελίδων: Παναγιώτα Φατούρου