Αλγόριθμοι και Πολυπλοκότητα
Ακ. Έτος 2015-2016

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

 

"People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then, they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically." - Donald Knuth

Γενικές Πληροφορίες
Διδάσκων: Τσίχλας Κωνσταντίνος
Email - URL - Τηλ.: tsichlas@delab.csd.auth.gr - http://delab.csd.auth.gr/~tsichlas/ - 2310991934
Ώρες Διαλέξεων:  Πέμπτη, 10-13, Αίθουσα Γ

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Περιγραφή

Οι αλγόριθμοι αποτελούν το θεμελιώδες εργαλείο και συστατικό της Πληροφορικής. Είναι στην ουσία ότι οι αριθμοί είναι για τα Μαθηματικά. Ως εκ τούτου οι επιστήμονες Πληροφορικής απαιτείται να έχουν γνώσεις για σύγχρονες μεθόδους σχεδίασης και ανάλυσης αλγορίθμων, δηλαδή για μεθόδους επίλυσης προβλημάτων.

Θα ασχοληθούμε με προχωρημένα θέματα που αφορούν τις Δομές Δεδομένων και τους Αλγόριθμους. Όσον αφορά τις Δομές Δεδομένων, θα ασχοληθούμε με επιμερισμένη ανάλυση, ανταγωνιστική ανάλυση, δυναμική βελτιστότητα και τέλος με τεχνικές που εκμεταλλεύονται το πεπερασμένο μήκος λέξης (π.χ. Van Emde Boas δένδρα).

Όσον αφορά το κομμάτι των αλγορίθμων θα ασχοληθούμε με ανταγωνιστική ανάλυση, εκθετικούς αλγόριθμους, προσεγγιστικούς αλγόριθμους, τυχαιοποιημένους αλγόριθμους και με την τεχνική της τοπικής αναζήτησης.

Αξιολόγηση Μαθήματος

Εκτός από την τελική εξέταση θα περιλαμβάνει μία σειρά προγραμματιστικών και θεωρητικών ασκήσεων (προαιρετικές).

 Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Ανακοινώσεις

1. Εδώ θα βρείτε την 1η προαιρετική άσκηση.

2. Εδώ θα βρείτε τους βαθμούς της 1ης άσκησης.

3. Θα παρουσιασθούν τρία θέματα στα πλαίσια του μαθήματος από τους φοιτητές (παρουσιάσεις των 25-30 λεπτών). Όποιος θέλει να παρουσίασει ένα εκ των θεμάτων 2 και 3 ή κάποιο άλλο σχετικό θέμα να επικοινωνήσει μαζί μου.

1. Βιολογικός Υπολογισμός (δόθηκε)

2. Κβαντικός Υπολογισμός (κεφάλαια 9-15 από το βιβλίο του Aaronson - Προφανώς θα παρουσιασθούν κάποιο από αυτό το υλικό)

3. Στα όρια της φιλοσοφίας (κεφάλαια 18-21)

4. (22/12/2015) Εδώ θα βρείτε την 2η προαιρετική άσκηση.

5. (22/12/2015) Οι παρουσιάσεις των εργασιών θα γίνουν την εβδομάδα 11-15/1 ή την εβδομάδα 18-22/1/2016. Το πρώτο θέμα έχει δοθεί. Το τρίτο θέμα επίσης. Ενώ ένας ακόμα φοιτητής θα κάνει ένα θέμα με τίτλο "Hardness for Easy Problems".

6. Στην 13η διάλεξη θα γίνουν οι παρουσιάσεις των φοιτητών ενώ θα κλείσουμε και την ύλη με ένα παράδειγμα προσεγγιστικού/τυχαιοποιημένου αλγόριθμου.

7. (4/2/2016) Εδώ θα βρείτε τα θέματα και ενδεικτικές λύσεις. Εδώ θα βρείτε την τελική βαθμολογία (με τις βαθμολογίες των ασκήσεων και των παρουσιάσεων).


Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό 

