Αλγόριθμοι και Πολυπλοκότητα e-learning

Μέσω αυτού του μαθήματος οι φοιτητές θα είναι σε θέση να:

• Ορίζουν την έννοια της χρονικής πολυπλοκότητας.
• Διακρίνουν τις διαφορές μεταξύ των ασυμπτωτικών συμβολισμών Ο,Ω,Θ.
• Υπολογίζουν τη χρονική πολυπλοκότητα ενός αλγορίθμου με δομές επανάληψης.
• Υλοποιούν προγραμματιστικά σωρό με τη βοήθεια μονοδιάστατου πίνακα.
• Αναγνωρίζουν τις διαφορές μεταξύ ενός απλού και ενός δυαδικού δέντρου.
• Ξεχωρίζουν ένα πλήρες δυαδικό δέντρο από ένα σχεδόν πλήρες.
• Υπολογίζουν την πολυπλοκότητα αλγορίθμων εισαγωγής και διαγραφής στις δομές δέντρου και ουράς.
• Εντοπίσουν τις συνεκτικές συνιστώσες ενός μη κατευθυνόμενου γραφήματος και τις ισχυρές συνεκτικές συνιστώσες ενός κατευθυνόμενου.
• Κατανοήσουν ότι οι αλγόριθμοι αναζήτησης γράφων έχουν ευρεία εφαρμογή σε παιχνίδια με λαβύρινθους.
• Κατασκευάσουν τη λύση ενός τέτοιου παιχνιδιού με τη βοήθεια των αλγορίθμων BFS και DFS.
• Κατονομάζουν τουλάχιστον 2 διαφορές μεταξύ των αλγορίθμων BFS και DFS.
• Κατανοήσουν τους αλγορίθμους Dijkstra,Kruskal,Prim,  τις ιδιότητες και τα χαρακτηριστικά των συνεκτικών δέντρων ελάχιστου κόστους 
• Aναγνωρίσουν τη σημασία της απόδειξης ορθότητας, αλλά και του θεωρήματος βέλτιστου για συνεκτικά δέντρα με ελάχιστο κόστος (βάρος)
• .
• Eφαρμόζουν τον αλγόριθμο Dijkstra για την υλοποίηση του αλγορίθμου του συντομότερου μονοπατιού από τον κόμβο αφετηρίας ενός γράφου σε έναν άλλο κόμβο του ίδιου γράφου και τους αλγορίθμους Prim και Kruskal για την υλοποίηση του αλγορίθμου για το συνεκτικό δέντρο με ελάχιστο βάρος.
• Κατανοήσουν την έννοια του Δυναμικού Προγραμματισμού,αλλά και το πως και το πότε εφαρμόζεται και να κατασκευάζουν έναν κατευθυνόμενο άκυκλο γράφο (DAG).
• Υλοποιούν τους αλγορίθμους συντομότερου μονοπατιού για DAG,είτε αυτός είναι Bellman ford,όπου πρέπει να αναλογίζονται και τη περίπτωση να υπάρχουν αρνητικά βάρη στο γράφο, είτε αυτός γίνεται με τοπολογική ταξινόμηση .
• Εφαρμόζουν τον αλγόριθμο Ford -Fulkerson σε γράφο.
• Αναγνωρίζουν πότε η αρχική ροή σε ένα γράφο διατηρείται.
• Εντοπίζουν το μονοπάτι μέγιστης ροής.
• Υλοποιούν προγραμματιστικά τον αλγόριθμο Ford-Fulkerson.
• Κατανοήσουν την έννοια, τις ιδιότητες και τα χαρακτηριστικά ενός άπληστου αλγορίθμου.
• Κατασκευάζουν έναν άπληστο αλγόριθμο για όποιο πρόβλημα τους ζητείται.
• Αναγνωρίζουν αν ένα πρόβλημα μπορεί να υλοποιηθεί μέσω ενός άπληστου αλγορίθμου.
• Αποδεικνύουν αν ένας άπληστος αλγόριθμος είναι ορθός ή όχι.
• Αναγνωρίζουν πότε μία τοποθέτηση βασιλισσών στη σκακιέρα αποτελεί λύση στο πρόβλημα των Κ-βασιλισσών.
• Κατονομάζουν για ποιες τιμές του Κ , το πρόβλημα των Κ-βασιλισσών είναι αδύνατο.
• Κατασκευάζουν πρόγραμμα σε Python για την εύρεση των Κ-βασιλισσών με την τεχνική του backtracking.
• Εντοπίζουν ποια μέθοδος μεταξύ των backtracking και dynamic programming είναι προτιμότερη ανάλογα με τη φύση του προς λύση προβλήματος.
• Λύνουν ένα πρόβλημα με τη μέθοδο Divide and Conquer.
• Κατασκευάζουν μία αναδρομική συνάρτηση εντοπίζοντας το Base case και τον αναδρομικό τύπο.
• Υπολογίζουν τη χρονική πολυπλοκότητα ενός αναδρομικού αλγορίθμου.
• Επιλύουν το πρόβλημα των πύργων των Hanoi  τόσο σχεδιαστικά όσο και προγραμματιστικά.
• Ταξινομούν έναν πίνακα με τη μέθοδο MergeSort.
• Απαριθμούν τις συναντώμενες δυσκολίες κατά την εύρεση του base case αναδρομικού αλγορίθμου.
• Εντοπίζουν σε ποια τάξη μεγέθους ανήκει καθεμία από τις δοθέντες συναρτήσεις.
• Εφαρμόζουν το Master Theorem ανάλογα σε ποια από τις 3 περιπτώσεις βρίσκονται.
• Μετατρέπουν μία μη εκθετική συνάρτηση σε εκθετική με τη βοήθεια των λογαρίθμων.
•  

Μικτή διδασκαλία

• Αριθμός Εκπαιδευόμενων: 50
• Αριθμός Μαθημάτων: 13
• Χρόνος Μαθήματος: 2
• Χρόνος στο σπίτι: 2
• Συνολικός χρόνος: 52