Παρουσίαση/Προβολή

Αλγόριθμοι

(INF161) - EVANGELOS MARKAKIS

Περιγραφή Μαθήματος

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

Ημερομηνία δημιουργίας

Δευτέρα, 21 Δεκεμβρίου 2009

Σελίδα μαθήματος

Περίγραμμα
Διδάσκοντες

Διδάσκουσα

Αλκμήνη Σγουρίτσα

E-mail: alkmini at aueb dot gr

Ώρες γραφείου: Δευτέρα 13:00-15:00 και Τρίτη 9:00-11:00 (κατόπιν συνεννόησης μέσω e-mail)

Βοηθοί

Αρτέμης Τσικιρίδης, Χριστόδουλος Σαντοριναίος, Γιώργος Παπασωτηρόπουλος (Yποψήφιοι Διδάκτορες)

E-mails: {artem, santgchr, gpapasotiropoulos} at aueb dot gr

Ώρες γραφείου: Τετάρτη 1-3 (ή άλλη ημέρα/ώρα κατόπιν συνεννόησης), γραφείο: Α46.
Περιεχόμενο μαθήματος

Θα ακολουθήσουμε τις εξής θεματικές ενότητες:
- Ασυμπτωτικοί συμβολισμοί - Πολυπλοκότητα
- Σχεδίαση αλγορίθμων
  - Διαίρει και Βασίλευε (Divide and Conquer)
  - Aλγόριθμοι γράφων (Graph algorithms)
  - Άπληστοι αλγόριθμοι (Greedy algorithms)
  - Δυναμικός Προγραμματισμός (Dynamic Programming)
- Κλάσεις πολυπλοκότητας και ΝΡ-πληρότητα
Βιβλιογραφία

Για διανομή προτείνονται τα εξής δύο βιβλία:
- S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani: “Αλγόριθμοι”, εκδόσεις Κλειδάριθμος
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: “Εισαγωγή στους Αλγορίθμους”, Πανεπιστημιακές Εκδόσεις Κρήτης.
Σαν βοηθητικά συγγράμματα προτείνονται τα εξής
- J. Kleinberg, E.Tardos: “Σχεδιασμός Αλγορίθμων”, εκδόσεις Κλειδάριθμος
- Udi Manber: “Introduction to algorithms”, Addison Wesley,
- S. S. Skiena: “The Algorithm Design Manual”, Springer Verlang