ΑΛΓΟΡΙΘΜΟΙ & ΠΟΛΥΠΛΟΚΟΤΗΤΑ

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

Οι μαθησιακοί στόχοι του μαθήματος συνοψίζονται στα εξής:

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

Γενικές Ικανότητες:


Οι ικανότητες που πρέπει να αποκτήσει ο πτυχιούχος και στις οποίες αποσκοπεί το μάθημα είναι:

• Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση των απαραίτητων τεχνολογιών.
• Προσαρμογή σε νέες καταστάσεις.
• Λήψη αποφάσεων.
• Αυτόνομη εργασία.
• Ομαδική εργασία
• Σχεδιασμός και διαχείριση έργων.
• Άσκηση κριτικής και αυτοκριτικής.
• Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης.

Περιεχόμενο Μαθήματος:

• Ασυμπτωτικός συμβολισμός (O, ο, Ω, ω, Θ).
• Ανάλυση πολυπλοκότητας αλγορίθμων (μέσης και χειρότερης περίπτωσης).
• Ανάλυση αποδοτικότητας αλγορίθμων ταξινόμησης.
• Τυχαιοκρατικοί αλγόριθμοι.
• Διαίρει και βασίλευε.
• Άπληστοι αλγόριθμοι.
• Αλγόριθμοι οπισθοδρόμησης (stable marriages, 8-queens).
• Δυναμικός προγραμματισμός (knapsack).
• Γραφήματα, αναπαραστάσεις γραφημάτων.
• Αναζήτηση κατά βάθος - αναζήτηση κατά πλάτος.
• Ελάχιστο συνεκτικό δένδρο (Kruskal, Prim).
• Συντομότερα μονοπάτια από μια κορυφή (Dikstra, Bellman Ford).
• Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών (Floyd Warshall).
• Υπολογιστική πολυπλοκότητα.
• Υπολογισιμότητα.
• Η κλάση προβλημάτων NP και το πρόβλημα P vs NP.
• NP πληρότητα, αναγωγές πολυωνυμικού χρόνου.
• Προσεγγιστικοί αλγόριθμοι.