Ημερολόγιο Μαθήματος
Διάλεξη Ημερομηνία Ύλη Εβδομάδας Υλικό
1η 1/10/2015 Εισαγωγή στο Μάθημα Διαφάνειες
2η 8/10/2015 Οι κλάσεις P και NP - Συμπληρωματικά Προβλήματα (σελ. 1-38 στις διαφάνειες) Διαφάνειες
3η 15/10/2015 Η κλάση co-NP, Αναγωγή πολυωνυμικού χρόνου, Παραδείγματα(σελ. 39-80 στις διαφάνειες από 8/10)  
4η 22/10/2015 NP-πλήρη προβλήματα και NP-δυσχερή προβλήματα, Αναγωγές (σελ. 81-126 από
διαφάνειες 8/10)		  
5η 29/10/2015 Έγιναν οι υπόλοιπες διαφάνειες (μερικές απλά αναφέρθηκαν) από τις 8/10. Συγκεκριμένα, δόθηκε αλγόριθμος για το 2SAT και δόθηκε η αναγωγή του 3SAΤ στο πρόβλημα του αθροίσματος υποακολουθίας. Έγινε όλο το Κεφάλαιο 8 του βιβλίου.
6η 5/11/2015 Χωρική Πολυποκότητα, PSPACE, Το πρόβλημα της Γεωγραφίας (σελ. 1-28) Διαφάνειες
7η 12/11/2015 Το πρόβλημα της Ανταγωνιστικής Χωροθέτησης Υπηρεσιών και το Πρόβλημα Σχεδιασμού. Έγινε το Κεφάλαιο 9 του βιβλίου.
  19/11/2015 Δεν θα γίνει μάθημα λόγω προβλήματος υγείας του διδάσκοντα
8η 26/11/2015 Επέκταση των Ορίων Επιλυσιμότητας (10.1 και 10.2 από βιβλίο) Διαφάνειες
9η 3/12/2015 Προσεγγιστικοί Αλγόριθμοι: Το πρόβλημα Εξισορρόπησης Φορτίου (11.1 από βιβλίο)  
10η 10/12/2015 Πρόβλημα Επιλογής Κέντρων (11.2) και Προσέγγιση μέσω Γραμμικού Προγραμματισμού (11.6) Διαφάνειες
11η 17/12/2015 PTAS για το πρόβλημα του Σακιδίου (11.8) Εισαγωγή στους Τυχαιοποιημένους Αλγόριθμους - Το πλειοψηφικό στοιχείο Διαφάνειες
12η 14/1/2016 Το Επαναλαμβανόμενο Στοιχείο, Επίλυση Ανταγωνισμού, Καθολική Ελάχιστη Αποκοπή
13η 21/1/2016 Το Πρόβλημα MAX 3-SAT, Παρουσιάσεις Φοιτητών: Ελεύθερη Βούληση, Δυσκολία Πολυωνυμικών Προβλημάτων, Μοριακός Υπολογισμός  

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Χρήσιμο Υλικό

Τα βασικά εγχειρίδια του μαθήματος είναι:

1. J. Kleinberg and E. Tardos: Σχεδιασμός Αλγορίθμων, Κλειδάριθμος, 2008.

Τα ακόλουθα βιβλία και ιστότοποι είναι αρκετά χρήσιμοι για το μάθημα.

  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein: Εισαγωγή στους Αλγόριθμους, Πανεπιστημιακές Εκδόσεις Κρήτης, 2010.

  2. Α. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.

  3. Παναγιώτης Μποζάνης: "Αλγόριθμοι - Σχεδιασμός και Ανάλυση", Εκδόσεις Τζιόλα, 2003.

  4. Robert Sedgewick and Philippe Flajolet: "An Introduction to the Analysis of Algorithms", Addisson Wesley, 1996.

  5. Steven Skienna: "The Algorithm Design Manual" Springer-Verlag, 1998.

  6. Anany Levitin: "Introduction to the Design and Analysis of Algorithms", Addison Wesley, 2003. (Μετάφραση από τις Εκδόσεις Τζιόλα, 2008.)

  7. Π.Δ. Μποζάνης. Προβλήματα και Ασκήσεις στους Αλγόριθμους. Εκδόσεις Τζιόλα, 2009.

 

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό