Προηγμένα Θέματα Αλγορίθμων (ΠΛ3)

Περιγράμματα Μεταπτυχιακών Μαθημάτων - Τμήμα Μαθηματικών

Γενικά

Σχολή	Σχολή Θετικών Επιστημών
Τμήμα	Τμήμα Μαθηματικών
Επίπεδο Σπουδών	Μεταπτυχιακό
Κωδικός Μαθήματος	ΠΛ3
Εξάμηνο	1
Τίτλος Μαθήματος	ΠΡΟΗΓΜΕΝΑ ΘΕΜΑΤΑ ΑΛΓΟΡΙΘΜΩΝ
Αυτοτελείς Διδακτικές Δραστηριότητες	Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 7.5)
Τύπος Μαθήματος	Μάθημα Ειδίκευσης
Προαπαιτούμενα Μαθήματα	Προπτυχιακά μαθήματα σε Δομές Δεδομένων και Εισαγωγή στους Αλγορίθμους, (προαιρετικά ένα μάθημα στα Διακριτά μαθηματικά)
Γλώσσα Διδασκαλίας και Εξετάσεων	Ελληνική
Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus	Ναι (στην Αγγλική γλώσσα)
Ηλεκτρονική Σελίδα Μαθήματος (URL)	Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων.

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

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

Σκοπός είναι η βαθύτερη κατανόηση της σχεδίασης και ανάλυσης αλγορίθμων και η εξέταση ειδικών κλάσεων προβλημάτων και αλγορίθμων για την επίλυση τους καθώς και η εισαγωγή των φοιτητών στην κριτική σκέψη και την ερευνητική διαδικασία. Στο μάθημα γίνεται λεπτομερής εξέταση προηγμένων μεθόδων ανάλυσης και σχεδίασης αλγορίθμων. Μελετώνται τρόποι ανάλυσης ενός αλγορίθμου και εύρεσης της πολυπλοκότητάς του. Για την σχεδίαση ενός αλγορίθμου για ένα πρόβλημα μελετώνται βασικές μέθοδοι σχεδίασης όπως: απληστία, δυναμικός προγραμματισμός, οπισθοδρόμηση, αναδρομή, διεξοδική διερεύνηση και διελεύσεις με διακλάδωση και περιορισμό. Εξετάζονται κατηγορίες αλγορίθμων όπως ταξινόμηση, αναζήτηση, επιλογή, αλγόριθμοι σε γράφους, αριθμητική ακεραίων και πολυωνύμων, αλγόριθμοι σε πίνακες, αλγόριθμοι χειρισμού αλυσίδων. Ορίζονται οι κλάσεις πολυπλοκότητας P, NP. Ειδικά θέματα. Μετά την ολοκλήρωση του μαθήματος ο φοιτητής / τρια: Μπορεί να αναλύσει έναν αλγόριθμο Μπορεί να επιλέξει τον αποτελεσματικότερο αλγόριθμο μεταξύ αλγορίθμων για την επίλυση ενός προβλήματος. Έχει κατανόηση των βασικών σχεδιαστικών μεθόδων και μπορεί να σχεδιάσει αποτελεσματικούς αλγορίθμους για την επίλυση ενός προβλήματος. Γνωρίζει αλγορίθμους για την επίλυση βασικών κατηγοριών προβλημάτων και μπορεί να τους χρησιμοποιήσει σαν δομικό στοιχείο για την σχεδίαση άλλων αλγορίθμων.

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

Αυτόνομη εργασία Βιβλιογραφική έρευνα Ανάλυση πολυπλοκότητας ενός αλγορίθμου Επιλογή αλγορίθμου για την επίλυση ενός προβλήματος Μπορεί να σχεδιάσει αποτελεσματικούς αλγορίθμους για την λύση ενός προβλήματος

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

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

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

Τρόπος Παράδοσης	Πρόσωπο με πρόσωπο
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών	Ναι
Οργάνωση Διδασκαλίας	Δραστηριότητα Φόρτος Εργασίας Εξαμήνου Διαλέξεις 39 Αυτοτελής Μελέτη 78 Ασκήσεις, Εργασίες 70.5 Σύνολο Μαθήματος 187.5
Αξιολόγηση Φοιτητών	Τελική εξέταση (40%) που περιλαμβάνει: ερωτήσεις σχετικές με την σχεδίαση και ανάλυση αλγορίθμων και ιδιότητες αυτών ερωτήσεις κρίσεως Ασκήσεις - σχεδίαση, ανάλυση, ιδιότητες υλοποίηση αλγορίθμων (30%) Παρουσιάσεις σχετικών θεμάτων (30%)

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

• Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press, 1990. (επίσης μεταφρασμένο από τις Πανεπιστημιακές Εκδόσεις Κρήτης)
• Δομές δεδομένων, αλγόριθμοι και εφαρμογές c++, Sahnii Sartaj, Εκδόσεις α. Τζιόλα
• Αλγόριθμοι σε C++, μέρη 1-4: θεμελιώδεις έννοιες, δομές δεδομένων, ταξινόμηση, αναζήτηση, Robert Sedgewick, Εκδόσεις Κλειδάριθμος
• Αλγοριθμοι σε C, μέρη 1-4: θεμελιώδεις έννοιες, δομές δεδομένων, ταξινόμηση, αναζήτηση, Robert Sedgewick, Εκδόσεις Κλειδάριθμος
• Mark Allen Weiss, Data Structures & Algorithm Analysis in Java, Addison-Wesley
• Clifford A. Shaffer, Data Structures and Algorithm Analysis, ebook, http://people.cs.vt.edu/shaffer/Book/
• A. Aho, J. Hopcroft, J. Ullman, (1983). Data Structures and Algorithms, Addison-Wesley.
• Baase, S., Computer Algorithms - Introduction to Design and Analysis, Second Edition, , Addison Wesley, Reading, Massachusetts, 1988.
• Knuth, D., The Art of Computer Programming - Vol. 1 Fundamental Algorithm, Addison Wesley, Reading, Massachusetts, 1973.
• Knuth, D., The Art of Computer Programming - Vol. 2 SemiNumerical Algorithm, Addison Wesley, Reading, Massachusetts, 1973.
• Knuth, D., The Art of Computer Programming - Vol. 3 Sorting and Searching, Addison Wesley, Reading, Massachusetts, 1973.