Γενικές Πληροφορίες
Ώρες Διαλέξεων & Ασκήσεων
| Ημέρα |
Ώρα |
Αίθουσα |
| Δευτέρα |
11:00-13:00 |
A212 |
| Τετάρτη |
11:00-13:00 |
Α212 |
| Παρασκευή |
11:00-13:00 |
Β212 |
Διδάσκων
Μενέλαος
Καραβέλας
Γραφείο: Δ306
Τηλέφωνο: 2810 393 706
email: mkaravel at uoc gr
Ώρες Γραφείου: Δε/Τε 13:00-13:30
Βοηθός Διδασκαλίας
Iordan Iordanov
Γραφείο: Δ317
email: i.m.iordanov at gmail com
Ώρες Γραφείου: Δε 10:00-11:00 / Πα 13:00-14:00
Περιεχόμενο Μαθήματος
Βασικές έννοιες σχεδιασμού και ανάλυσης αλγορίθμων και
αλγοριθμικής πολυπλοκότητας. Αλγοριθμικές τεχνικές. Αλγόριθμοι
ταξινόμησης, εύρεσης και επιλογής. Δυναμικός
προγραμματισμός. Άπληστοι αλγόριθμοι. Στοιχειώδεις αλγόριθμοι
γραφημάτων. Αλγόριθμοι ελαχίστων επικαλυπτόντων δέντρων και
ελαχίστων μονοπατίων.
Επιλογή θεμάτων από τις εξής κατηγορίες
αλγορίθμων: Αλγόριθμοι ροής σε
δίκτυα. Αλγόριθμοι υπολογιστικής γεωμετρίας, θεωρίας πινάκων,
θεωρία αριθμών και συνδυαστικής.
Mailing list μαθήματος
Η mailing list του μαθήματος είναι η:
em202-list@tem.uoc.gr
Στη λίστα θα στέλνονται πληροφορίες και ανακοινώσεις σχετικά με το
μάθημα και θα απαντούνται ερωτήσεις σχετικά με δικά σας
ερωτήματα.
Προκειμένου να λαμβάνετε τα μηνύματα της λίστας αλλά και να
μπορείτε να στείλετε μηνύματα σε αυτή στείλτε email στην διεύθυνση
majordomo@tem.uoc.gr στο body του οποίου πρέπει
να γράψετε τη φράση
subscribe em202-list
Ανακοινώσεις
Σε αντίστροφη χρονολογική σειρά.
| Ημερομηνία |
Ανακοίνωση |
|
27 Oct 2014
|
Η πρόοδος του μαθήματος θα γίνει τη Δευτέρα 1η Δεκ 2014 την ώρα του μαθήματος.
Για την πρόοδο ισχύει ότι και για κάθε εξέταση του μαθήματος. Δείτε
λεπτομέρειες εδώ. Η ύλη της προόδου θα ανακοινωθεί
περί τα μέσα Νοεμβρίου.
|
|
03 Oct 2014
|
Στις διαλέξεις του μαθήματος θα ακολουθηθεί (χωρίς αυτό να είναι
δεσμευτικό με οποιόποτε τρόπο και για οποιοδήποτε λόγο), το βιβλίο
«Εισαγωγή στους Αλγορίθμους», των T. Cormen, C. Leiserson,
R. Rivest και C. Stein (μετάφραση της 2ης αγγλόφωνης έκδοσης από
τον Ι. Παπαδόγγονα).
Η ύλη που θα διδαχθεί από το βιβλίο αυτό αναφέρεται στα παρακάτω
χωρία του βιβλίου:
- Μέρος I: Κεφάλαια 1-4, και μερικώς το 5
- Μέρος II: Κεφάλαια 6-9
- Μέρος III: Κεφάλαιο 10 (θα συζητηθούν εν συντομία)
- Μέρος IV: Κεφάλαια 15-17 (μερικώς)
- Μέρος VI: Κεφάλαια 22-25
Χρόνου επιτρέποντος θα διδαχθεί και επιπλέον ύλη, στην οποία περίπτωση
θα ανακοινωθούν και τα αντίστοιχα χωρία του βιβλίου.
|
|
24 Σεπ 2014
|
Το μάθημα της Δευτέρας 24 Σεπ 2014 αναβάλλεται. Θα υπάρξει
νέα ανακοίνωση για την αναπλήρωσή του.
|
Ημερολόγιο
Σε χρονολογική σειρά.
| Ημερομηνία |
Περιεχόμενο Μαθήματος |
|
22 Σεπ 2014
|
Γενική εισαγωγή στο μάθημα. Περιεχόμενα μαθήματος.
|
|
01 Oct 2014
|
Εισαγωγή στις έννοιες της σχεδίασης και χρονικής/χωρικής ανάλυσης
αλγορίθμου. Η εισαγωγή έγινε με τη βοήθεια του προβλήματος εύρεσης
του ελαχίστου στοιχείου ενός συνόλου. Παρουσιάστηκε τόσο επαναληπτικός
όσο και αναδρομικός αλγόριθμος. Με αφορμή τον δεύτερο έγινε εισαγωγή
στην έννοια των αναδρομικών σχέσεων που προκύπτουν κατά την ανάλυση
αλγορίθμων.
|
|
06 Oct 2014
|
Σχετικός ρυθμός αύξησης συναρτήσεων. Η ανάγκη σύγκρισης συναρτήσεων
στα πλαίσια της ανάλυσης αλγορίθμων. Ορισμός του Ο-, Ω- και Θ-συμβολισμού.
Παραδείγματα χρήσης των ορισμών. Εξήγηση των συμβολισμών ως σύνολα.
Βασικές ιδιότητες των ασυμπτωτικών συμβολισμών:
- f(n) = O(g(n)) συνεπάγεται g(n)=Ω(f(n))
- f(n) = O(g(n)) και f(n)=Ω(g(n)) ισοδυναμεί με f(n)=Θ(g(n))
- f1(n) = Ο(g1(n)) και f2(n)=O(g2(n)) συνεπάγεται f1(n)+f2(n)=O(g1(n)+g2(n))
- f1(n) = Ο(g1(n)) και f2(n)=O(g2(n)) συνεπάγεται f1(n)*f2(n)=O(g1(n)*g2(n))
- f(n) = Ο(g(n)) και c θετική σταθερά συνεπάγεται c*f(n)=O(g(n)) (χωρίς απόδειξη)
- f(n) = Ο(g(n)) και c σταθερά συνεπάγεται f(n)+c=O(g(n)) (χωρίς απόδειξη), υπό την προϋπόθεση
ότι το όριο της f(n), καθώς το n τείνει στο άπειρο, είναι το άπειρο. Αντιπαράδειγμα
στο οποίο φαίνεται ότι η ιδιότητα δεν ισχύει γενικά.
|
|
08 Oct 2014
|
Ορισμός του o-συμβολισμού. Συσχέτιση του συμβολισμού f=o(g) με το όριο του λόγου f(n)/g(n)
καθώς το n τείνει στο άπειρο. Παραδείγματα και ιδιότητες του o-συμβολισμού.
Το ασυμβίβαστο των o- και O-συμβολισμών.
|
|
13 Oct 2014
|
Ορισμός του ω-συμβολισμού. Συσχέτιση του συμβολισμού f=ω(g) με το όριο του λόγου f(n)/g(n)
καθώς το n τείνει στο άπειρο. Παραδείγματα και ιδιότητες του ω-συμβολισμού.
Το ασυμβίβαστο των ω- και Ω-συμβολισμών.
Συμμετοχή στην εκδήλωση για την αναγόρευση του Edmund M. Clarke σε Επίτιμο Διδάκτορα του ΤΕΥ.
|
|
15 Oct 2014
|
Επίλυση αναδρομικών εξισώσεων με τη μέθοδο της αντικατάστασης. Παραδείγματα και ασκήσεις.
|
|
20 Oct 2014
|
Εκτίμηση της λύσης αναδρομικών εξισώσεων με τη μέθοδο του δέντρου αναδρομής. Παραδείγματα εφαρμογής της μεθόδου.
|
|
22 Oct 2014
|
Το Κεντρικό Θεώρημα. Παραδείγματα εφαρμογής του. Παράδειγμα αναδρομικής σχέσης στην οποία δεν είναι εφαρμόσιμο.
|
|
27 Oct 2014
|
Ο σωρός ως δομή δεδομένων. Ταξινόμηση με σωρό, και ο αλγόριθμος HeapSort.
|
|
29 Oct 2014
|
Ο αλγόριθμος ταξινόμησης QuickSort.
|
|
03 Nov 2014
|
Κάτω φράγμα πολυπλοκότητας για αλγορίθμους ταξινόμησης που βασίζονται σε συγκρίσεις.
|
|
05 Nov 2014
|
Αλγόριθμοι ταξινόμησης που δεν βασίζονται σε συγκρίσεις. Οι αλγόριθμοι
CountingSort και RadixSort.
|
|
10 Nov 2014
|
Προβλήματα Επιλογής:
- Επιλογή ελαχίστου
- Επολογή μεγίστου
- Επιλογή ελαχίστου και μεγίστου
- Επιλογή ελαχίστου και 2ου ελαχίστου
- Επιλογή στοιχείου τάξης k βρίσκωντας k ελάχιστα
- Επιλογή στοιχείου τάξης k με σωρό
|
|
12 Nov 2014
|
Επιλογή σε αναμενόμενο γραμμικό χρόνο.
Ο τυχαιοκρατικός αλγόριθμος RandomizedSelect, και ανάλυση της
πολυπλοκότητάς του.
|
|
19 Nov 2014
|
Επιλογή σε χειρότερο δυνατό γραμμικό χρόνο.
Ο αλγόριθμος Select, και ανάλυση της πολυπλοκότητάς του (γραμμική).
|
|
24 Nov 2014
|
Εισαγωγή στα γραφήματα και ορισμοί.
Αναπαράσταση γραφημάτων.
Ο αλγόριθμος αναζήτησης κατά βάθος (BFS).
|
|
26 Nov 2014
|
Ο αλγόριθμος αναζήτησης κατά πλάτος (DFS).
Τα είδη ακμών στο αλγόριθμο DFS. Ιδιότητες
των χρόνων έναρξης και τερματισμού αναζήτησης
των κόμβων. Ο αλγόριθμος DFS ως μέθοδος εύρεσης
ύπαρξης κυκλωμάτων σε γραφήματα.
|
|
01 Dec 2014
|
Πρόοδος του μαθήματος.
|
|
08 Dec 2014
|
Τοπολογική ταξινόμηση κατευθυνόμενων ακυκλικών γράφων (DAGs).
Περιγραφή του προβλήματος Ελαχίστου Επικαλύπτοντος Δέντρου (MST).
|
|
10 Dec 2014
|
Οι αλγόριθμοι των Kruskal και Prim για την εύρεση
ελαχίστων επικαλυπτόντων δέντρων. Ανάλυση πολυκλοκότητας του
αλγορίθμου του Kruskal, και ορθότητα του αλγορίθμου αυτού.
Ορθότητα του αλγορίθμου του Prim.
|
|
15 Dec 2014
|
Ανάλυση πολυκλοκότητας του αλγορίθμου του Prim.
Το πρόβλημα εύρεσης ελαχίστων μονοπατιών. Ιδιότητες
ελαχίστων μονοπατιών. Η έννοια της χαλάρωσης ακμής
και λογική των αλγορίθμων που βασίζονται σε χαλαρώσεις
ακμών. Ιδιότητες αλγορίθμων που βασίζονται σε
χαλαρώσεις ακμών.
|
|
17 Dec 2014
|
Ο αλγόριθμος των Bellman & Ford. Αλγόριθμος εύρεσης
ελαχίστων μονοπατιών σε DAGs. Σύντομη περιγραφή του αλγορίθμου του
Dijkstra.
|
Ασκήσεις
Οι ασκήσεις θα είναι διαθέσιμες μόνο
από την ιστοσελίδα του μαθήματος.
Οι ασκήσεις θα φέρουν ημερομηνία παράδοσης που θα
αντιστοιχεί πάντα σε ημέρα που υπάρχει διάλεξη του
μαθήματος. Θα πρέπει δε να παραδίδονται στην αρχή της
διάλεξης αυτής.
Oι λύσεις τους θα γίνονται κατά τη διάρκεια των διαλέξεων.
| Άσκηση |
Περιγραφή |
PDF |
|
1η
|
Η άσκηση αυτή αφορά τους τους συμβολισμούς Ο, Θ, Ω, ο, ω
και την επίλυση αναδρομικών σχέσεων.
|
|
|
2η
|
Η άσκηση αυτή αφορά την επίλυση αναδρομικών σχέσεων.
|
|
|
2η
|
Η άσκηση αυτή αφορά αλγορίθμους ταξινόμησης, εύρεσης και
αναζήτησης σε γράφους.
|
|
Αξιολόγηση
Οι ασκήσεις του μαθήματος και η πρόοδος είναι υποχρεωτικά,
με την έννοια ότι αντιστοιχούν σε συγκεκριμένο ποσοστό του τελικού βαθμού.
Ο βαθμός του μαθήματος (Β) τόσο για την περίοδο Ιανουαρίου, όσο και για την
περίοδο Σεπτεμβρίου θα υπολογιστεί από το βαθμό της προόδου (Π), το βαθμό
των ασκήσεων (Α), και το βαθμό της τελικής
εξέτασης (Ε), σύμφωνα με τον τύπο:
B = 0.15 * A + 0.2 * Π + 0.65 * Ε, αν Ε ≥ 4
B = E, αν E < 4
Εξετάσεις
Όλες οι εξετάσεις του μαθήματος θα γίνουν με κλειστά βιβλία.
Η χρήση οποιούδηποτε είδους ηλεκτρονικής συσκευής δεν θα
επιτραπεί. Παραταύτα στην πρόοδο μπορείτε να έχετε μαζί σας μέχρι και 2
σελίδες (1 φύλλο) χειρόγραφων σημειώσεων, ενώ στις εξετάσεις των περιόδων
Ιανουαρίου και Σεπτεμβρίου μπορείτε να έχετε μέχρι και 4 σελίδες (2 φύλλα)
χειρόγραφων σημειώσεων. Σε περίπτωση που οι
σημειώσεις σας δεν είναι χειρόγραφες θα κατάσχονται.
Σε περίπτωση που για τον οποιοδήποτε λόγο δεν μπορείτε
να παρευρεθείτε σε εξέταση του μαθήματος, επικοινωνήστε με τον
διδάσκοντα του μαθήματος το συντομότερο δυνατόν.
Σε περίπτωση που για ιατρικούς λόγους χρειάζεστε ειδική
μεταχείρηση στις εξετάσεις του μαθήματος (π.χ. λόγω αναπηρίας), επικοινωνήστε με το
διδάσκοντα του μαθήματος το συντομότερο δυνατό.
Στις εξετάσεις να έχετε μαζί σας την φοιτητική σας
ταυτότητα.
Βαθμολογίες
| Περιγραφή |
PDF |
| Συγκεντρωτικός πίνακας βαθμολογιών για την περίοδο Φεβρουαρίου |
|
| Πίνακας βαθμολογιών για την ειδική περίοδο Ιουνίου |
|