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

Πληροφορίες

Κωδικός : ΥΠ25

Τύπος : Υποχρεωτικό

Εξάμηνο : 6

Μονάδες ECTS: 5

URL: https://eclass.hua.gr/courses/DIT110/

Αναμενόμενα Αποτελέσματα

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

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

Περιεχόμενο

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

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

Τρόπος Αξιολόγησης

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

Βιβλιογραφία

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

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