6ο εξάμηνο


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



Τίτλος μαθήματος Ανάλυση και Σχεδίαση Αλγορίθμων
Κωδικός μαθήματος ΜΚ37
Είδος μαθήματος Υποχρεωτικό
Επίπεδο μαθήματος Προπτυχιακό
Έτος σπουδών 3ο
Εξάμηνο 6ο
Πιστωτικές μονάδες ECTS 5
Ιστοσελίδα eclass.uowm.gr/courses/ICTE311/
Ώρες ανά εβδομάδα 4
Διδάσκων Νικόλαος Πλόσκας (Επίκουρος Καθηγητής)
Περιεχόμενο μαθήματος Ανάλυση Αλγορίθμων, Πολυπλοκότητα Αλγορίθμων, Ασυμπτωτική Ανάλυση. Τεχνικές Σχεδίασης Αλγορίθμων, Αναδρομικοί Αλγόριθμοι, Αλγόριθμοι Διαίρει‐και‐Βασίλευε, Δυναμικός Προγραμματισμός, Άπληστοι Αλγόριθμοι, Πιθανοκρατικοί Αλγόριθμοι.
Αλγόριθμοι Γραφημάτων και Δικτύων.
Υπολογιστική Πολυπλοκότητα, οι κλάσεις P και NP, ΝΡ‐πληρότητα.
Αναμενόμενα μαθησιακά αποτελέσματα και δεξιότητες Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:
  • να κατανοήσουν βασικές αλγοριθμικές τεχνικές (π.χ. διαίρει-καιβασίλευε, δυναμικού προγραμματισμού)
  • να επεκτείνουν την αλγοριθμική τους σκέψη
  • να μπορούν να συνδυάζουν γνωστές τεχνικές για την επίλυση νέων προβλημάτων
  • να αναλύουν και να συγκρίνουν αλγορίθμους εκτιμώντας τους απαιτούμενους πόρους εκτέλεσης,
  • να μελετούν αλγορίθμους ως προς την πολυπλοκότητα
  • να εκτελούν ασυμπτωτική ανάλυση αλγορίθμων
  • να σχεδιάζουν και να υλοποιούν αποδοτικούς αλγορίθμους
  • να υλοποιούν προγραμματιστικά αλγόριθμους σε διάφορες γλώσσες προγραμματισμού
  • να κατανοούν και να εφαρμόζουν διάφορα είδη αλγορίθμων (αναδρομικούς, άπληστους, γραφημάτων και δικτύων, κ.α.)
  • να επιλέγουν τους καταλληλότερους αλγορίθμους ανάλογα με το πρόβλημα που αντιμετωπίζουν,
  • να κατανοούν τις κλάσεις P και NP.
Προαπαιτούμενα μαθήματα Κανένα
Μέθοδοι διδασκαλίας Διαλέξεις με χρήση διαφανειών, ασκήσεις στον πίνακα
Αξιολόγηση Δύο υποχρεωτικά σετ εργασιών με τελική προφορική εξέταση (30%)
Τελική Γραπτή Εξέταση (70%)
Γλώσσα διδασκαλίας Ελληνική
Βιβλιογραφία
  • CORMEN T.H., LEISERSON C.E., RIVEST R.L., STEIN C., ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ, ΤΟΜΟΣ Ι, ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ, 2009.
  • SANJOY DASGUPTA, CHRISTOS PAPADIMITRIOU, UMESH VAZIRANI, ΑΛΓΟΡΙΘΜΟΙ, ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ, 2009.
  • Μποζάνης Παναγιώτης Δ., Αλγόριθμοι, ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε., 2006.


Διδάσκων: Πλόσκας Νικόλαος