Γενικά

Διδάσκουσα: Παναγιώτα Φατούρου
Γραφείο: 215 (Λευκά Κτίρια Α´ όροφος)
Ώρες Γραφείου: Πέμπτη, 16:00-17:00
Ηλεκτρονική Διεύθυνση: rg.cou.dsc@urutaf
Τηλέφωνο: +30 2810 393549
Βοηθοί Μαθήματος: Καζέπης Νικόλαος, Μπιρλιράκη Χρυσή, Παλιούρας Κων/νος, Τζομπανάκη Αικατερίνη, Κατωπόδης Αλέξανδρος, Παπαδάκης Εμμανουήλ, Φραγκιαδάκη Γεωργία
Γραφείο Βοηθών: Εργαστήριο Μεταπτυχιακών, Υπόγειο Λευκών Κτιρίων
Ώρες Γραφείου Βοηθών: Δευτέρα, 12:00
Ηλεκτρονική Διεύθυνση Μαθήματος: rg.cou.dsc@a042yh

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

Τρίτη, 11:00 - 13:00, αίθουσα Λ202.

Πέμπτη, 11:00 - 13:00, αίθουσα Λ202.

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

Παρασκευή, 11:00 - 13:00, αίθουσα Λ202.

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

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

Μαθησιακοί Στόχοι

Περιεχόμενα Μαθήματος

Πρόγραμμα

Εβδομάδα Θέμα
1η Εισαγωγή - Βασικές έννοιες αλγορίθμων και δομών δεδομένων
2η Χρονικές Πολυπλοκότητες - Επιμερισμένο Κόστος, Απλά παραδείγματα αναδρομικών σχέσεων - Πίνακες
3η Βασικές Δομές Δεδομένων: Λίστες, Στοίβες, Ουρές
4η Λίστες
5η Δένδρα
6η Δένδρα
7η Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών
8η Κατακερματισμός
9η Κατακερματισμός - Σύνολα που υποστηρίζουν ειδικές λειτουργίες
10η Ουρές Προτεραιότητας - Γράφοι
11η Γράφοι
12η Ταξινόμηση
13η Τεχνικές Σχεδίασης Αλγορίθμων

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

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

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

20% * Β1 + 80% * Β2, όπου Β1 είναι ο βαθμός με τον οποίο βαθμολογήθηκε ένα μέρος κατά την προφορική του εξέταση και Β2 είναι ο βαθμός με τον οποίο βαθμολογήθηκε το ίδιο μέρος της εργασίας μετά τις όποιες βελτιώσεις παραδόθηκαν με την τελική παράδοση της εργασίας).

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

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

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

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

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

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


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

Βάσει των παραπάνω ο τελικός βαθμός ενός φοιτητή υπολογίζεται ως εξής:

Τελικός Βαθμός = 0.20 * ΜΟΘΑ + 0.20 * ΤΒΠΕ + 0.60 * ΒΤΓ όπου

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

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

