Τίτλος Μαθήματος:Ανάλυση & Σχεδιασμός Αλγορίθμων
Διδάσκοντες (ακαδημαϊκό έτος 2020-21):
α) Γεωργιάδης Λεωνίδας (Καθηγητής)
leonid@auth.gr (Θεωρία)
Γραφείο: Κτίριο Δ, 6ος όροφος, Γραφείο 23. Τηλ: 2310 996385
β) Συμεωνίδης Ανδρέας (Αναπληρωτής Καθηγητής)
asymeon@eng.auth.gr (Θεωρία)
Γραφείο: Κτίριο Δ, 4ος όροφος.
Τηλ: 2310 99 4344.
γ) Κρασανάκης Εμμανουήλ (Υποψήφιος Διδάκτορας)
manios.krasanakis@issel.ee.auth.gr (Ασκήσεις)
Περιεχόμενο ΜαθήματοςΤο μάθημα συζητά τεχνικές για την ανάλυση και των σχεδιασμό αλγορίθμων και δομών δεδομένων, όχι από την προγραμματιστική, αλλά την αναλυτική οπτική τους. Οι έννοιες που αναπτύσσονται στα πλαίσια του μαθήματος οδηγούν στον έλεγχο της επίδοσης ενός αλγορίθμου και τη σύγκριση δυο ή περισσοτέρων αλγορίθμων σε σχέση με τις απαιτήσεις τους σε χώρο και χρόνο. Αναλυτικές μέθοδοι χρησιμοποιούνται για την περιγραφή, τόσο των θεωρητικών, όσο και των πρακτικών ορίων των αλγορίθμων.
Συγκεκριμένα, στα πλαίσια του μαθήματος καλύπτονται: αρχές και μέθοδοι ανάλυσης αλγορίθμων, ασυμπτωτικός ρυθμός αύξησης συναρτήσεων, αναδρομικές σχέσεις, πιθανότική ανάλυση και τυχαιοκρατικοί αλγόριθμοι, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι, αντισταθμιστική ανάλυση, προχωρημένα θέματα στην ανάλυση και σχεδιασμό αλγορίθμων
Προτεινόμενα συγγράμματαΒιβλίο [59359780]: ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Βιβλίο [13898]: ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ, JON KLEINBERG, EVA TARDOS
Ύλη μαθήματος (ακαδ. έτος 2022-23):Δ = Διάλεξη, Παρ. = παράγραφοι του βιβλίου του Cormen
Δ-1: Εισαγωγή – Βασικές Έννοιες (Παρ. 1.1, 1.2, 2.1)
Δ-2: Ανάλυση Αλγορίθμων – Διαίρει & Κυρίευε (Παρ. 2.2, 2.3)
Δ-3: Ασυμπτωτικός Συμβολισμός (Παρ. 3.1, 3.2)
Δ-4: Ανάλυση Αναδρομικών Σχέσεων (Παρ. 4.1, 4.2, 4.3 - Παραρτήματα Α, Β1, Β2)
Δ-5: Πιθανοτική Ανάλυση – Τυχαιοκρατικοί Αλγόριθμοι (Παρ. 5.1, 5.2, 5.3 - Παραρτήματα Γ1-Γ4)
Δ-6: Ταχυταξινόμηση (Παρ. 7.1, 7.2, 7.3,7.4)
Δ-7: Δυναμικός Προγραμματισμός Ι: ΧΓΠ, ΑΠ (Παρ. 15.1, 15.2)
Δ-8: Δυναμικός Προγραμματισμός IΙ: ΜΚΥ, ΒΔΑ (Παρ. 15.3, 15.4, 15.5)
Δ-9: Άπληστοι Αλγόριθμοι Ι: ΕΔ, ΠΣ (Παρ. 16.1, 16.2)
Δ-10: Άπληστοι Αλγόριθμοι ΙΙ: HC, ΕΣΔ (Παρ. 16.3, 23.1, 23.2)
Δ-11: Σύνθετα Θέματα
Τρόπος εξέτασης:Γραπτές εξετάσεις πάνω σε ασκήσεις
Επιπλέον 2 απαλακτικές πρόοδοι κατά τη διάρκεια του εξαμήνου.
Τρόπος Βαθμολόγησης:Πρόοδος 1
- Ύλη των διαλέξεων 1 – 6
- 40% του τελικού βαθμού
Ημερομηνία 1ης Προόδου: Θα οριστεί κατά τη διάρκεια του εξαμήνου. Ώρα: 11:00 – 13:00 πμ.
Πρόοδος 2
- Ύλη των διαλέξεων 1 – 13
- 60% του τελικού βαθμού
Ημερομηνία 2ης Προόδου: Θα οριστεί κατά τη διάρκεια του εξαμήνου. Ώρα: 11:00 – 13:00 πμ.
Γραπτές Εξετάσεις
- Ύλη των διαλέξεων 1 – 13
- 100% του τελικού βαθμού
Τελικός Βαθμός
Το μέγιστο του βαθμού: {(0.4*Πρόοδος 1 +0.6* Πρόοδος 2) , Γραπτές εξετάσεις}
Παρατηρήσεις
- Η συμμετοχή στις Προόδους είναι προαιρετική
- Στην περίπτωση επιτυχίας στις Προόδους, η προσέλευση στις Γραπτές εξετάσεις είναι προαιρετική.
-Η πρόοδος δεν κρατιέται για την εξετατική του Σεπτεμβρίου.
Προσοχή: Αν κάποια/ος μετέχει στις προόδους, και δεν παρουσιαστεί στις γραπτές εξετάσεις, θα σταλεί στη γραμματεία ο βαθμός προόδου της/του.
Αν επιθυμεί να ΜΗ ΣΤΑΛΕΙ ο βαθμός θα πρέπει μας ενημερώσει με email στο
asymeon@eng.auth.gr ΠΡΙΝ ΤΗΝ ΗΜΕΡΟΜΗΝΙΑ ΤΗΣ ΓΡΑΠΤΗΣ ΕΞΕΤΑΣΗΣ.
Επιπλέον πληροφορίες:To μάθημα διδάσκεται 4 ώρες κάθε εβδομάδα. 2 από αυτές αντιστοιχούν στη θεωρία και οι άλλες 2 στις ασκήσεις.
Επιπλέον υλικό:Στη σελίδα του μαθήματος στο e-elearning υπάρχουν:
- Αρχεία των διαφανειών των διαλέξεων και λύσεις των ασκήσεων.
- Αρχεία σημειώσεων – αν χρειαστεί.
- Αρχεία επιπλέον άρθρων – αν χρειαστεί.
- Quiz με ασκήσεις.
Ιστοσελίδες:Iστοσελίδα μαθήματος στο
elearningΣχόλια - απόψεις - συμβουλές:Δείτε εδωΠΡΟΣΟΧΗ! Το παρόν topic θα αφεθεί κλειδωμένο αν θέλετε να έχετε τυχόν διορθώσεις και σχόλια επικοινωνήστε με κάποιον συντονιστή.