Εισαγωγή στη σχεδίαση και ανάλυση αλγορίθμων: Αλγοριθμικά προβλήματα και μαθηματική μοντελοποίησή τους, περιγραφή αλγορίθμων με ψευδοκώδικα, ορθότητα και τερματισμός, χρονική και χωρική πολυπλοκότητα, ανάλυση καλύτερης, χειρότερης και αναμενόμενης περίπτωσης, ασυμπτωτικός συμβολισμός O, Ω και Θ, αθροίσματα και αναδρομικές σχέσεις, θεώρημα Master.
Βασικές τεχνικές σχεδίασης αλγορίθμων: Εξαντλητική αναζήτηση και οπισθοδρόμηση, διαίρει και βασίλευε, άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός και τυχαιοποιημένοι αλγόριθμοι. Επιλογή της κατάλληλης τεχνικής με βάση τη δομή του προβλήματος. Αποδείξεις ορθότητας με μαθηματική επαγωγή, αμετάβλητες συνθήκες και επιχειρήματα ανταλλαγής.
Ταξινόμηση, αναζήτηση και επιλογή: Συγκριτικοί αλγόριθμοι ταξινόμησης, ταξινόμηση με συγχώνευση, γρήγορη ταξινόμηση και ταξινόμηση σωρού, εύρεση διαμέσου και k-οστού στοιχείου, κάτω φράγματα στο μοντέλο συγκρίσεων.
Αλγόριθμοι γράφων: Αναπαράσταση γράφων, αναζήτηση κατά πλάτος και κατά βάθος, συνδεσιμότητα, διμερικότητα, τοπολογική διάταξη και ισχυρά συνεκτικές συνιστώσες, ελάχιστα γεννητικά δέντρα, συντομότερες διαδρομές, μέγιστη ροή, ελάχιστη τομή και διμερής αντιστοίχιση.
Υπολογιστική πολυπλοκότητα και αναγωγές: Προβλήματα απόφασης, αποδοτικοί και μη αποδοτικοί αλγόριθμοι, πιστοποιητικά και επαλήθευση, οι κλάσεις P και NP, πολυωνυμικές αναγωγές, NP-σκληρότητα και NP-πληρότητα, το θεώρημα Cook–Levin, κλασικά NP-πλήρη προβλήματα και τεχνικές απόδειξης NP-πληρότητας.
Αλγόριθμοι για υπολογιστικά δύσκολα προβλήματα: Τυχαιοκρατικοί και προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, ευρετικές μέθοδοι και άλλες τεχνικές αντιμετώπισης προβλημάτων για τα οποία δεν είναι γνωστοί αποδοτικοί ακριβείς αλγόριθμοι.
Επιλεγμένα θέματα αλγορίθμων και εφαρμογών: Παρουσίαση πρόσθετων περιοχών της αλγοριθμικής, ανάλογα με τον διαθέσιμο χρόνο και τα ενδιαφέροντα του μαθήματος. Τα θέματα μπορούν να περιλαμβάνουν ενδεικτικά αλγορίθμους συμβολοσειρών, υπολογιστική γεωμετρία, αλγοριθμική θεωρία αριθμών και κρυπτογραφία, διαδικτυακούς ή προσεγγιστικούς αλγορίθμους και εφαρμογές σε σύγχρονα υπολογιστικά προβλήματα.
Μαθησιακά Αποτελέσματα:
Το μάθημα εστιάζει στις θεμελιώδεις έννοιες και τεχνικές της σχεδίασης και ανάλυσης αλγορίθμων, καθώς και στην κατανόηση των ορίων της αποδοτικής υπολογιστικής επίλυσης. Στόχος του είναι η ανάπτυξη αλγοριθμικής σκέψης: η ικανότητα μετάβασης από την άτυπη περιγραφή ενός προβλήματος στην ακριβή μαθηματική του διατύπωση, στον σχεδιασμό ενός ορθού αλγορίθμου και στην τεκμηριωμένη αξιολόγηση της αποδοτικότητάς του.
Με την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:
Να μοντελοποιούν προβλήματα που προκύπτουν από πρακτικές εφαρμογές ως σαφώς ορισμένα μαθηματικά και αλγοριθμικά προβλήματα, προσδιορίζοντας τις εισόδους, τις επιθυμητές εξόδους και τους σχετικούς περιορισμούς.
Να διατυπώνουν και να περιγράφουν αλγορίθμους με σαφήνεια και ακρίβεια, χρησιμοποιώντας κατάλληλο ψευδοκώδικα και μαθηματικό συμβολισμό.
Να σχεδιάζουν αλγορίθμους αξιοποιώντας βασικές τεχνικές, όπως η εξαντλητική αναζήτηση, το διαίρει και βασίλευε, οι άπληστοι αλγόριθμοι, ο δυναμικός προγραμματισμός, η οπισθοδρόμηση και η τοπική αναζήτηση.
Να επιλέγουν την κατάλληλη τεχνική σχεδίασης για ένα δεδομένο πρόβλημα και να αναγνωρίζουν τις δομικές ιδιότητες που καθιστούν μια τεχνική εφαρμόσιμη.
Να αποδεικνύουν την ορθότητα αλγορίθμων χρησιμοποιώντας κατάλληλες μεθόδους, όπως μαθηματική επαγωγή, αμετάβλητες συνθήκες, επιχειρήματα ανταλλαγής και αποδείξεις μέσω αντίφασης.
Να αναλύουν τη χρονική και χωρική πολυπλοκότητα αλγορίθμων, χρησιμοποιώντας ασυμπτωτικό συμβολισμό, αθροίσματα και αναδρομικές σχέσεις.
Να συγκρίνουν διαφορετικές αλγοριθμικές λύσεις ως προς την ορθότητα, την αποδοτικότητα, τις απαιτήσεις μνήμης και την καταλληλότητά τους για διαφορετικές κατηγορίες εισόδων.
Να διακρίνουν μεταξύ προβλημάτων που επιδέχονται αποδοτική αλγοριθμική επίλυση και προβλημάτων που θεωρούνται υπολογιστικά δυσεπίλυτα.
Να κατανοούν και να εφαρμόζουν τις βασικές έννοιες της υπολογιστικής πολυπλοκότητας, όπως οι κλάσεις P και NP, οι πολυωνυμικές αναγωγές, η NP-σκληρότητα και η NP-πληρότητα.
Να τεκμηριώνουν με αυστηρό και κατανοητό τρόπο τις σχεδιαστικές επιλογές, τις αποδείξεις ορθότητας και την ανάλυση των αλγορίθμων τους.
Αξιολόγηση:
Λεπτομέρειες για την βαθμολόγηση του μαθήματος περιέχονται στην ιστοσελίδα του μαθήματος
Τα μαθήματα του Τμήματος Επιστήμης Υπολογιστών κωδικοποιούνται με τα γράμματα "ΗΥ" και με τρία ψηφία. Το πρώτο ψηφίο δηλώνει το έτος κατά το οποίο συνήθως παρακολουθείται το μάθημα, το δε δεύτερο την επιστημονική περιοχή του μαθήματος:
Πρώτο Ψηφίο
Κανονικό Έτος Παρακολούθησης
1,2,3,4
Πρώτο, Δεύτερο, Τρίτο, Τέταρτο
5,6
Μεταπτυχιακά μαθήματα
7,8,9
Ειδικά θέματα
Δεύτερο Ψηφίο
Επιστημονική Περιοχή
0
Εισαγωγικά - Γενικά
1
Υπόβαθρο (Μαθηματικά, Φυσική)
2
Υλικό και Συστήματα Υπολογιστών
3
Τηλεπικοινωνίες και Δίκτυα
4,5
Συστήματα Λογισμικού και Εφαρμογές
6
Πληροφοριακά Συστήματα
7
Υπολογιστική Όραση και Ρομποτική
8
Αλγοριθμική και Θεωρία Υπολογισμού
9
Ειδικές Εργασίες
Ακολουθούν συνοπτικοί κατάλογοι κατά κατηγορίες των μαθημάτων του προγράμματος βασικών σπουδών του Τμήματος Επιστήμης Υπολογιστών του Πανεπιστημίου Κρήτης. Μαθήματα των οποίων οι κωδικοί αρχίζουν με "ΜΕΜ" ή "ΦΥΣ" διδάσκονται από το Τμήμα Μαθηματικών Εφαρμοσμένων Μαθηματικών ή το Φυσικό αντιστοίχως και αναφέρονται με τους οικείους κωδικούς. Τα προαπαιτούμενα που αναφέρονται μέσα σε παρενθέσεις συνιστώνται έντονα, αλλά δεν είναι υποχρεωτικά.