Αλγόριθμοι και Πολυπλοκότητα
Διδάσκοντες Ορέστης Τελέλης
Κατηγορία μαθήματος Κ
Κωδικός μαθήματος ΨΣ-101
Πιστωτικές μονάδες 5
Ώρες μαθήματος 3 ώρες
Ώρες εργαστηρίων 2 ώρες
Ηλεκτρονικό υλικό Προβολή στον Αρίσταρχο (Open e-Class)

Μαθησιακά Αποτελέσματα

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής / η φοιτήτρια θα είναι σε θέση:

  • να εξηγεί και χειρίζεται θεμελιώδεις έννοιες όπως πρόβλημα (και τύπος προβλήματος, αναλόγως της πολυπλοκότητας), αλγόριθμος, στιγμιότυπο, χρόνος εκτέλεσης ως συνάρτηση μεγέθους στιγμιοτύπου, ασυμπτωτική συμπεριφορά αλγορίθμου, ασυμπτωτικός συμβολισμός, αναδρομικές εξισώσεις και μεθόδους επίλυσής τους.
  • να αναλύει, επιλέγει, και αποτιμά αλγορίθμους βασιζόμενος/η στις παραπάνω έννοιες.
  • να σχεδιάζει αποτελεσματικούς αλγορίθμους βασιζόμενος/η στις παραπάνω έννοιες και σε βασικές τεχνικές σχεδιασμού αλγορίθμων (διαίρει και βασίλευε, απληστία, δυναμικός προγραμματισμός)
  • να επικοινωνεί αλγοριθμικές ιδέες με καθαρό, σαφή και τυπικό τρόπο.

Με στόχο να κατασκευάζει και να αποτιμά υπολογιστικά προγράμματα και την χρήση των πόρων που απαιτούν.

Περιεχόμενα

  • Εισαγωγή, Αντιπροσωπευτικά Προβλήματα
  • Στοιχεία Ανάλυσης Αλγορίθμων
  • Γραφήματα και Αλγόριθμοι
  • Άπληστοι Αλγόριθμοι
  • Αλγόριθμοι “Διαίρει και Βασίλευε”
  • Δυναμικός Προγραμματισμός
  • Στοιχεία Ροών Δικτύου
  • Υπολογιστική Δυσεπιλισιμότητα

Προτεινόμενα Συγγράμματα

  • Kleinberg J. &Tardos E. (2006): Algorithm Design, (Pearson International Edition), Addison Wesley,
  • Τ. Cormen, C.Leiserson, R.Rivest, C.Stein (2009): Introduction to Algorithms, The MIT Press (μεταφρασμένο στα Ελληνικά, εκδόσεις ΠΕΚ)

Πρόσθετη Βιβλιογραφία

Επιπλέον, στο e-class του τμήματος αναρτώνται σημειώσεις σε ηλεκτρονική μορφή και ασκήσεις.