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


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


Disclaimer

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

Περίληψη

  1. Το μάθημα θα διαπραγματευτεί:
    Έννοιες και ζητήματα Σχεδίασης και Ανάλυσης Αλγορίθμων
  2. Εστιάζει σε:
    Ασυμπτωτική, Πιθανοκρατική Ανάλυση
    Αλγορίθμους Αναζήτησης, Ταξινόμησης, Εύρεσης προτύπου σε συμβολοσειρές
    Αλγορίθμους και Δομές Δεδομένων για το πρόβλημα του Λεξικού (B+-δένδρα, Bloom filters, Cuckoo hashing)
    Άπληστους αλγορίθμους (σε Caching, Scheduling, Independent/Dominating Sets)
    Βασικούς αλγορίθμους Υπολογιστικής Γεωμετρίας (πλησιέστεροι γείτονες, κυρτό περίβλημα)
    Δυναμικό προγραμματισμό
    Γραμμικό προγραμματισμό
    Γραφηματο-θεωρητικούς αλγορίθμους (ελάχιστα μονοπάτια, ζευγνύοντα δένδρα, ροές)
    NP-Completeness
    Προσεγγιστικούς αλγορίθμους
    Online αλγορίθμους
  3. Μετά το πέρας του μαθήματος, όσοι επέτυχαν θα δύνανται να:
    Σχεδιάζουν αποτελεσματικούς και αποδοτικούς αλγορίθμους
    Υλοποιούν αλγορίθμους λαμβάνοντας υπόψη τις απαιτήσεις του προβλήματος και τους διαθέσιμους υπολογιστικούς πόρους
    Χρησιμοποιούν δομές δεδομένων κατάλληλες για την υλοποίηση του εκάστοτε αλγορίθμου
    Αναπτύσουν νέες αλγοριθμικές λύσεις σε προκύπτοντα νέα προβλήματα
    Αποτιμούν τα θεωρητικά όρια δεδομένων αλγορίθμων
    Αναλύουν την συμπεριφορά και επίδοση δεδομένων αλγορίθμων, σε σχέση με την δύναμη και τις αδυναμίες των
    Αναγνωρίζουν την ομοιότητα μεταξύ διαφορετικών προβλημάτων, οδηγούμενοι στην ανάλυση της δυσκολίας των προβλημάτων

Διδάσκων

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

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

