Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών


Πανεπιστήμιο Θεσσαλίας (Βόλος)


Disclaimer

Η παρούσα ιστοσελίδα δεν υποκαθιστά την τάξη. Θα ενημερώνεται ασύγχρονα και μη πλήρως

Περίληψη

  1. Το μάθημα θα διαπραγματευτεί:
    Βασικές έννοιες και προβλήματα Σχεδίασης και Ανάλυσης Αλγορίθμων
  2. Εστιάζει σε:
    Ασυμπτωτική, Πιθανοκρατική, Amortized Ανάλυση
    Αναζήτηση-Ταξινόμηση
    Δένδρα αναζήτησης, (μοντέρνο) Κατακερματισμό
    Τυχαιοκρατικούς αλγορίθμους
    Άπληστους αλγορίθμους
    Δυναμικό προγραμματισμό
    Γραμμικό προγραμματισμό
    Online αλγορίθμους
    Γραφηματο-θεωρητικούς αλγορίθμους (ελάχιστα μονοπάτια, ζευγνύοντα δένδρα, union-find)
    Ροές σε γραφήματα
    NP-Completeness
    Προσεγγιστικούς αλγορίθμους

Διδάσκων

Δημήτριος Κατσαρός

Βιβλιογραφία διδασκαλίας

Βιβλίο
Τίτλος Εισαγωγή στους Αλγορίθμους Introduction to Algorithms (3rd ed.)
Συγγραφείς Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Γλώσσα Ελληνική Αγγλική
Εδώ

Για όσους επιθυμούν να επεκτείνουν τις γνώσεις τους στο αντικείμενο των αλγορίθμων

Βιβλίο
Τίτλος Algorithm Design
Σχεδιασμός Αλγορίθμων
Approximation Algorithms
(Downloadable behing UTh' IP)
Probability and Computing
Randomization and Probabilistic Techniques
in Algorithms and Data Analysis
Algorithms The Algorithm Design Manual
(Downloadable behing UTh' IP)

και φυσικά τα έργα του "πατριάρχη" Donald Knuth.

Απαιτήσεις μαθήματος (για τους 2-ετείς φοιτητές ακ.έτους 2021-2022):

Απαιτήσεις μαθήματος (για τους μεγαλυτέρων ετών φοιτητές):


Δειγματικό υλικό του ακ.έτους 2020-2021.



Εργασία κωδικοποίησης

Ανακοίνωση της 'Εργασίας κωδικοποίησης': Project

Σειρές προβλημάτων

Ανακοίνωση της 'Σειράς-Προβλημάτων-01': Problem-Set01
Λύσεις της 'Σειράς-Προβλημάτων-01': Problem-Set01-Sols
Ανακοίνωση της 'Σειράς-Προβλημάτων-02': Problem-Set02
Ανακοίνωση της 'Σειράς-Προβλημάτων-03': Problem-Set03

Οι διαλέξεις θα πραγματοποιούνται στο Αμφ.1 (106)

Δευτέρα 15:00-17:00 και Πέμπτη 13:00-15:00

Πρόγραμμα διαλέξεων

Εβδομάδα Ημερομηνία Αντικείμενο διάλεξης Μελέτη ελλ. βιβλίο
1 28/02-03/03/2022 α) Εισαγωγή στην έννοια του αλγορίθμου
β) Insertion sort και Merge sort
γ) Ρυθμός αύξησης συναρτήσεων
Κεφ. 1
Κεφ. 2
Κεφ. 3
2 07-10/03/2022 α) Ασκήσεις (asymp. notation, Bubble sort, inversions counting)
β) Αλγόριθμοι Διαίρει-και-Βασίλευε (Binary search, Recurrences)
γ) Master theorem
Κεφ. 4
Binary Search demo
3 14-17/03/2022 α) Διαίρει-και-Βασίλευε: Strassen πολλαπλασιαμός πινάκων
β) Κάτω όριο των comparison-based αλγορίθμων ταξινόμησης
γ) (Deterministic) Quicksort
Κεφ. 4
Κεφ. 7
Κεφ. 8.1
QuickSort demo
4 21-24/03/2022 α) Randomized Quicksort. Πιθανοκρατική ανάλυσης μέσης επίδοσης του Randomized Quicksort
β) Bucket sort. Πιθανοκρατική ανάλυση
γ) Περίληψη βασικών δομών δεδομένων: Συνδεδεμένες Λίστες, (Κυκλικές) Ουρές, Δένδρα, Σωρός (Ταξινόμηση με σωρό)
Κεφ. 5
Κεφ. 6
Κεφ. 7
Κεφ. 8.4
Κεφ. 10
HeapSort demo
5 28-31/03/2022 α) Order statistics (i-th smallest, median)
β1) The Dictionary problem: Hashing
β2) The Dictionary problem: Cuckoo hashing
β3) The Dictionary problem: Bloom filter
β4) The Dictionary problem: B^(+)-δένδρα
Κεφ. 9
Κεφ. 11
Κεφ. 16
CuckooHashing demo (και ανάλυση)
BloomFilter demo
Bloom Filter πιθανότητα σφάλματος
6 04-07/04/2022 α) Άπληστοι αλγόριθμοι
α1) Knapsack problem (Fractional)
α2) Huffman encoding
α3) Interval Scheduling [proof: the greedy stays ahead]
α4) Optimal cache replacement with perfect knowledge of the future [proof: the exchange argument]
a5) Vertex cover
Κεφ. 16
Belady's optimal offline caching (και απόδειξη)
7 11-14/04/2022 α) Δυναμικός Προγραμματισμός
α1) Weighted Interval Scheduling
α2) Longest Common Subsequence
α3) 0/1 Knapsack
α4) Edit Distance
β) Γραμμικός Προγραμματισμός
β1) Weighted Vertex Cover
Κεφ. 15
Κεφ. 29 (έως 29.2)
Weighted Interval Scheduling
Longest Common Subsequence
Knapsack & String Alignment
Linear Programming
Traveling Salesman Problem and DP
8 02-05/05/2022 α) Graph-Theoretic αλγόριθμοι
α1) Depth/Breadth traversal
β) Minimum Spanning Tree
β1) Αλγόριθμος Kruskal
β2) Αλγόριθμος Prim
Κεφ. 22
Κεφ. 23
9 09-12/05/2022 Shortest-paths
Κεφ. 24
Bellman-Ford SPs, All-Pairs-SPs (Matrix, Floyd-Warshall)
10 16-19/05/2022 α) Maximum-flow
β) Maximum-flow/min-cut applications
Κεφ. 26
Ford-Furkeson demo
11 23-26/05/2022 α) NP and computational intractability
β) Polynomial-time reductions: By simple equivalence, By special case to general case, By encoding with gadgets
Κεφ. 34
about NP
12 30/05-02/06/2022 α) NP-completeness
β) Approximation algorithms
Κεφ. 34
Κεφ. 35
13 04/06/2022 Online (competitive) algorithms Κεφ. 17.3
Competitive algorithms


dkatsar AT e-ce DOT uth DOT gr
Τελευταία ενημέρωση: Δευ. 16 Μαΐου 2022