Τμήμα Πληροφορικής, Φθινόπωρο 2001

Η/Υ 4-32: Δομές Δεδομένων

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


Εξέταση 3ης Προγραμματιστικής Άσκησης

Την Τρίτη 9/01/02 θα γίνει η εξέταση της 3ης προγραμματιστικής άσκησης. Θα πραγματοποιηθεί στο εργαστήριο unix στον 1ο όροφο.  Η εξέταση είναι υποχρεωτική για όλους. Ασκήσεις που δεν θα εξεταστούν προφορικά (λόγω απουσίας του φοιτητή) θα μηδενίζονται. Η εξέταση δεν θα επαναληφθεί και μόνο αυτοί με αποδεικτέα σοβαρό λόγο θα εξεταστούν μετά από αυτή την ημερομηνία. Σε αυτή την περίπτωση ο φοιτητής θα πρέπει να με ενημερώσει πριν από την εξέταση. Όλοι οι φοιτητές που θα εξεταστούν θα πρέπει να δηλώσουν τη μέρα και ώρα εξέτασής τους στον πίνακα που έχει αναρτηθεί έξω από το γραφείο μου.


Εξέταση 2ης Προγραμματιστικής Άσκησης

Μετά από ανακοίνωση της Πρυτανείας για την μη πραγματοποίηση μαθημάτων σήμερα Τρίτη 18/12, η προγραμματισμένη εξέταση της 2ης προγραμματιστικής άσκησης μεταφέρεται για την Τρίτη 8/01/02. Η εξέταση των φοιτητών θα γίνει με τη σειρά που αυτοί έχουν ήδη δηλώσει στον πίνακα που έχει αναρτηθεί έξω από το γραφείο μου. Όσοι φοιτητές δεν μπορέσουν να έρθουν στην εξέταση θα πρέπει να με ενημερώσουν πριν την εξέταση, διαφορετικά η άσκηση τους θα μηδενιστεί.


 

5η Προγραμματιστική Άσκηση

