Γενικά
| Διδάσκουσα: | Παναγιώτα Φατούρου |
| Γραφείο: | 215 (Λευκά Κτίρια Α´ όροφος) |
| Ώρες Γραφείου: | Τρίτη: 14:00-15:00, Πέμπτη: 14:00 – 15:00 |
| Ηλεκτρονική Διεύθυνση: |  |
| Τηλέφωνο: | +30 2810 393549 |
| Βοηθοί Μαθήματος: | Γεωργαλής Γιάννης, Δρόσης Γιάννης, Ζωγραφιστού Δήμητρα, Καζέπης Νικόλας, Παπαθανασίου Βαγγέλης, Παρταράκης Νίκος, Πέτσας Θανάσης. |
| Γραφείο Βοηθών: | Εργαστήριο Μεταπτυχιακών, Υπόγειο Λευκών Κτιρίων |
| Ώρες Γραφείου Βοηθών: | Δευτέρα, 19:00-20:00 |
| Ηλεκτρονική Διεύθυνση Μαθήματος: |  |
Ώρες και Αίθουσες Διδασκαλίας
Τρίτη, 15:00-17:00, στην αίθουσα Λ202. Πέμπτη, 15:00-17:00, στην αίθουσα Λ202.Ώρες και Αίθουσα Φροντιστηρίου-Εργαστηρίου
Παρασκευή, 15:00-17:00, στην αίθουσα Λ202.Σύνοψη Μαθήματος
Το μάθημα θα εστιάσει στη μελέτη βασικών δομών δεδομένων, όπως π.χ. πινάκων, στοιβών, ουρών, λιστών, δένδρων κλπ., καθώς και πιο πολύπλοκων δομών δεδομένων, όπως ισοζυγισμένων δένδρων, γράφων, κ.α. Επίσης, θα μελετηθεί η τεχνική του κατακερματισμού, καθώς και δομές δεδομένων για την υλοποίηση δυναμικών ευρετηρίων, απλών συνόλων και συνόλων με ειδικές λειτουργίες. Θα διδαχθούν επιλεγμένα θέματα σε ταξινόμηση και βασικές τεχνικές σχεδίασης αλγορίθμων.
Βιβλία
Το μάθημα θα βασιστεί σε περισσότερα από ένα βιβλία (και κυρίως στα ξενόγλωσσα βιβλία που αναφέρονται στην παρακάτω λίστα). Οποιοδήποτε από τα παρακάτω βιβλία καλύπτει το σημαντικότερο μέρος της ύλης που θα διδαχθεί. Για την επιτυχή διεκπεραίωση του μαθήματος, οι φοιτητές θα πρέπει να βασιστούν κυρίως στις διαφάνειες του μαθήματος, καθώς και σε οποιοδήποτε άλλο υλικό μοιρασθεί κατά τη διάρκεια αυτού.
- Harry Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins Publishers, Inc., New York, 1991.
- Μιchael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons, Inc., (4th edition).
- Michael T. Goodrich, Roberto Tamassia, and David M. Mount, Data Structures and Algorithms in C++, John Wiley & Sons, Inc.
- Παναγιώτης Μποζάνης, Δομές δεδομένων, 960-418-010-Χ, Τζιόλας, 2003.
- Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press, 1990. (Το βιβλίο κυκλοφορεί μεταφρασμένο από τις Πανεπιστημιακές Εκδόσεις Κρήτης σε δύο μέρη.)
- Sahni, Δομές Δεδομένων, Αλγόριθμοι και Εφαρμογές στη C++, Μετάφραση: Γιάννης Θεοδωρίδης & Γιάννης Μανωλόπουλος, Εκδόσεις Τζιόλα, 2004.
- Γεώργιος Φ. Γεωργακόπουλος, Δομές Δεδομένων: Έννοιες, Τεχνικές, Αλγόριθμοι, Πανεπιστημιακές Εκδόσεις Κρήτης, Ηράκλειο 2002.
- Ι. Μανωλόπουλος, Δομές Δεδομένων, Μια προσέγγιση με Pascal, Εκδόσεις Art of Text, Θεσσαλονίκη.
Πρόγραμμα
| Εβδομάδα | Θέμα |
|---|---|
| 1η | Εισαγωγή - Βασικές έννοιες αλγορίθμων και δομών δεδομένων |
| 2η | Χρονικές Πολυπλοκότητες - Επιμερισμένο Κόστος, Απλά παραδείγματα αναδρομικών σχέσεων - Πίνακες |
| 3η | Βασικές Δομές Δεδομένων: Λίστες, Στοίβες, Ουρές |
| 4η | Λίστες |
| 5η | Δένδρα |
| 6η | Δένδρα |
| 7η | Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών |
| 8η | Κατακερματισμός |
| 9η | Κατακερματισμός - Σύνολα που υποστηρίζουν ειδικές λειτουργίες |
| 10η | Ουρές Προτεραιότητας - Γράφοι |
| 11η | Γράφοι |
| 12η | Ταξινόμηση |
| 13η | Τεχνικές Σχεδίασης Αλγορίθμων |
Εργασίες και Βαθμολόγηση
Κατά τη διάρκεια του εξαμήνου θα δοθούν πέντε σειρές θεωρητικών ασκήσεων και μια προγραμματιστική εργασία. Κάθε άσκηση θα πρέπει να επιστρέφεται πριν από την αναγραφόμενη ημερομηνία και ώρα προκειμένου να μπορεί να βαθμολογηθεί με άριστα. Αν η παράδοση της άσκησης γίνει μέχρι και τρία 24ωρα μετά την προθεσμία, η εργασία βαθμολογείται με μείωση βαθμού κατά 1.0/10.0 μονάδα για κάθε μέρα καθυστέρησης. Πολύ καλές ασκήσεις μπορεί να βαθμολογηθούν με βαθμό μεγαλύτερο του 10.
Η προγραμματιστική εργασία θα είναι χωρισμένη σε τρία μέρη με διαφορετική ημερομηνία παράδοσης το καθένα. Το κάθε μέρος θα πρέπει να παραδοθεί πριν από την αναγραφόμενη ημερομηνία και ώρα. Για τη βαθμολόγηση μερών της εργασίας που παραδίδονται καθυστερημένα ισχύει ο αλγόριθμος που περιγράφεται παραπάνω για τις θεωρητικές ασκήσεις. Για τα μέρη της προγραμματιστικής εργασίας θα υπάρχει προφορική εξέταση. Κατά τη διάρκεια της προφορικής εξέτασης, οι φοιτητές θα λαμβάνουν σχόλια βάσει των οποίων θα μπορούν να βελτιώνουν το συγκεκριμένο μέρος της εργασίας τους (δηλαδή κάθε φοιτητής έχει δικαίωμα να βελτιώσει οποιοδήποτε μέρος της εργασίας του μετά την λήξη της προθεσμίας παράδοσης αυτού και να συμπεριλάβει τη βελτιωμένη έκδοση στο επόμενο μέρος της εργασίας). Ο βαθμός των διαφόρων μερών της εργασίας θα αποφασιστεί μετά την παράδοση και του τελευταίου μέρους (και θα ληφθούν υπόψη για κάθε μέρος και οι βελτιώσεις που έχουν γίνει εκ των υστέρων). Ο βαθμός κάθε μέρους θα καθοριστεί ως εξής:
30% * Β1 + 70% * Β2, όπου Β1 είναι ο βαθμός με τον οποίο βαθμολογήθηκε ένα μέρος κατά την προφορική του εξέταση και Β2 είναι ο βαθμός με τον οποίο βαθμολογήθηκε το ίδιο μέρος της εργασίας μετά τις όποιες βελτιώσεις παραδόθηκαν με την τελική παράδοση της εργασίας).
Προσοχή: Για το τελευταίο μέρος της εργασίας δεν υπάρχει η δυνατότητα βελτιστοποίησης του κώδικα και επανεξέτασης.
Ο προγραμματισμός, όπως και η έκθεση, είναι μια ιδιαίτερη ατομική εργασία. Κάθε φοιτητής πρέπει ατομικά να κατανοήσει το πρόβλημα και να σκιαγραφήσει μια πιθανή λύση του (αν και μπορεί να ρωτάει τη διδάσκουσα και τους βοηθούς του μαθήματος για τις απορίες του ή για προβλήματα στη μετάφραση του κώδικά του). Είναι επίσης σημαντικό ο κώδικάς του να είναι ευανάγνωστος. Η βαθμολογία στα προγράμματα θα αντικατοπτρίζει την πληρότητα και την ορθότητα, αλλά και τα συνοδεύοντα σχόλια. Οι αντιγραφές και οι στενές συνεργασίες απαγορεύονται αυστηρά και θα τιμωρούνται με μείωση ή μηδένιση βαθμού. Είναι καλύτερα να παραδοθεί μια ημιτελής άσκηση παρά μια παραλλαγμένη αντιγραφή. Οι φοιτητές μπορούν ωστόσο να απασχολούν τους βοηθούς του μαθήματος και τη διδάσκουσα στις ώρες γραφείου τους για τις απορίες τους.
Οι φοιτητές μπορούν να χρησιμοποιήσουν οποιονδήποτε υπολογιστή για τα προγραμματιστικά τους καθήκοντα. Για τη βαθμολόγηση των εργασιών τους όμως, το πρόγραμμα θα δοκιμάζεται στα μηχανήματα κάποιου εργαστηρίου του Τμήματος. Σε αυτούς τους σταθμούς εργασίας εκτελείται το λειτουργικό σύστημα unix. Επομένως, όσοι από τους φοιτητές επιθυμούν να εργαστούν σε άλλα μηχανήματα θα πρέπει να σιγουρευτούν ότι ο κώδικας τους τρέχει σωστά και στα παραπάνω μηχανήματα.
Οι φοιτητές είναι υπεύθυνοι για την κακή χρήση του λογαριασμού τους. Το password τους θα πρέπει να παραμείνει μυστικό και ο λογαριασμός τους να χρησιμοποιείται μόνο από αυτούς. Θα πρέπει τέλος να φροντίζουν η προστασία του καταλόγου στον οποίο βρίσκονται τα προγράμματά τους να μην επιτρέπει ανάγνωση (ή εγγραφή) από άλλους (η εντολή chmod είναι πολύ χρήσιμη).
Στην τελική εξέταση επιτρέπεται στους φοιτητές να έχουν μαζί τους το βιβλίο και τις διαφάνειες του μαθήματος (δεμένες ως ένα ενιαίο πακέτο με θερμοκόλληση). Άλλου είδους χαρτιά και σημειώσεις απαγορεύονται. Επίσης, στην τελική εξέταση απαγορεύεται η χρήση κινητού τηλεφώνου και θα πρέπει όλοι οι εξεταζόμενοι φοιτητές να έχουν μαζί τους το πάσο ή την ταυτότητα ή το δίπλωμα οδήγησης ή το διαβατήριο τους ή οποιοδήποτε άλλο αναγνωριστικό.
Ο τελικός βαθμός θα εξαρτηθεί τόσο από τη βαθμολογία των ασκήσεων και των εργασιών, όσο και από την επίδοση των φοιτητών στην τελική εξέταση, ως εξής:
Σειρές Ασκήσεων: 15%
Εργασία: 20%
Τελική Εξέταση: 65%
Βάσει των παραπάνω ο τελικός βαθμός ενός φοιτητή υπολογίζεται ως εξής:
Τελικός Βαθμός = 0.15 * ΜΟΘΑ + 0.20 * ΤΒΠΕ + 0.65 * ΒΤΓ όπου
- ΜΟΘΑ: Μέσος Όρος Θεωρητικών Ασκήσεων
- ΤΒΠΕ: Τελικός Βαθμός Προγραμματιστικής Εργασίας
- ΒΓTE: Βαθμός Γραπτού στην Τελική Εξέταση
Αν ένας φοιτητής βαθμολογηθεί με βαθμό χαμηλότερο του 4 στην τελική εξέταση αποτυγχάνει στο μάθημα ανεξάρτητα από το πόσο καλές είναι οι ασκήσεις που έχει παραδώσει.
Ο ίδιος αλγόριθμος για την διεξαγωγή της βαθμολογίας ισχύει και στην εξέταση του Σεπτεμβρίου.
Τρόπος Παράδοσης Ασκήσεων: Η παράδοση των θεωρητικών ασκήσεων γίνεται στο βοηθό του μαθήματος που θα βρίσκεται στο εργαστήριο των μεταπτυχιακών στο υπόγειο των λευκών κτιρίων, την ημέρα της παράδοσης και ώρα 19:00-20:00. Ασκήσεις που παραδίδονται μετά τις 20:00 θεωρούνται εκπρόθεσμες. Οι φοιτητές μπορούν να παραδίδουν τις ασκήσεις τους και νωρίτερα από αυτή την ημερομηνία στους βοηθούς ή τη διδάσκουσα του μαθήματος. Όσοι από τους φοιτητές δεν έχουν καταφέρει να παραδώσουν τις ασκήσεις τους πριν από την προθεσμία παράδοσης θα πρέπει να τις παραδώσουν στο βοηθό που θα βρίσκεται στο εργαστήριο των μεταπτυχιακών την προκαθορισμένη μέρα και ώρα. Οι φοιτητές μπορούν να παραδίδουν τις ασκήσεις τους ηλεκτρονικά χρησιμοποιώντας το πρόγραμμα submit αλλά σε αυτή την περίπτωση απαιτείται να γίνουν scan οι λύσεις. Αυτός είναι ο τρόπος παράδοσης εκπρόθεσμων ασκήσεων. Το μάθημα δεν χρησιμοποιεί κουτιά για την παράδοση ασκήσεων αφού αυτό δεν εγγυάται την ασφάλεια των ασκήσεων των φοιτητών. Επομένως, οι ασκήσεις που θα βρεθούν σε οποιοδήποτε κουτί δεν θα γίνονται δεκτές από τους βοηθούς του μαθήματος και τη διδάσκουσα. Αν δεν υπάρχει κάποιος βοηθός στο γραφείο των μεταπτυχιακών στο υπόγειο των λευκών κτιρίων την προκαθορισμένη μέρα και ώρα, αναφέρουμε το γεγονός αυτό στη λίστα και περιμένουμε οδηγίες από τη διδάσκουσα ή από κάποιο βοηθό για τον τρόπο παράδοσης.
Η παράδοση των προγραμματιστικών ασκήσεων γίνεται μόνο μέσω του προγράμματος submit.
Λίστα Ηλεκτρονικού Ταχυδρομείου & Λογαριασμός Μαθήματος
Για το μάθημα υπάρχει e-mailing λίστα η οποία θα χρησιμοποιείται για την αποστολή ηλεκτρονικών μηνυμάτων σε όλους τους φοιτητές που έχουν δηλώσει το μάθημα. Για την εγγραφή στη λίστα απαιτείται η αποστολή ενός ηλεκτρονικού μηνύματος (e-mail) στη διεύθυνση:
με κενό θέμα και σώμα:
Η εγγραφή στη λίστα είναι υποχρεωτική. Όποιος φοιτητής δεν εγγραφεί στη λίστα, δεν θα λαμβάνει τα e-mails που αποστέλλονται και δεν θα γνωρίζει σημαντικά θέματα που αφορούν το μάθημα. Το e-mail address της λίστας είναι:
Όλα τα e-mails προς αυτή τη διεύθυνση θα λαμβάνονται από όλους τους φοιτητές που έχουν εγγραφεί στη λίστα. Οι φοιτητές υποχρεούνται να εξετάζουν καθημερινά το e-mail τους ώστε να ενημερώνονται έγκαιρα για τα μηνύματα που αποστέλλονται στη λίστα. Οι φοιτητές υποχρεούνται να εγγραφούν στη λίστα μέχρι τις 10/10.
Για το μάθημα υπάρχει επίσης λογαριασμός στον οποίο οι φοιτητές μπορούν να στέλνουν ηλεκτρονικά μηνύματα με τις απορίες τους. Η ηλεκτρονική διεύθυνση του λογαριασμού είναι:
Παρακολούθηση
Η παρακολούθηση στις διαλέξεις συνίσταται ισχυρά, αλλά δεν είναι υποχρεωτική. Οι φοιτητές θα πρέπει να γνωρίζουν κατά την τελική εξέταση οτιδήποτε παρουσιάζεται ή αναφέρεται στις παραδόσεις. Κάποιο ποσοστό της ύλης δεν περιέχεται στην ελληνική βιβλιογραφία ή παρουσιάζεται με άλλη σειρά, για αυτό η παρακολούθηση συνίσταται ισχυρά.
Προαπαιτούμενα
Τα μαθήματα που είναι προαπαιτούμενα για τη δήλωση του μαθήματος ΗΥ240 είναι το ΗΥ-100: Εισαγωγή στην Επιστήμη Υπολογιστών και το ΗΥ-150: Προγραμματισμός. Είναι επίσης καλό οι φοιτητές να έχουν διεκπεραιώσει επιτυχώς το μάθημα ΗΥ-118: Διακριτά Μαθηματικά. Οι φοιτητές που δεν έχουν διεκπεραιώσει επιτυχώς τα μαθήματα αυτά δεν έχουν το υπόβαθρο που απαιτείται για να επιτύχουν στο μάθημα.
Άλλη σχετική βιβλιογραφία
- K. Mehlhorn and S. Näher, “LEDA”, Cambridge University Press, 1999.
- C. J. Van Wyk, “Data Structures and C Programs”, Addison-Wesley Publishing Company, 1988.
- Mark Allen Weiss, Data Structures & Algorithm Analysis in Java, Addison-Wesley, 1999, 0-201-35754-2
- William Collins, Data Structures and the Java Collections Framework, 2nd ed., McGraw-Hill, 2005, ISBN: 0-07-282379-8.
- Leendert Ammeraal, «Προγραμματισμός και Δομές Δεδομένων στη C», Μ. Γκιούρδας, 1989.
- Niklaus Wirth, «Αλγόριθμοι & Δομές Δεδομένων», Κλειδάριθμος, 1990.
- Gregory Rawlins, Αλγόριθμοι: Ανάλυση και Σύγκριση, Κριτική, 2004, 960-218-350-0 (στην πρώτυπη αγγλική έκδοση: Compared to What, Computer Science Press, 1992, ISBN: 0-7167-8243-X).
- Anany Levitin, Εισαγωγή στην Ανάλυση & Σχεδίαση Αλγορίθμων, 978-960-418-143-8, Τζιόλας, 2008 (στην πρώτυπη αγγλική έκδοση: The Design & Analysis of Algorithms, 2nd ed, Pearson, 2007).
- Robert Sedgewick, Algoritmhs in Java, 3rd ed, Addison-Wesley, 2003, ISBN: 0-201-36120-5, Volume A: Fundamentals, Data Structures, Sorting, Searching