Βιβλίο
Τίτλος Εισαγωγή στους Αλγορίθμους 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
Σχεδιασμός Αλγορίθμων
Algorithms Illuminated, Parts 1-4
Approximation Algorithms
(Downloadable behing UTh' IP)
Probability and Computing
Randomization and Probabilistic Techniques
in Algorithms and Data Analysis
Algorithms

και φυσικά τα έργα του Donald Knuth.

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

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





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

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

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

Ανακοίνωση της 'Σειράς-Προβλημάτων-01': Problem-Set01

Οι διαλέξεις θα ξεκινήσουν την Πέμπτη 07 Μαρτίου 2024

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

Δευτέρα 18:00-20:00 και Πέμπτη 18:00-20:00

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

Εβδομάδα Ημερομηνία Αντικείμενο διάλεξης Μελέτη ελλ. βιβλίο
1 07/03/2024 α) Εισαγωγή στην έννοια του αλγορίθμου
β) Insertion sort και Merge sort
γ) Ρυθμός αύξησης συναρτήσεων
Κεφ. 1
Κεφ. 2
Κεφ. 3
I2A_SLIDES_SORTING
2 11-14/03/2024 α) Ασκήσεις
β) Αλγόριθμοι Διαίρει-και-Βασίλευε (Binary search, Recurrences)
γ) Master theorem, Akra-Bazzi theorem
Κεφ. 4
Binary Search demo
I2A_SLIDES_MASTER
Akra-Bazzi theorem
3 21/03/2024 α) Διαίρει-και-Βασίλευε: Strassen πολλαπλασιαμός πινάκων
β) Κάτω όριο των comparison-based αλγορίθμων ταξινόμησης
γ) (Deterministic) Quicksort
Κεφ. 4
Κεφ. 7
Κεφ. 8.1
MergeSort demo, MergeSort code
QuickSort demo
I2A_SLIDES_DIVIDE_and_CONQUER
4 28/03/2024 α) Quicksort. Ανάλυση Μέσης Περίπτωσης
β) Υπολογιστική Γεωμετρία: Εύρεση του Πλησιεστέρου Ζεύγους Σημείων
γ) Bucket sort. Πιθανοκρατική ανάλυση
Κεφ. 5
Κεφ. 7
Κεφ. 8.4
Κεφ. 33.4
Average case analysis of Quicksort
Closest Pair of Points
HeapSort demo
5 01-04/04/2024 α) Order statistics (i-th smallest, median)
β1) The Dictionary problem: Cuckoo hashing
β2) The Dictionary problem: Bloom filter
β3) The Dictionary problem: B^(+)-δένδρα
Κεφ. 9
Κεφ. 18
CuckooHashing demo (και ανάλυση)
BloomFilter demo
Bloom Filter πιθανότητα σφάλματος
6 08-11/04/2024 α) Άπληστοι αλγόριθμοι
α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) Dominating Sets
Κεφ. 16
Greedy algorithms: Interval scheduling, Interval partitioning, Shortest-paths
Belady's optimal offline caching (και απόδειξη)
7 15-18/04/2024 α) Δυναμικός Προγραμματισμός
α1) Weighted Interval Scheduling
α2) Longest Common Subsequence
α3) 0/1 Knapsack
α4) Edit Distance
β) Γραμμικός Προγραμματισμός
β1) Weighted Vertex Cover
γ) Ταύτιση συμβολοσειρών
γ1) Αλγόριθμοι: Απλοϊκός, Morris-Pratt, Knuth-Morris-Pratt
Κεφ. 15
Κεφ. 29 (έως 29.2)
Κεφ. 32 (32.1, 32.4)
Weighted Interval Scheduling
Longest Common Subsequence
Knapsack & String Alignment
0/1 Knapsack animation
Linear Programming
Linear Programming in Matlab
Traveling Salesman Problem and DP
Pattern matching: Naive, Morris-Pratt, Knuth-Morris-Pratt
8 22-25/04/2024 α) Graph-Theoretic αλγόριθμοι
α1) Depth/Breadth traversal
β) Minimum Spanning Tree
β1) Αλγόριθμος Kruskal
β2) Αλγόριθμος Prim
Κεφ. 22
Κεφ. 23
9 13-16/05/2024 Shortest-paths
Κεφ. 24
Κεφ. 25
Bellman-Ford SPs, All-Pairs-SPs (Matrix, Floyd-Warshall)
10 20-23/05/2024 α) Maximum-flow
β) Maximum-flow/min-cut applications
Κεφ. 26
Ford-Furkeson demo
11 27-30/05/2024 α) NP and computational intractability
β) Polynomial-time reductions: By simple equivalence, By special case to general case, By encoding with gadgets
Κεφ. 34
about NP
12 03-06/06/2024 α) NP-completeness
β) Approximation algorithms
Κεφ. 34
Κεφ. 35
Approximation algorithms (Load balancing, set cover)
Approximation algorithms
13 ΑΠΟ ΑΝΑΠΛΗΡΩΣΗ α) Υπολογιστική Γεωμετρία: Εύρεση του Κυρτού περιβλήματος (convex hull) συνόλου σημείων
β) Online (competitive) algorithms
Κεφ. 17.3
Κεφ. 33.3
Convex Hull - Graham scan
Competitive algorithms


dkatsar AT e-ce DOT uth DOT gr
Τελευταία ενημέρωση: Τετ. 20 Μαρ. 2024