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

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

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

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

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

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

Περιεχόμενα

  • Εισαγωγικές έννοιες: Η έννοια του προβλήματος, του αλγορίθμου, της ανάλυσης αλγορίθμων, και της υπολογιστικής πολυπλοκότητας. Προβλήματα βελτιστοποίησης και απόφασης, παραδείγματα. Παραδείγματα ανάλυσης αλγορίθμων: Πειραματικά και θεωρητικά. Υπολογιστικό μοντέλο. Βασικά εισαγωγικά στοιχεία για τις κλάσεις υπολογιστικής πολυπλοκότητας.
  • Ασυμπτωτικός Συμβολισμός. Ορισμοί, παραδείγματα και ασκήσεις. Παραδείγματα επί απλών αλγορίθμων.
  • Επανάληψη σωρών, δέντρων, και παρουσίασή τους ως μαθηματικά αντικείμενα (γενικευμένες δομές δεδομένων). Χρήση τους σε λειτουργίες που αφορούν στην ταξινόμηση, αναζήτηση κλπ. Υπολογισμός της υπολογιστικής πολυπλοκότητας λειτουργιών σε σωρούς, και λεπτομερής υπόδειξη του υπολογισμού της πολυπλοκότητας ταξινόμησης με σωρό. Συγκριτικοί αλγόριθμοι ταξινόμησης και υπολογισμός κάτω ασυμπτωτικού ορίου χρονικής πολυπλοκότητας για συγκριτικους αλγορίθμους ταξινόμησης.
  • Η γενικευμένη δομή του λεξικού: Παρουσίαση και συζήτηση για την υπολογιστική πολυπλοκότητα εισαγωγής, διαγραφής, αναζήτησης στοιχείου, αναλόγως της υλοποίησης του λεξικού. Πρόσθετο παράδειγμα υπολογισμού διαμέρισης συνόλου με λειτουργίες ένωσης και εύρεσης. Συζήτηση και παρουσίαση του υπολογισμού της υπολογιστικής πολυπλοκότητας των λειτουργιών ένωσης και εύρεσης σε δάσος (που αναπαριστά τα σύνολα διαμέρισης), βελτιστοποιήσεις των λειτουργιών και εφαρμογή σε γραφήματα (εύρεση συνιστωσών σε μη συνδετικά γραφήματα).
  • Εισαγωγή στην τεχνική διαίρει και βασίλευε. Επίδειξη του αλγορίθμου ταξινόμησης με συγχώνευση για την κατανόηση της τεχνικής και υπολογισμός της υπολογιστικής πολυπλοκότητας του αλγορίθμου με χρήση δέντρου αναδρομής. Εισαγωγή στις αναδρομικές εξισώσεις πολυπλοκότητας. Γενίκευση δέντρων αναδρομής και αναδρομικών εξισώσεων. Παρουσίαση και απόδειξη του κεντρικού θεωρήματος. Παραδείγματα και εφαρμογές.
  • Συνέχεια στην τεχνική διαίρει και βασίλευε: Η ταχυταξινόμηση ως παράδειγμα. Υπενθύμιση του αλγορίθμου, υπολογισμός της υπολογιστικής πολυπλοκότητας. Εισαγωγή στην έννοια του στοχαστικού αλγορίθμου και επίδειξη τρόπου υπολογισμού υπολογιστικής πολυπλοκότητας για στοχαστική ταχυταξινόμηση.
  • Απληστία: Βασικές έννοιες και παραδείγματα με συγκεκριμένα προβλήματα. Αποδείξεις ορθότητας αλγορίθμων και υπολογιστικής πολυπλοκότητάς τους.
  • Δυναμικός προγραμματισμός: Βασικές έννοιες. Διαφορές από τη μέθοδο της απληστίας και συζήτηση με παραδείγματα για τη σωστή χρήση της τεχνικής. Παραδείγματα προβλημάτων και υπολογισμός πολυπλοκότητας των αντίστοιχων αλγορίθμων δυναμικού προγραμματισμού. Εφαρμογές σε γραφήματα (μεταξύ άλλων).

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

  • Τ. Cormen, C.Leiserson, R.Rivest, C.Stein (2009): Introduction to Algorithms, The MIT Press (μεταφρασμένο στα Ελληνικά, εκδόσεις ΠΕΚ)
  • Sedgewick R. (2006): Αλγόριθμοι σε C, Μέρη 1-4, 3η αμερικάνικη έκδοση (μεταφρασμένο), Εκδόσεις Kλειδάριθμος.
  • Rawling G.J.E (2004): Αλγόριθμοι Ανάλυση και Σύγκριση (μεταφρασμένο), Εκδόσεις Κριτική.
  • Papadimitriou C. H. & Steiglitz K. (1982): Combinatorial optimization : algorithms and complexity, Prentice Hall.
  • Knuth D. (1997): Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison-Wesley,
  • Kleinberg J. &Tardos E. (2006): Algorithm Design, (Pearson International Edition), Addison Wesley,
  • Anany V. Levitin (2007): Introduction to the Design & Analysis of Algorithms, (Pearson International Edition), Addison Wesley.

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

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