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

Διδάσκων: Θεοχάρης Μαλαμάτος

Διαλέξεις: Πέμπτη 11-2μμ, Αίθ. Ι4 και Παρασκευή 11-2μμ, Αίθ. Ι13

Περιγραφή

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

Διαλέξεις

Θέματα Διαλέξεων

 Αναφορά
Dasgupta et al.		 Αναφορά
Kleinberg, Tardos		 Αναφορά
Cormen et al.		 Αναφορά
Goodrich, Tamassia

1

Εισαγωγή, Αλγόριθμοι και Υπολογιστικά Προβλήματα, Ανάλυση Αλγορίθμων, Ασυμπτωτικοί Συμβολισμοί

Κεφ. 0

1.2, 2.1-2.2, 2.4-2.5

Κεφ. 1, 2

1.1, 1.2

2

Γραφήματα: Αναπαραστάσεις, Αναζήτηση κατά Πλάτος, Αναζήτηση σε Βάθος

Κεφ. 3

3.1-3.3

22.1, 22.2, 22.3

13.1-13.3

3

Γραφήματα: Τοπολογική Ταξινόμηση, Συνδεδεμένες Συνιστώσες, Ισχυρά Συνδεδεμένες Συνιστώσες

Κεφ. 3

3.5-3.6

22.4, 22.5

13.4

4

Διαίρει-και-Βασίλευε: Συγχωνευτική Ταξινόμηση, Αναδρομικές Σχέσεις

Κεφ. 2

5.1-5.2

Κεφ. 2, 3, 4.1-4.3

8.1, 11.1

5

 Διαίρει-και-Βασίλευε: Διάμεσος και Επιλογή

 Κεφ. 2

 13.5

 9.2

9.2

6

Διαίρει-και-Βασίλευε: Πολλαπλασιασμός Ακεραίων, Πολλαπλασιασμός Πινάκων με τον Αλγόριθμο του Strassen

Κεφ. 2

5.5

28.2, 2.1, 8.1

11.2, 11.3

7

 Ορθότητα με Χρήση Αναλλοίωτων Συνθηκών, Κάτω Φράγμα Ταξινόμησης Κεφ. 2

 Σημ.

 2.1, 8.1

1.2.3, 8.3, 9.1

8

Άπληστοι Αλγόριθμοι: Επιλογή Δραστηριοτήτων, Κλασματικό Σακίδιο

Κεφ. 5

4.1

16.1, 16.2

10.1, 10.2

9

Άπληστοι Αλγόριθμοι: Κώδικες Huffman

Κεφ. 5

4.8

16.3

10.3

10

Άπληστοι Αλγόριθμοι σε Γραφήματα: Ελάχιστο Συνδετικό Δέντρο: Αλγόριθμοι του Kruskal και του Prim

Κεφ. 5

4.5

23.2

15.1-15.3

11

Άπληστοι Αλγόριθμοι σε Γραφήματα: Συντομότερες Διαδρομές: Αλγόριθμος του Dijkstra

Κεφ. 4

4.4

24.3

14.1-14.2

12

Δυναμικός Προγραμματισμός: Μέγιστη Κοινή Υπακολουθία, 0-1 Σακίδιο

Κεφ. 6

6.2, 6.4

15.4

12.5-12.6

13

Δυναμικός Προγραμματισμός: Συντομότερες Διαδρομές: Αλγόριθμος των Bellman-Ford, Αλγόριθμος του Floyd

Κεφ. 4, 6

6.8

24.1, 25.2

14.3, 14.5

14

Δυναμικός Προγραμματισμός: Πολλαπλασιασμός Αλυσίδας Πινάκων

Κεφ. 6

Σημ.

15.2

12.1

15

NP-πλήρη Προβλήματα, Αναγωγές Πολυωνυμικού Χρόνου

Κεφ. 8

8.1-8.5

34

Κεφ. 17

16

Προσεγγιστικοί Αλγόριθμοι, Πιθανοτικοί Αλγόριθμοι, Υπολογιστική Γεωμετρία

Κεφ. 9, 2

Κεφ. 11, 13.5

Κεφ. 35, 7, 33

Κεφ. 18, 19, 22

Βιβλία και Διαφάνειες Μαθήματος

Τα δωρεάν συγγράμματα είναι τα εξής:

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

Βαθμολογία

Ο βαθμός του μαθήματος υπολογίζεται κατά τα 6/10 από το βαθμό στην τελική γραπτή εξέταση και κατά τα 4/10 από τον μέσο όρο των βαθμών στις ασκήσεις του μαθήματος. Η εξέταση είναι επιτυχής όταν ο βαθμός της γραπτής εξέτασης και των ασκήσεων είναι αμφότεροι μεγαλύτεροι ή ίσοι του πέντε.

Ασκήσεις

Κατά τη διάρκεια του εξαμήνου θα δοθούν μία σειρά από υποχρεωτικές θεωρητικές και προγραμματιστικές ασκήσεις. Η ανακοίνωση των ασκήσεων και των σχετικών ημερομηνιών παράδοσης θα γίνεται στα μαθήματα και μέσω email. Τα θέματα των ασκήσεων θα τοποθετούνται στην πλατφόρμα eclass.

Σύνδεσμοι