Αλγόριθμοι και Πολυπλοκότητα (εαρινό '11)
Θεωρία: αίθουσα «Νο. 3»,
Σχολικό Κτίριο, Πέμπτη 19:00-21:00, Παρασκευή 11:00-13:00 (Α.
Καπόρης)
Εργαστήριο: αίθουσα
"Ηλέκτρα", Τρίτη 17:00-21:00 (Α. Δούμα, Δ. Δρόσος, Ε.
Κωνσταντίνου, Α. Λερός)
Διαλέξεις (&
video):
25/3/2011
Σελίδες 1-24 από τις διαφάνειες
εδώ του
καθηγητή Josep Diaz. Έγιναν οι σελίδες 11-15 από το βιβλίο
Algorithms. Σχεδιάσαμε γραμμικό αλγόριθμο υπολογισμού της
ακολουθίας Fibonacci με αρχικά γραμμικό και μετά σταθερό χώρο. Η
μαγνητοσκόπηση είναι
εδώ και
εδώ. Θα πρέπει να κατεβάσετε το km
player (free) για να τις δείτε.
3-4/3/2011
Δείτε μαγνητοσκόπηση
εδώ
(3/3/2011) και
εδώ
(4/3/2011) για ασυμπτωτικό συμβολισμό συναρτήσεων.
Αφορούσαν σελ. 29-42 από Algorithm Design.
Σελ. 15-17 από
Algorithms. Σελ. 40-59 (ενότητες 3.1 ως
αρχή 4.1) από Introduction to Algorithms.
Δείτε & ΜΙΤ διάλεξη
εδώ.
10-11/3/2011
Δείτε μαγνητοσκόπηση
εδώ
(10/3/2011) και
εδώ
(11/3/2011) για
χρονική πολυπλοκότητα για αλγορίθμους "διαίρει & βασίλευε" merge-sort και "sort&count".
Αφορούσαν σελ. 209-225 από Algorithm Design
και
Σελ. 58-62 από
Algorithms και Σελ. 29-39, 59-83 από
Introduction to Algorithms.
Δείτε & ΜΙΤ διάλεξη
εδώ.
17-18/3/2011
Δείτε video με maple
tutorial
εδώ
(17/3/2011)
και
εδώ
(18/3/2011) για
τον άπληστο αλγόριθμο σε
Interval scheduling.
Αφορούσαν σελ. 115-122 από Algorithm Design.
Δείτε & ΜΙΤ διάλεξη
σε άπληστους αλγόριθμους
εδώ.
31/3-1/4/2011
Δείτε video με διάλεξεις σε
άπληστους
εδώ
(31/3/2011)
και
εδώ
(1/4/2011).
7/4-8/4/2011
Δείτε video με διάλεξεις σε
Δυναμικό Προγραμματισμό
εδώ
(7/4/2011)
και
εδώ
(8/4/2011).
Οι σημειώσεις των διαφανειών είναι
εδώ. Δείτε και τις πολύ καλές
διαλέξεις στο MIT.
5/5-6/5/2011
Δείτε video με διάλεξεις σε
Δυναμικό Προγραμματισμό
εδώ
(5/5/2011).
12/5-13/5/2011
Δείτε video με διάλεξεις σε
Δυναμικό Προγραμματισμό
εδώ
(12/5/2011).
Δείτε video με διάλεξεις
σε Πιθανοτικούς Αλγόριθμους
εδώ
(13/5/2011).
Αφορούν Κεφ. 13, σελ. 707-714 στο βιβλίο
Algorithm Design. Δείτε και τις πολύ καλές
διαλέξεις στο MIT
για πιθανοτικό quicksort.
19/5-20/5/2011
Δείτε video με διάλεξεις
σε Πιθανοτικούς Αλγόριθμους
εδώ
(19/5/2011)
και
εδώ (20/5/2011).
26/5-27/5/2011
Δείτε video με διάλεξεις
σε Πιθανοτικούς Αλγόριθμους
εδώ.
23/6/2011
Λύσεις Τελική Εξέταση Θεωρία (Νέο!).
Χρήσιμο υλικό:
Τα επίσημα συγγράμματα του μαθήματος που θα
λάβετε από το Τμήμα είναι οι μεταφράσεις στα Ελληνικά από
τα αντίστοιχα πρωτότυπα στα Αγγλικά
Algorithms by S. Dasgupta, C.H.
Papadimitriou, και U.V.
Vazirani.
Algorithm Design by Jon Kleinberg and Eva Tardos
(δείτε &
slides).
Επίσης, πολύ καλό βιβλίο στα Αγγλικά είναι και το
Introduction to Algorithms by Cormen
, Leiserson, Rivest and Stein από το οποίο
θα κάνουμε αρκετά σημεία στις διαλέξεις.
Βαθμολογία:
Τελική
γραπτή εξέταση κατοχυρώνεται με
≥5
στο εργαστήριο (που προκύπτει από συμμετοχή & παράδοση
homework &
τελική εξέταση εργαστηρίου). Αν η τελική γραπτή εξέτασης είναι
≥5,
τότε τελικός βαθμός = 30% (βαθμ. εργ.) + 70% (βαθμ. τελ. εξέτ.).
Όσοι
έχουν περάσει το εργαστήριο με τον κ. Ριζομυλιώτη,
κατοχυρώνουν
δικαίωμα τελικής γραπτής εξέτασης, αν φροντίσουν να λάβω
email επιβεβαίωσης
από κ. Ριζομυλιώτη.
Τελική Εξέταση
Εργαστηρίου: Τρίτη 31/5.
Τελική γραπτή εξέταση θεωρίας:
23/6, 15:00, Σχολική αίθουσα Νο 1, Νο
3.
Ώρες για φοιτητές:
Τετ-Πεμ-Παρ: 18:00-21:00, κτίριο Λυμπέρη, 2ος όροφος, γραφείο Β5
(είσοδος από Β1), τηλ. 22730 82239- kaporisa@gmail.com
|