Τρόπος Παράδοσης Ασκήσεων: Η παράδοση των θεωρητικών ασκήσεων γίνεται στο βοηθό του μαθήματος που θα βρίσκεται στο εργαστήριο των μεταπτυχιακών στο υπόγειο των λευκών κτιρίων, την ημέρα της παράδοσης και ώρα 12:00 - 13:00. Ασκήσεις που παραδίδονται μετά τις 20:00 θεωρούνται εκπρόθεσμες. Οι φοιτητές μπορούν να παραδίδουν τις ασκήσεις τους και νωρίτερα από αυτή την ημερομηνία στους βοηθούς ή τη διδάσκουσα του μαθήματος. Όσοι από τους φοιτητές δεν έχουν καταφέρει να παραδώσουν τις ασκήσεις τους πριν από την προθεσμία παράδοσης θα πρέπει να τις παραδώσουν στο βοηθό που θα βρίσκεται στο εργαστήριο των μεταπτυχιακών την προκαθορισμένη μέρα και ώρα. Οι φοιτητές μπορούν να παραδίδουν τις ασκήσεις τους ηλεκτρονικά χρησιμοποιώντας το πρόγραμμα submit αλλά σε αυτή την περίπτωση απαιτείται να γίνουν scan οι λύσεις. Αυτός είναι ο τρόπος παράδοσης εκπρόθεσμων ασκήσεων. Το μάθημα δεν χρησιμοποιεί κουτιά για την παράδοση ασκήσεων αφού αυτό δεν εγγυάται την ασφάλεια των ασκήσεων των φοιτητών. Επομένως, οι ασκήσεις που θα βρεθούν σε οποιοδήποτε κουτί δεν θα γίνονται δεκτές από τους βοηθούς του μαθήματος και τη διδάσκουσα. Αν δεν υπάρχει κάποιος βοηθός στο γραφείο των μεταπτυχιακών στο υπόγειο των λευκών κτιρίων την προκαθορισμένη μέρα και ώρα, αναφέρουμε το γεγονός αυτό στη λίστα και περιμένουμε οδηγίες από τη διδάσκουσα ή από κάποιο βοηθό για τον τρόπο παράδοσης.

Πρόγραμμα submit

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

Αναλυτικά, για κάθε άσκηση ή μέρος της προγραμματιστικής εργασίας, οι εντολές submit που θα πρέπει να χρησιμοποιηθούν είναι:

Για τις σειρές ασκήσεων 1 μέχρι 4, αντίστοιχα οι εξής:

Για το κάθε μέρος της προγραμματιστικής εργασίας αντίστοιχα, οι παρακάτω:


όπου <dir> είναι ο φάκελος όπου βρίσκονται τα αρχεία που πρέπει να παραδωθούν. Επειδή το πρόγραμμα submit δεν καταχωρεί συμπιεσμένα αρχεία, τα αρχεία προς παράδοση δεν πρέπει να είναι binary/compressed/gzipped.

Περισσότερες πληροφορίες για το πρόγραμμα submit βρίσκονται και στο http://www.csd.uoc.gr/index.jsp?tID=services⊂=info.

Επίσης αναλυτικότερες οδηγίες υπάρχουν εδώ.

Λίστα Ηλεκτρονικού Ταχυδρομείου & Λογαριασμός Μαθήματος

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

rg.cou.dsc@omodrojam

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

tsil-a042yh ebircsbus

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

rg.cou.dsc@tsil-a042yh

Όλα τα e-mails προς αυτή τη διεύθυνση θα λαμβάνονται από όλους τους φοιτητές που έχουν εγγραφεί στη λίστα. Οι φοιτητές υποχρεούνται να εξετάζουν καθημερινά το e-mail τους ώστε να ενημερώνονται έγκαιρα για τα μηνύματα που αποστέλλονται στη λίστα. Οι φοιτητές υποχρεούνται να εγγραφούν στη λίστα μέχρι τις 25/2.

Για το μάθημα υπάρχει επίσης λογαριασμός στον οποίο οι φοιτητές μπορούν να στέλνουν ηλεκτρονικά μηνύματα με τις απορίες τους. Η ηλεκτρονική διεύθυνση του λογαριασμού είναι:

rg.cou.dsc@a042yh

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

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

Προαπαιτούμενα

Τα μαθήματα που είναι προαπαιτούμενα για τη δήλωση του μαθήματος ΗΥ240 είναι το ΗΥ-100: Εισαγωγή στην Επιστήμη Υπολογιστών και το ΗΥ-150: Προγραμματισμός. Είναι επίσης καλό οι φοιτητές να έχουν διεκπεραιώσει επιτυχώς το μάθημα ΗΥ-118: Διακριτά Μαθηματικά. Οι φοιτητές που δεν έχουν διεκπεραιώσει επιτυχώς τα μαθήματα αυτά δεν έχουν το υπόβαθρο που απαιτείται για να επιτύχουν στο μάθημα.

Βιβλία

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

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

Σελίδες προηγούμενων εξαμήνων