Εισαγωγή στη Θεωρία και Ανάλυση Αλγορίθμων

Περιγραφή θέματος

• Γενικά
  
  

  Γενικά

  Εισαγωγή στη Θεωρία και Ανάλυση Αλγορίθμων

  Διδάσκων : Χ. Παπαδόπουλος

  

  Περιγραφή: Εισαγωγή σε θεμελιώδεις αλγοριθμικές έννοιες και τεχνικές. Βασικά στοιχεία σχεδιασμού και ανάλυσης αλγορίθμων, αποδοτικότητα αλγορίθμων, ασυμπτωτικός συμβολισμός, ορθότητα αλγορίθμων, βασικές δομές δεδομένων, ουρές προτεραιότητας και εφαρμογή τους στην ταξινόμηση στοιχείων (heapsort).
  

  Μαθησιακοί Στόχοι Μαθήματος: Στόχος του μαθήματος είναι η μετάδοση γνώσεων στους σπουδαστές του τμήματωμ Μαθηματικών για την ανάλυση αλγορίθμων, την αποδοτικότητα, τον ασυμπτωτικός συμβολισμός. Οι συνηθισμένοι χρόνοι εκτέλεσης και οι βασικές δομές δεδομένων όπως: πίνακες, λίστες, στοίβες, ουρές. Ακόμα αναλύονται έννοιες όπως το ευσταθές ταίριασμα, ορθότητα σωρός και ουρά προτεραιότητας. Μέθοδος «Διαίρει και Βασίλευε»:Εφαρμογές σε ταξινόμηση στοιχείων, Επίλυση αναδρομικών σχέσεων. Γραφήματα και αλγόριθμοι γραφημάτων: Διάτρεξη γραφημάτων (BFS, DFS), Συνεκτικότητα, Τοπολογική διάταξη. Μέθοδοι «Απληστείας» και «Δυναμικού Προγραμματισμού»:Ελάχιστα σκελετικά δένδρα (αλγόριθμος Prim, αλγόριθμος Kruskal), Συντομότερες διαδρομές (αλγόριθμος Dijkstra, Ροή δικτύου), Χρονοπρογραμματισμός. Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα, NP-πληρότητα

  Λέξεις κλειδιά: Βασικές δομές δεδομένων. ασυμπτωτικός συμβολισμός, ευσταθές ταίριασμα, μέθοδος διαίρει και βασίλευε, ταξινόμηση στοιχείων, επίλυση αναδρομικών σχέσεων, αλγόριθμοι BFS και DFS, συνεκτικότητα, τοπολογική ταξινόμηση, ελάχιστα σκελετικά δένδρα, συντομότερες διαδρομές, μέθοιδοι απληστίας και δυναμικού προγραμματισμού, ΝΡ-πληρότητα.

  • Πληροφορίες για τις εργασίες Σελίδα
  • Πληροφορίες για τον τρόπο βαθμολόγησης του μαθήματος Σελίδα
  • Τι είναι οι AlgoFights Αρχείο
  • Ανακοινώσεις Ομάδα Συζητήσεων
• 1. Βασικά στοιχεία σχεδίασης & ανάλυσης αλγορίθμων
  
  

  1. Βασικά στοιχεία σχεδίασης & ανάλυσης αλγορίθμων

  Περιγραφή θεματικής ενότητας: Βασικά στοιχεία σχεδίασης & ανάλυσης αλγορίθμων. Εισαγωγικά θέματα του μαθήματος. Η έννοια της αποδοτικότητας ενός αλγορίθμου. Αντιπροσωπευτικά προβλήματα ως προς την πολυπλοκότητα χρόνου. Ορισμοί πολυωνυμικού και εκθετικού χρόνου.

  Λέξεις κλειδιά: Ταχύτητα επίλυσης προβλημάτων με Η/Υ 

  Ύλη βιβλιογραφίας:
  [KT]: Κεφάλαιο 2.1, 
  [CLRS]: Κεφάλαια 1.1, 1.2, 2.1, 2.2

  • Διαφάνειες 1 Αρχείο
  • AlgoFigts Ανακοίνωση Αποστολής 1: "Παράταιρη Μπίλια" Αρχείο
