Αλγόριθμοι


Διδάσκων/ουσα: Ανδρόνικος Θεόδωρος
Κωδικός Μαθήματος: HY-020
Τύπος Μαθήματος: Μάθημα Κορμού
Επίπεδο Μαθήματος: Προπτυχιακό
Γλώσσα Μαθήματος: Ελληνικά
Εξάμηνο: Δ΄
ECTS: 6
Διδακτικές Μονάδες: 4
Ώρες Διάλεξης: 4
Σύνολο Ωρών: 4
Σελίδα E Class: https://opencourses.ionio.gr/courses/DDI189/


Αντικειμενικοί Στόχοι - Επιδιωκόμενα Μαθησιακά Αποτελέσματα:

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

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

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

Περιεχόμενο (Syllabus):

Το μάθημα απευθύνεται σε φοιτήτριες και φοιτητές του δεύτερου έτους σπουδών. Καλύπτει τα εξής θέματα:

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

Συνιστώμενη βιβλιογραφία προς μελέτη:
  1. “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ”, Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Εκδόσεις ΙΤΕ - Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-473-6, 2016
  2. “ΑΛΓΟΡΙΘΜΟΙ”, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-211-6, 2009
  3. “ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ”, Jon Kleinberg, Eva Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-207-9, 2009
Ενημέρωση: 15-01-2020

Επιστροφή