Αλγόριθμοι και Πολυπλοκότητα

Εξάμηνο:
4ο
Τύπος Μαθήματος:
Υποχρεωτικό (ΥΜ)
Κατεύθυνση:
-
Κωδικός:
Κ17
ECTS:
8
Διδακτικές Ώρες
Ώρες Θεωρίας:
4
Ώρες Φροντιστηρίου:
2
Ώρες Εργαστηρίου:
0
Μάθημα στις Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (S1):
-
Διαχείριση Δεδομένων και Γνώσης (S2):
-
Λογισμικό (S3):
-
Υλικό και Αρχιτεκτονική (S4):
-
Επικοινωνίες και Δικτύωση (S5):
-
Επεξεργασία Σήματος και Πληροφορίας (S6):
-
Σχετικά Μαθήματα
Υποχρεωτικά Προαπαιτούμενα:
-
Συνιστώμενα Προαπαιτούμενα:
Αναλυτική Περιγραφή
DIT_PPS_K17-Αλγόριθμοι και Πολυπλοκότητα.pdf
Σύντομη περιγραφή Μαθήματος
Το μάθημα εισάγει τις έννοιες της σχεδίασης και ανάλυσης του αλγορίθμου και παρουσιάζει τα βασικά μαθηματικά εργαλεία που χρησιμοποιούνται για την αποτίμηση της απόδοσής του. Περιγράφει τις τεχνικές αναζήτησης σε σύνολα (union and find) και παρουσιάζει τις θεμελιώδεις τεχνικές διάσχισης σε γραφήματα, κατά πλάτος (BFS) και κατά βάθος (DFS). Εστιάζει στις τρεις βασικές μεθόδους σχεδίασης αλγορίθμων, “διαίρει και βασίλευε”, άπληστοι (greedy) αλγόριθμοι και δυναμικός προγραμματισμός. Αναλύει τα χαρακτηριστικά κάθε μεθόδου και αναδεικνύει τα πρακτικά προβλήματα που επιλύονται αποτελεσματικά από κάθε μέθοδο. Ορίζει τα προβλήματα απόφασης και τις κλάσεις P και NP. Περιγράφει την έννοια της αναγωγής και προσδιορίζει τα προβλήματα NP-complete και NP-hard.
Βιβλιογραφία

1. Th. H. Cormen, CH. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms, MIT-Press, 2009, 3rd edition, MIT Press, http://mitpress.mit.edu/algorithms/ (Εύδοξος).
2. Jon Kleinberg & Eva Tardos, Algorithm Design, Addison – Wesley, 2006 (Εύδοξος).
3. S. Dasgupta, C. H. Papadimitriou & U. V. Vazirani, Algorithms, McGraw-Hill, 2008 (Εύδοξος).


• Σημειώσεις, Αλγόριθμοι και Πολυπλοκότητα, 2016, Β. Ζησιμόπουλος
https://eclass.uoa.gr/modules/document/index.php?course=D469&openDir=/4c2b32c4z3e6


•Διαφάνειεςδιαλέξεων, https://eclass.uoa.gr/modules/document/index.php?course=D469&openDir=/4c2b32c4rt6n

Διδάσκων