• 2. Ανάλυση αλγορίθμων
  
  

  2. Ανάλυση αλγορίθμων

  Περιγραφή θεματικής ενότητας : Ανάλυση αλγορίθμων, Αποδοτικότητα, Ασυμπτωτικός ρυθμός αύξησης και ασυμπτωτικοί συμβολισμοί. Ασυμπτωτικά όρια για κάποιες συνηθισμένες συναρτήσεις. Επισκόπηση Συνηθισμένων Χρόνων Εκτέλεσης. Εφαρμογές σε Κατάταξη Συναρτήσεων.

  Λέξεις κλειδιά : βήματα αλγορίθμου, ασυμπτωτικός χρόνος εκτέλεσης, αποδοτικός αλγόριθμος

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 2.2, 2.4 
  [CLRS]: Κεφάλαιο 3.1

  • Διαφάνειες 2 Αρχείο
  • AlgoFights Αποστολή 2: Παιχνίδι ερωτήσεων. Σελίδα
• 3. Συνηθισμένοι χρόνοι εκτέλεσης και δομές δεδομένων
  
  

  3. Συνηθισμένοι χρόνοι εκτέλεσης και δομές δεδομένων

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

  Λέξεις κλειδιά : πίνακες, λίστες, ουρές, στοίβες, χρόνοι εκτέλεσης αλγορίθμου

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 2.4, 2.5 
  [CLRS]: Κεφάλαια 3.2, 10.1, 11.1.

  • Διαφάνειες 3 Αρχείο
• 4. Ευσταθές ταίριασμα, ορθότητα, σωρός και ουρά προτεραιότητας
  
  

  4. Ευσταθές ταίριασμα, ορθότητα, σωρός και ουρά προτεραιότητας

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

  Λέξεις κλειδιά: σωρός και ουρά προτεραιότητας, ευσταθές ταίριασμα, ορθότητα, ανάλυση αλγορίθμου 

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 1.1, 2.3, 2.5 
  [CLRS]: Κεφάλαιο 6.

  • Διαφάνειες 4 Αρχείο
  • AlgoFights Αποστολή 3: Μερικά Αθροίσματα Σελίδα
• 5. Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων και επίλυση αναδρομικών σχέσεων
  
  

  5. Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων και επίλυση αναδρομικών σχέσεων

  Περιγραφή θεματικής ενότητας: Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων με συγχώνευση. Επίλυση αναδρομικών σχέσεων με τις μεθόδους εκδίπλωσης αναδρομής (δέντρο αναδρομής), Επαναληπτική μέθοδος – ανάπτυξη διαδρομής, Μέθοδος αντικατάστασης – σωστής πρόβλεψης, αλλαγής μεταβλητών, Βασικό Θεώρημα Αναδρομών (Μaster Theorem), Γραμμικές αναδρομικές σχέσεις. Κάτω Φράγματα σε Αναζητήσεις και Ταξινομήσεις. Μέτρηση αντιστροφών. Πλησιέστερο ζεύγος σημείων. 

  Λέξεις κλειδιά: αποδοτικοί αλγόριθμοι ταξινόμησης, μέθοδος διαίρει και βασίλευε, τρόποι επίλυσης αναδρομικών σχέσεων

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 5.1, 5.2, 5.3, 5.4
  [CLRS]: Κεφάλαιο 2.3, 4.1, 4.2, 4.3,  7.1, 7.2

  • Διαφάνειες 5 Αρχείο
  • AlgoFights Αποστολή 4: Συμμετοχή σε ανοιχτή συζήτηση Σελίδα
• 6. Βασικοί αλγόριθμοι γραφημάτων
  
  

  6. Βασικοί αλγόριθμοι γραφημάτων

  Περιγραφή θεματικής ενότητας: Βασικές έννοιες και ιδιότητες γραφημάτων. Αλγόριθμοι γραφημάτων: διάσχιση κατά πλάτος (BFS), διάσχιση κατά βάθος (DFS). Αποδοτική υλοποίηση των αλγορίθμων και πρακτικές εφαρμογές. Διμερή γραφήματα. Κατευθυνόμενα Άκυκλα Γραφήματα. Συνεκτικότητα γραφημάτων και τοπολογική ταξινόμηση. 

  Λέξεις κλειδιά: διάσχιση κατά πλάτος (BFS), διάσχιση κατά βάθος (DFS), τοπολογική ταξινόμηση

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 3.1, 3.2, 3.3, 3.4, 3.5, 3.6
  [CLRS]: Κεφάλαιο 22.1, 22.2, 22.3, 22.4, 22.5

  • Διαφάνειες 6 Αρχείο
  • AlgoFights Αποστολή 5: Παιχνίδι με γράφους Αρχείο
