Η/Υ 432: Δομές Δεδομένων - Υποχρεωτικό μάθημα 3^ου εξαμήνου  

Χειμερινό Εξάμηνο Ακ. Έτους 2005-2006

Τμήμα Πληροφορικής

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

Για το τελικό διαγώνισμα

Για όσους διαβάζουν αγγλικά, από το βιβλίο Lewis & Dennenberg θα πρέπει να διαβαστούν οι ακόλουθες ενότητες:

Chapter 1
1.1
1.2: όλη η ενότητα εκτός από Locatives
1.3: σελ. 17 - 29 (όχι αποδείξεις θεωρημάτων)

Chapter 2
2.1

Chapter 3
Όλο το κεφαλαίο εκτός από Ενότητα 3.3 και σελίδες 89-90 (καθώς και η μισή σελίδα 88).

Chapter 4
Όλο το κεφάλαιο εκτός από την ενότητα "Scanning a Tree in Constant Space"

Chapter 5
Μόνο ενότητα 5.4

Chapter 6
6.1
6.2: όχι η ανάλυση που ξεκινά από το τέλος της σελίδας 179 και καταλήγει προς το τέλος της σελίδας180.
6.3: Μόνο Binary Search & Skip Lists (χωρίς αποδείξεις θεωρημάτων)
6.4 (όχι αποδείξεις θεωρημάτων)

Chapter 7
7.1
7.2: 2-3 Trees
7.3 (όχι αποδείξεις θεωρημάτων)

Chapter 8
8.3
8.4
8.5 (όχι αποδείξεις θεωρημάτων)

Chapter 9
9.1 (όχι Leftist Trees)
9.2 (όχι αποδείξεις θεωρημάτων)

Chapter 12
12.1 (όχι Trees)

 

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

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

Βοηθοί Μαθήματος:                                  Καλλιμάνης Νικόλαος & Καλογήρου Χάρης & Χριστοδουλίδου Μαρία
Γραφείο Βοηθών:                                      Α25
Ώρες Γραφείου Βοηθών:                          Πέμπτη, 15:00-17:00, Παρασκευή, 12:00-14:00
Ηλεκτρονική Διεύθυνση Μαθήματος:      

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

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

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

Τρίτη, 12:00-14:00 (θα πραγματοποιείται περιστασιακά). 

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

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

Βιβλία

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

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

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

Πρόγραμμα

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

Κατά τη διάρκεια του εξαμήνου θα δοθούν 3 εργασίες. Κάθε εργασία θα έχει ένα σύνολο από θεωρητικές ασκήσεις και ένα προαιρετικό προγραμματιστικό μέρος. Ο προγραμματισμός θα γίνει σε γλώσσα C. Κάθε εργασία θα πρέπει να επιστρέφεται πριν από την αναγραφόμενη ημερομηνία και ώρα (προκειμένου να μπορεί να βαθμολογηθεί με άριστα). Το θεωρητικό μέρος μπορεί να παραδοθεί με καθυστέρηση τριών 24ώρων με μείωση βαθμού κατά 1.0/10.0 μονάδα για κάθε μέρα καθυστέρησης.

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

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

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

Όλες οι ασκήσεις θα πρέπει να έχουν παραδοθεί πριν από την εξέταση ή την επίλυσή τους. Για τις ασκήσεις ενδεχόμενα να υπάρχει γραπτή εξέταση. Πολύ καλές ασκήσεις μπορεί να βαθμολογηθούν με βαθμό μεγαλύτερο του 10.

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

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

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

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

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

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

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

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

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

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

Παρατήρηση

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

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

•   Sahni, Δομές Δεδομένων, Αλγόριθμοι και Εφαρμογές στη C++, Μετάφραση: Γιάννης Θεοδωρίδης & Γιάννης Μανωλόπουλος, Εκδόσεις Τζιόλα, 2004.

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

• 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.

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

  To 3ο Σετ Ασκήσεων είναι έτοιμο (ds-homework3.pdf). Ημερομηνία παράδοσης του 1ου Μέρους: Τρίτη, 20 Δεκεμβρίου 2005, ώρα 12:00 (στους βοηθούς του μαθήματος, γραφείο Α25). Ημερομηνία παράδοσης του 2ου Μέρους: Τρίτη, 10 Ιανουαρίου 2005, ώρα 12:00 (στους βοηθούς του μαθήματος, γραφείο Α25). Ημερομηνία παράδοσης προγραμματιστικού μέρους: Πέμπτη, 22 Δεκεμβρίου 2005.

• To 2ο Σετ Ασκήσεων είναι έτοιμο (ds-homework2.pdf). Ημερομηνία παράδοσης του 1ου Μέρους: Τετάρτη, 30 Νοεμβρίου 2005, ώρα 12:00 (στους βοηθούς του μαθήματος, γραφείο Α25). Ημερομηνία παράδοσης του 2ου Μέρους: Παρασκευή, 9 Δεκεμβρίου 2005, ώρα 12:00 (στους βοηθούς του μαθήματος, γραφείο Α25).

• To 1ο Σετ Ασκήσεων είναι έτοιμο (ds-homework1.doc). Ημερομηνία παράδοσης του 1ου Μέρους: Πέμπτη, 10/11, ώρα 15:00 (στους βοηθούς του μαθήματος, γραφείο Α25). Ημερομηνία παράδοσης του 2ου Μέρους: Δευτέρα, 21/11, ώρα 12:00.

• Διαφάνειες Ενότητας 3 (ds-section3.pdf)

• Διαφάνειες Ενότητας 1 και 2 (ds-sections1-2.pdf)

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

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

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

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

 

Όποιος φοιτητής δεν εγγραφεί στη λίστα, δεν θα λαμβάνει τα e-mails που αποστέλονται και δεν θα γνωρίζει σημαντικά θέματα που αφορούν το μάθημα. Το e-mail address της λίστας είναι . Όλα τα e-mails προς αυτή τη διεύθυνση θα λαμβάνονται από όλους τους φοιτητές που έχουν εγγραφεί στη λίστα.

• Γενικές Πληροφορίες για το μάθημα (syllabus.doc).

Ημερολόγιο

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

  3ο Σετ Ασκήσεων (ds-homework3.pdf)

• 2ο Σετ Ασκήσεων (ds-homework2.pdf)

• 1ο Σετ Ασκήσεων (ds-homework1.doc)

• Διαφάνειες Ενότητας 4 (ds-section4.pdf)

• Διαφάνειες Ενότητας 3 (ds-section3.pdf)

• Διαφάνειες Ενότητας 1 και 2 (ds-sections1-2.pdf)

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

• Γενικές Πληροφορίες για το μάθημα (syllabus.doc).

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