Την 5η Προγραμματιστική άσκηση θα πρέπει να κάνουν (1) όσοι δεν έχουν ποτέ παραδώσει κάτι που να τρέχει, ή (2) όσοι δεν έχουν παραδώσει καμία προγραμματιστική άσκηση αλλά παρ΄ όλα αυτά θα ήθελαν να περάσουν το μάθημα φέτος, ή (3) όσοι έχουν παραδώσει κάτι που τρέχει σε κάποια από τις σειρές αλλά αυτό έπιανε μόνο ένα μικρό ποσοστό του συνολικού βαθμού της άσκησης (π.χ., είχαν κάνει μόνο μερικά (ή ένα) ερώτημα τα οποία δεν έπιαναν συνολικό βαθμό πάνω από 50. Οι φοιτητές αυτοί θα πρέπει να πάρουν την εκφώνηση της 5ης προγραμματιστικής άσκησης από το φάκελο που έχει αναρτηθεί έξω από το γραφείο μου (ή να την κατεβάσουν από την ιστοσελίδα). Η προθεσμία παράδοσης για την 5η Άσκηση είναι ίδια με εκείνη του 4ου Σετ, δηλαδή Τετάρτη 9/1/02, ώρα 12:59. 


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


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

Διδάσκων:                                               Παναγιώτα Φατούρου
Γραφείο:                                                  26 (Α´ ορόφου)
Ώρες Γραφείου:                                       Τρίτη: 15:00 – 17:00, Τετάρτη: 15:00-17:00
Ηλεκτρονική Διεύθυνση:                        
Τηλέφωνο:                                               (0651) 98808
Βοηθός Μαθήματος:                                Στέλιος Μαστρογιαννάκης (smastrog ΑΤ cs.uoi.gr)
Γραφείο Βοηθού:                                      Β5
Ηλεκτρονική Διεύθυνση Μαθήματος:    

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

Δευτέρα, 15:00-17:00, στην αίθουσα Ι-2.
Τετάρτη, 15:00-17:00, στην αίθουσα Ι-2.

 

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

Πέμπτη, 18:00-20:00, στην αίθουσα Ι-2

 

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

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

 

Βιβλία

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

q       Ιωάννης Μανωλόπουλος, «Δομές Δεδομένων: Μια Προσέγγιση με την Pascal», Εκδόσεις Art of Text, Θεσσαλονίκη.

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

 

Πρόγραμμα

1η εβδομάδα

Εισαγωγή, Ανάλυση Αλγορίθμων
Δείκτες & Δυναμική Αποθήκευση στη
C, Πίνακες

2η εβδομάδα

Λίστες

3η εβδομάδα

Δένδρα

4η εβδομάδα

Λίστες & Δένδρα: Υλοποίηση Συνόλων  

5η εβδομάδα

Λίστες & Δένδρα: Υλοποίηση Συνόλων

6η εβδομάδα

Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών  

7η εβδομάδα

Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών

8η εβδομάδα

Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών

9η εβδομάδα

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

10η εβδομάδα

Κατακερματισμός, Σύνολα που υποστηρίζουν ειδικές λειτουργίες

11η εβδομάδα

Σύνολα που υποστηρίζουν ειδικές λειτουργίες, Γράφοι

12η εβδομάδα

Γράφοι

 

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

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

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

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

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

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

Σειρές Ασκήσεων: 40%
Τελική Εξέταση: 60%

Προκειμένου ένας φοιτητής να περάσει το μάθημα πρέπει να γράψει τουλάχιστον 5 στο τελικό διαγώνισμα, ανεξάρτητα από το πόσο καλές είναι οι ασκήσεις που έχει παραδώσει.

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

 

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

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

 

Παρατήρηση

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

 

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

 


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

Την Τρίτη 9/01/02 θα γίνει η εξέταση της 3ης προγραμματιστικής άσκησης. Θα πραγματοποιηθεί στο εργαστήριο unix στον 1ο όροφο.  Η εξέταση είναι υποχρεωτική για όλους. Ασκήσεις που δεν θα εξεταστούν προφορικά (λόγω απουσίας του φοιτητή) θα μηδενίζονται. Η εξέταση δεν θα επαναληφθεί και μόνο αυτοί με αποδεικτέα σοβαρό λόγο θα εξεταστούν μετά από αυτή την ημερομηνία. Σε αυτή την περίπτωση ο φοιτητής θα πρέπει να με ενημερώσει πριν από την εξέταση. Όλοι οι φοιτητές που θα εξεταστούν θα πρέπει να δηλώσουν τη μέρα και ώρα εξέτασής τους στον πίνακα που έχει αναρτηθεί έξω από το γραφείο μου.
Την 5η Προγραμματιστική άσκηση θα πρέπει να κάνουν (1) όσοι δεν έχουν ποτέ παραδώσει κάτι που να τρέχει, ή (2) όσοι δεν έχουν παραδώσει καμία προγραμματιστική άσκηση αλλά παρ΄ όλα αυτά θα ήθελαν να περάσουν το μάθημα φέτος, ή (3) όσοι έχουν παραδώσει κάτι που τρέχει σε κάποια από τις σειρές αλλά αυτό έπιανε μόνο ένα μικρό ποσοστό του συνολικού βαθμού της άσκησης (π.χ., είχαν κάνει μόνο μερικά (ή ένα) ερώτημα τα οποία δεν έπιαναν συνολικό βαθμό πάνω από 50. Οι φοιτητές αυτοί θα πρέπει να πάρουν την εκφώνηση της 5ης προγραμματιστικής άσκησης από το φάκελο που έχει αναρτηθεί έξω από το γραφείο μου. Η προθεσμία παράδοσης για την 5η Άσκηση είναι ίδια με εκείνη του 4ου Σετ, δηλαδή Τετάρτη 9/1/02, ώρα 12:59.

Μετά από ανακοίνωση της Πρυτανείας για την μη πραγματοποίηση μαθημάτων σήμερα Τρίτη 18/12, η προγραμματισμένη εξέταση της 2ης προγραμματιστικής άσκησης μεταφέρεται για την Τρίτη 8/01/02. Η εξέταση των φοιτητών θα γίνει με τη σειρά που αυτοί έχουν ήδη δηλώσει στον πίνακα που έχει αναρτηθεί έξω από το γραφείο μου. Όσοι φοιτητές δεν μπορέσουν να έρθουν στην εξέταση θα πρέπει να με ενημερώσουν πριν την εξέταση, διαφορετικά η άσκηση τους θα μηδενιστεί.
Η 5η Προγραμματιστική άσκηση είναι διαθέσιμη.
Η άσκηση 7 στο 4ο Σετ Ασκήσεων είναι προαιρετική.

 


Ημερολόγιο

Δευτέρα Τρίτη Τετάρτη Πέμπτη Παρασκευή
1/10

 

2/10

 

3/10

 

4/10

 

5/10

 

8/10

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

 

9/10

 

 

 

10/10

Μελέτη Διαφανειών & κεφ. 2, Μανωλόπουλου (παρ. 2.5 όχι)
Επανάληψη στη C 

 

11/10

Μελέτη διαφανειών και Παρ. 3.1, 3.2, 3.3 του κεφ. 3, Μανωλόπουλου
Μπορείτε να δουλεύετε με τις θεωρητικές ασκήσεις 1-6 του 1ου Σετ.

12/10

 

 

15/10


Μελέτη διαφανειών και Παρ. 3.4: 3.4.1, 3.4.2, 3.4.3, 3.4.4, 3.5: 3.5.1 του κεφ. 3, Μανωλόπουλου
Έχει καλυφθεί η ύλη για όλες τις ασκήσεις του 1ου Σετ.

16/10

 

 

 

 

17/10

 Μελέτη διαφανειών και ασκήσεων. 

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

 

18/10

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

 

 

 

19/10

 

 

 

 

22/10

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

 

 

23/10

 

 

 

24/10

Μελέτη διαφανειών και Παρ.  4.1, 4.2, 4.3, κεφ. 4, Μανωλόπουλου (όχι σελ. 115 - 118)

25/10

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

 

 

26/10

 

 

 

29/10

Μελέτη Διαφανειών και Παρ. 3.4.5, Μανωλόπουλου

 

30/10

 

 

 

31/10

Μελέτη Διαφανειών και Παρ. 4.4, Μανωλόπουλου.

 

1/11

 

 

 

2/11

 

 

 

5/11

Μελέτη διαφανειών και Παρ. 5.2, Μανωλόπουλου.
 Η ύλη για τη λύση του 2ου Σετ Ασκήσεων έχει καλυφθεί.

6/11

 

 

 

7/11

 Μελέτη διαφανειών: ΑVL δένδρα

 

 

8/11

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

 

 

9/11

 

 

 

12/11

 

 

 

13/11

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

 

 

14/11

Μελέτη Διαφανειών: 2-3 δένδρα και Κόκκινα-Μαύρα Δένδρα

 

15/11

Μελέτη Διαφανειών: 
(a,b) -Δένδρα

 

 

16/11

 

 

 

19/11

Μελέτη Διαφανειών: Splay Δένδρα 

 

 

 

20/11

 

 

 

 

 

21/11

Μελέτη Διαφανειών: Splay Δένδρα (amortized κόστος λειτουργιών)

Η ύλη για τη λύση του 3ου Σετ ασκήσεων έχει καλυφθεί.

 

22/11

 

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

 

 

 

23/11

 

 

 

 

 

26/11

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

Μελέτη Παραγράφων 9.1, 9.3.2 και 9.3.3, κεφ. 9, Μανωλόπουλου

 

27/11

 

 

 

 

28/11

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

Μελέτη Παραγράφων 9.3.1, 9.4, κεφ. 9, Μανωλόπουλου

 

29/11

 

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

 

 

30/11

 

 

 

 

3/12

Μελέτη Διαφανειών: Hashing (Extendible Hashing, Perfect Hashing, Hashing Functions, Universal Hashing)

Μελέτη Παραγράφων 9.2 και 9.5, Μανωλόπουλου

 

 

4/12


 

 

 

 

 

5/12

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

Σύνολα με ειδικές λειτουργίες, Ουρές Προτεραιότητας, Σοροί, Ξένα Σύνολα με Ένωση (Disjoint Sets with Union, Δομές Union-Find)

Μελέτη κεφ. 6, Μανωλόπουλου

 

6/12

 

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


 

 

 

7/12

 

 

 

 

 

 

10/12

 Μελέτη Διαφανειών: Γράφοι

Μελέτη Παραγράφων 7.1, 7.4, Μανωλόπουλου


 

 

 

11/12


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

 

 

 

 

 

 

12/12

Μελέτη Διαφανειών: Μέθοδοι διάσχισης Γράφων

Κωδικοποίηση Αλφαριθμητικών (Strings)

Μελέτη Παραγράφων 7.5.1-7.5.2, Μανωλόπουλου

 

 

13/12

 

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

 


 

 

 

14/12

 

 

 


 

 

 

17/12

 

18/12

 

19/12

 

20/12

 

21/12

 

 


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

5η Προγραμματιστική Άσκηση (homework5.ps)
4ο Σετ Ασκήσεων (homework4.ps)

 


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