• 7. 'Απληστοι αλγόριθμοι, χρονοπρογραμματισμός και συντομότερες διαδρομές (Dijkstra)
  
  

  7. 'Απληστοι αλγόριθμοι, χρονοπρογραμματισμός και συντομότερες διαδρομές (Dijkstra)

  Περιγραφή θεματικής ενότητας: 'Απληστοι αλγόριθμοι. Χρονοπρογραμματισμός Διαστημάτων. Ορθότητα άπληστων αλγορίθμων. Διαμέριση Χρονικών Διαστημάτων. Χρονοπρογραμματισμός για Ελαχιστοποίηση Καθυστέρησης. Στρατηγικές Ανάλυσης Άπληστων Αλγορίθμων και παραδείγματα. Συντομότερες Διαδρομές σε Γραφήματα και ο αλγόριθμος του Dijkstra. 

  Λέξεις κλειδιά: χρονοπρογραμματισμός, άπληστη επιλογή, συντομότερη διαδρομή, ο αλγόριθμος του Dijkstra

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 4.1, 4.2, 4.4
  [CLRS]: Κεφάλαιο 16.1, 16.2, 16.5, 24.3

  • Διαφάνειες 7 Αρχείο
  • AlgoFights Αποστολή 6: Παιχνίδι με αλγόριθμους Αρχείο
• 8. Ελάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal), κωδικοποίηση Huffman
  
  

  8. Ελάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal), κωδικοποίηση Huffman

  Περιγραφή θεματικής ενότητας: Ελάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal). Ιδιότητα αποκοπής και η ιδιότητα του κύκλου. Αποδοτική υλοποίηση των αλγορίθμων. Ανάλυση και χαρακτηρισμός των αλγορίθμων. H δομή δεδομένων Union-Find. Κώδικες Huffman και Συμπίεση Δεδομένων.

  Λέξεις κλειδιά: άπληστη επιλογή, σκελετικό δένδρο, ελαφρύτερο σκελετικό δένδρο, κωδικοποίηση χαρκτήρων κατά Huffman

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 4.5, 4.6, 4.8
  [CLRS]: Κεφάλαιο 23.1, 23.2, 16.3

  • Διαφάνειες 8 Αρχείο
  • AlgoFights Αποστολή 7: Παιχνίδι με αλγόριθμους 2 Αρχείο
• 9. Μέθοδος "δυναμικού προγραμματισμού": Ροή δικτύου, χρονοπρογραμματισμός και σακίδια
  
  

  9. Μέθοδος "δυναμικού προγραμματισμού": Ροή δικτύου, χρονοπρογραμματισμός και σακίδια

  Περιγραφή θεματικής ενότητας: Μέθοδος "δυναμικού προγραμματισμού". Σταθμισμένος Χρονοπρογραμματισμός Διαστημάτων. Τμηματοποιημένα Ελάχιστα Τετράγωνα. Αθροίσματα Υποσυνόλων και Σακίδια.  Ευθυγράμμιση Ακολουθίας. Συντομότερα Μονοπάτια – Αλγόριθμος του Bellman-Ford. Εύρεση αρνητικών κύκλων σε γραφήματα. 

   Ροή δικτύου, χρονοπρογραμματισμός και σακίδια

  Λέξεις κλειδιά: δυναμικός προγραμματισμός, χρονοπρογραμματισμός, πρόβλημα του σακιδίου (Knapsack)

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 6.1, 6.2, 6.3, 6.4, 6.6, 6.8, 6.10
  [CLRS]: Κεφάλαιο 15.1, 15.2, 15.3, 15.4, 15.5, 24.1

  • Διαφάνειες 9 Αρχείο
  • AlgoFights Αποστολή 8: Παιχνίδι με αλγόριθμους 3 Αρχείο
