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

Γενικά

Σχολή: Ψηφιακής Τεχνολογίας

Τμήμα: Πληροφορικής και Τηλεματικής

Επίπεδο Σπουδών: Προπτυχιακό

Τίτλος Μαθήματος: Αλγόριθμοι και Πολυπλοκότητα

Κωδικός Μαθήματος: ΥΠ25

Τύπος: Επιστημονικής Περιοχής 

Εξάμηνο Σπουδών: 6

Γλώσσα Διδασκαλίας και Εξετάσεων: Ελληνική

Προσφέρεται σε φοιτητές Erasmus: ΝΑΙ

Ηλεκτρονική Σελίδα Μαθήματος: https://eclass.hua.gr/courses/DIT110/

Αυτοτελείς Δραστηριότητες

Εβδομαδιαίες ώρες διδασκαλίας (Θεωρία): 3

Εβδομαδιαίες ώρες διδασκαλίας (Εργαστήριο): 0

Πιστωτικές μονάδες: 5

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

Σκοπός του μαθήματος είναι η εξοικείωση των φοιτητών με την σχεδίαση και την ανάλυση αλγορίθμων για την επίλυση βασικών προβλημάτων. Οι φοιτητές θα γνωρίσουν τις βασικότερες μεθόδους σχεδίασης αλγορίθμων και τις βασικότερες αρχές ανάλυσης και μέτρησης της αποδοτικότητας των αλγορίθμων. Τέλος θα γνωρίσουν τις βασικότερες κλάσεις πολυπλοκότητας.

Φοιτητές που ολοκληρώνουν το μάθημα θα είναι σε θέση να γνωρίζουν:
- Τις βασικές τεχνικές σχεδιασμού αλγορίθμων.
- Αρχές ανάλυσης και μέτρησης της αποδοτικότητας των αλγορίθμων.
- Τρόπους αντιμετώπισης της NP-Πληρότητας

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

- Προσαρμογή σε νέες καταστάσεις
- Λήψη αποφάσεων
- Αυτόνομη εργασία
- Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης

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

Η έννοια του αλγορίθμου και πολυπλοκότητας. Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις. Αλγόριθμοι ταξινόμησης και επιλογής. Σωροί και ουρές προτεραιότητας. Τεχνικές αναζήτησης: μετασχηματισμός κλειδιού (hashing), δένδρα αναζήτησης. Δυναμικός προγραμματισμός, Άπληστοι (greedy) αλγόριθμοι. Αλγόριθμοι γραφημάτων: αναζήτηση σε γράφημα, ελάχιστο συνδέον δένδρο, συντομότεροι δρόμοι, μέγιστη ροή. Γενικά θέματα: ταξινόμηση μέσω δικτύων, αλγόριθμοι σύγκρισης συμβολοσειρών, αριθμητικοί αλγόριθμοι, NP-complete, προβλήματα.

1η εβδομάδα (Διάλεξη): Εισαγωγή.
2η εβδομάδα (Διάλεξη): Ανάλυση Αλγορίθμων
3η εβδομάδα (Διάλεξη): Αλγόριθμοι Γραφημάτων
4η εβδομάδα (Διάλεξη): Άπληστοι Αλγόριθμοι Ι
5η εβδομάδα (Διάλεξη): Άπληστοι Αλγόριθμοι ΙΙ
6η εβδομάδα (Διάλεξη): Διαίρει και Βασίλευε Ι
7η εβδομάδα (Διάλεξη): Διαίρει και Βασίλευε ΙΙ
8η εβδομάδα (Διάλεξη): Δυναμικός Προγραμματισμός Ι
9η εβδομάδα (Διάλεξη): Δυναμικός Προγραμματισμός ΙΙ
10η εβδομάδα (Διάλεξη): Δίκτυα, Μέγιστη Ροή και Ελάχιστη Αποκοπή 
11η εβδομάδα (Διάλεξη): NP & Υπολογιστική Δυσεπιλυσιμότητα Ι
12η εβδομάδα (Διάλεξη): NP & Υπολογιστική Δυσεπιλυσιμότητα ΙΙ
13η εβδομάδα (Διάλεξη): Αντιμετώπιση NP-Πληρότητας

Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση

Τρόπος Παρακολούθησης: πρόσωπο-με-πρόσωπο

Χρήση Τεχνολογιων Πληροφορίας και Επικοινωνιών: 

eclass μαθήματος, youtube channel

Οργάνωση Διδασκαλίας

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

Ι. Γραπτή τελική εξέταση (60%) που περιλαμβάνει:
- Ερωτήσεις πολλαπλής επιλογής
- Συγκριτική αξιολόγηση στοιχείων θεωρίας
ΙΙ. Ατομικές ή Ομαδικές Εργασίες (40%)

Συνιστώμενη Βιβλιογραφία

Jon Kleinberg & Eva Tardos, Σχεδιασμός Αλγορίθμων, Εκδόσεις Κλειδάριθμος, 2008.

Cormen, Leiserson, Rivest και Stein. Εισαγωγή στους αλγορίθμους, Τόμος Ι, Πανεπιστημιακές Εκδόσεις Κρήτης, 2006.