Μάθημα Κωδικός  Εξάμηνο Τύπος Ώρες Εργαστήριο /
Φροντιστήριο
ECTS Διδάσκοντες
Αλγόριθμοι ΗΥ020  Δ Κορμού  4
6
Ανδρόνικος Θ.

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

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

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

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

Η έννοια του αλγορίθμου και της πολυπλοκότητας. Βασικές έννοιες της ανάλυσης αλγορίθμων. Μαθηματικό υπόβαθρο. Τεχνικές επίλυσης αναδρομικών εξισώσεων. Τεχνικές σχεδίασης αλγορίθμων. Η τεχνική «διαίρει και βασίλευε». Ο αλγόριθμος της συγχώνευσης. Ο αλγόριθμος της γρήγορης ταξινόμησης. Ελάχιστος χρόνος εκτέλεσης αλγορίθμων διάταξης. Πολλαπλασιασμός αριθμών και πινάκων. Η τεχνική του δυναμικού προγραμματισμού. Ιδιότητα βέλτιστων επιμέρους δομών. Το πρόβλημα του πολλαπλασιασμού ακολουθίας πινάκων. Το ακέραιο πρόβλημα του σακιδίου. Το πρόβλημα της διαμέρισης. Η άπληστη τεχνική. Δρομολόγηση εργασιών, απληστία και ρέστα, το κλασματικό πρόβλημα του σακιδίου. Θεωρία Γραφημάτων. Αναπαράσταση γραφημάτων, αλγόριθμοι εξερεύνησης γραφημάτων. Αναζήτηση πρώτα σε πλάτος, αναζήτηση πρώτα σε βάθος. Τοπολογική ταξινόμηση. Ελάχιστα επικαλύπτοντα δένδρα. Άπληστος υπολογισμός ελάχιστου επικαλύπτοντος δέντρου. Συντομότερα μονοπάτια. Συντομότερα μονοπάτια μοναδικής πηγής. Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών. Οπισθοδρόμηση. Διακλάδωση και Φράξιμο. Βασικοί αλγόριθμοι συμβολοσειρών. Εισαγωγή στη Θεωρία Υπολογιστικής Πολυπλοκότητας.

Υλικό Μαθήματος

https://e-class.ionio.gr/courses/DCS237/

Προτεινόμενη Βιβλιογραφία

  1. “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ ΤΟΜΟΣ Ι”, CORMEN T.H., LEISERSON C.E., RIVEST R.L., STEIN C., Εκδόσεις ΙΤΕ-ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ, ISBN 978-960-524-225-1, 2009
  2. “Αλγόριθμοι”, Rawlins Gregory J. E., Εκδόσεις Κριτική, ISBN 978-960-218-350-2, 2004