• 10. Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα
  
  

  10. Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα

  Περιγραφή θεματικής ενότητας: Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα. Κατηγοριοποίηση προβλημάτων ως προς την Υπολογισιμότητα. Αναγωγές Πολυωνυμικού Χρόνου. Αναγωγή από Απλή Ισοδυναμία. Αναγωγή από ειδική περίπτωση σε γενική περίπτωση. Αναγωγή με μικροεργαλεία (gadgets). Η κλάση ΝΡ. ΝΡ-πλήρη προβλήματα. 

  Λέξεις κλειδιά: υπολογιστική πολυπλοκότητα, οι κλάσεις P και NP, ΝΡ-πληρότητα, αναγωγή πολυωνυμικού χρόνου

  Ύλη Βιβλιογραφίας: 
  [KT]: Κεφάλαιο 8
  [CLRS]: Κεφάλαιο 34 (Β' τόμος)

  • Διαφάνειες 10 Αρχείο
• 11. Επανάληψη
  
  

  11. Επανάληψη

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

  Λέξεις κλειδιά: επανάληψη της ύλης

   

  • Διαφάνειες 11 Αρχείο
• Βιβλιογραφία
  
  

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

  Επιλογή 1:
  [KT] J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008 (4η επιλογή στον Εύδοξο).

  Επιλογή 2:
  [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.

  Επιλογή 3:
  [DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Αλγόριθμοι, ελληνική έκδοση,Εκδόσεις Κλειδάριθμος, 2008
• Επιπρόσθετο Υλικό
  
  

  Επιπρόσθετο Υλικό

  • Παροράματα του βιβλίου "Σχεδιασμός Αλγορίθμων" των J. Kleinberg & E. Tardos Αρχείο
  • Σημειώσεις για Επίλυση Αναδρομικών Σχέσεων, του κ. Χρήστου Δ. Ζαρολιάγκη Αρχείο
  • Σημειώσεις-Ασκήσεις-Video αντίστοιχου μαθήματος στο ΜΙΤ (καλύπτεται περίπου το 75% της ύλης) URL
  • Λυμένες ασκήσεις: Ασυμπτωτικός συμβολισμός και διάταξη συναρτήσεων Αρχείο
  • Λυμένες ασκήσεις: Το πρόβλημα του ευσταθούς ταιριάσματος (1) Αρχείο
  • Λυμένες ασκήσεις: Το πρόβλημα του ευσταθούς ταιριάσματος (2) Αρχείο
• Εργασίες 2012-2013
  
  

  Εργασίες 2012-2013

  • Εκφώνηση 1oυ σετ Ασκήσεων Αρχείο
  • Εκφώνηση 2ου Σετ Ασκήσεων Αρχείο
• Διαλέξεις
  
  

  Διαλέξεις

  • • Διάλεξη 1 : Βασικά στοιχεία σχεδίασης & ανάλυσης αλγορίθμων
    • Διάλεξη 2 : Ανάλυση αλγορίθμων, Αποδοτικότητα, Ασυμπτωτικός ρυθμός αύξησης
    • Διάλεξη 3 : Συνηθισμένοι χρόνοι εκτέλεσης, και δομές δεδομένων πίνακες, λίστες, ουρές, στοίβες
    • Διάλεξη 4 : Ευσταθές ταίριασμα, ορθότητα, σωρός και ουρά προτεραιότητας
    • Διάλεξη 5 : Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων και επίλυση αναδρομικών σχέσεων
    • Διάλεξη 6 : Βασικοί αλγόριθμοι γραφημάτων
    • Διάλεξη 7 : 'Απληστοι αλγόριθμοι, χρονοπρογραμματισμός και συντομότερες διαδρομές (Dijkstra)
    • Διάλεξη 8 : Ελάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal), κωδικοποίηση Huffman
    • Διάλεξη 9 : Μέθοδος "δυναμικού προγραμματισμού", Ροή δικτύου, χρονοπρογραμματισμός και σακίδια
    • Διάλεξη 10 : Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα
    • Διάλεξη 11 : Επανάληψη με παραδείγματα και ασκήσεις