8ο εξάμηνο


Μάθημα: Ανάλυση και Σχεδίαση Αλγορίθμων



Κωδικός Μαθήματος: ΜΚ37
Επίπεδο Μαθήματος: Προπτυχιακό
Τύπος Μαθήματος: Γενικού Υποβάθρου
Εξάμηνο: 8
Κατεύθυνση: Κατεύθυνση Υπολογιστών και Ηλεκτρονικής
Πιστωτικές Μονάδες: 5
Εβδομαδιαίες Ώρες διδασκαλίας: 4
Erasmus:
Ιστοσελίδα: eclass.uowm.gr/courses/ICTE332/
Γλώσσα διδασκαλίας:Ελληνική
Γενικές Ικανότητες:
Περιεχόμενο:

Ανάλυση Αλγορίθμων. Πολυπλοκότητα Αλγορίθμων. Ασυμπτωτική Ανάλυση. Τεχνικές Σχεδίασης Αλγορίθμων. Αναδρομικοί Αλγόριθμοι. Θεώρημα Κυριαρχίας. Αλγόριθμοι Διαίρει‐και‐Βασίλευε. Δυναμικός Προγραμματισμός, Άπληστοι Αλγόριθμοι. Πιθανοκρατικοί Αλγόριθμοι. Αλγόριθμοι Γραφημάτων και Δικτύων. Υπολογιστική Πολυπλοκότητα, οι κλάσεις P και NP, ΝΡ‐πληρότητα.

Αναμενόμενα μαθησιακά αποτελέσματα:

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

  • να πραγματοποιούν ανάλυση αλγορίθμων
  • να μελετούν αλγορίθμους ως προς την πολυπλοκότητα
  • να εκτελούν ασυμπτωτική ανάλυση αλγορίθμων
  • να σχεδιάζουν και να υλοποιούν αναδρομικούς και άπληστους αλγόριθμους
  • να σχεδιάζουν και να υλοποιούν αλγορίθμους εφαρμόζοντας τις αρχές του δυναμικού προγραμματισμού
  • να κατανοούν και να εφαρμόζουν αλγορίθμους γραφημάτων και δικτύων
  • να κατανοούν τις κλάσεις P και NP
Προαπαιτούμενα:

Κανένα

Τρόπος Παράδοσης:
Χρήση Τεχνολογιών Πληροφορίας και επικοινωνιών:
Οργάνωση Διδασκαλίας:

Διαλέξεις, εργαστήρια

Αξιολόγηση Φοιτητών:

Ασκήσεις (30%), Γραπτή εξέταση (70%)

Προτεινόμενη Βιβλιογραφία:
  1. Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, Εισαγωγή στους αλγορίθμους, Πανεπιστημιακές Εκδόσεις Κρήτης, Έκδοση: 1η/2016
  2. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Αλγόριθμοι, Εκδόσεις Κλειδάριθμος, Έκδοση: 1η/2009
  3. Παναγιώτης Μποζάνης, Αλγόριθμοι, Εκδόσεις Τζιόλα, Έκδοση: 2η/2017
  4. Jon Kleinberg, Eva Tardos, Σχεδιασμός αλγορίθμων, Εκδόσεις Κλειδάριθμος, Έκδοση: 1η/2009
  5. Anany Levitin, Ανάλυση και σχεδίαση αλγορίθμων, Εκδόσεις Τζιόλα, Έκδοση: 3η/2018
  6. Κωνσταντίνος Παπαρρίζος, Ανάλυση και σχεδίαση αλγορίθμων, Εκδόσεις Τζιόλα, Έκδοση: 1η/2010
Διδάσκων: Πλόσκας Νικόλαος