Cheat sheet

Η εξέταση του K17 είναι χωρίς βοηθήματα — αυτή είναι σελίδα μελέτης, όχι τυπολόγιο που σου δίνεται μέσα στην αίθουσα. Χρησιμοποίησέ την για να ξαναθυμηθείς γρήγορα ορισμούς και βασικά εργαλεία. Άσε σχόλιο σε όποια εγγραφή σε δυσκόλεψε.

Ασυμπτωτική ανάλυση

2 εγγραφές

Ορισμός O, Θ, Ω

L02 · Ασυμπτωτική ανάλυση

f (n) = O (g (n)) ⟺ \exists c, n_{0} > 0 : f (n) \leq c g (n) \forall n \geq n_{0}

f (n) = Ω (g (n)) ⟺ \exists c, n_{0} > 0 : f (n) \geq c g (n) \forall n \geq n_{0}

f (n) = Θ (g (n)) ⟺ f = O (g) \land f = Ω (g)

Ιεραρχία ρυθμού αύξησης

L02 · Ασυμπτωτική ανάλυση

1 ≺ lo g lo g n ≺ lo g n ≺ n^{ϵ} ≺ n ≺ n lo g n ≺ n^{2} ≺ n^{3} ≺ 2^{n} ≺ n! ≺ n^{n}

Διαίρει και κυρίευε

1 εγγραφές

Master Theorem

L03 · D&C I (mergesort, master)

Για $T (n) = a T (n / b) + f (n)$ με $a \geq 1, b > 1$ :

Case 1: f (n) = O (n^{l o g_{b} a - ϵ}) ⟹ T (n) = Θ (n^{l o g_{b} a})

Case 2: f (n) = Θ (n^{l o g_{b} a}) ⟹ T (n) = Θ (n^{l o g_{b} a} lo g n)

Case 3: f (n) = Ω (n^{l o g_{b} a + ϵ}) + regularity ⟹ T (n) = Θ (f (n))

Γραφήματα

4 εγγραφές

Dijkstra — συντομότερες διαδρομές

L09 · Γραφήματα IV (MST)

Άπληστος: επέκτεινε το εξερευνημένο σύνολο $S$ κατά την κορυφή με το ελάχιστο $π (v) = min_{u \in S} {d (u) + ℓ_{uv}}$ .

Με δυαδικό σωρό: $O (m lo g n)$ . Μόνο για θετικά βάρη.

Ιδιότητα αποκοπής (ΕΕΔ)

L09 · Γραφήματα IV (MST)

Για κάθε αποκοπή $S \subset V$ , η ακμή ελάχιστου κόστους στο σύνολο ακμών αποκοπής ανήκει στο ΕΕΔ.

Ιδιότητα κύκλου (ΕΕΔ)

L09 · Γραφήματα IV (MST)

Για κάθε κύκλο $C$ , η ακμή μέγιστου κόστους στον $C$ δεν ανήκει στο ΕΕΔ.

Prim & Kruskal (ΕΕΔ)

L09 · Γραφήματα IV (MST)

Prim: μεγάλωσε ένα δέντρο από μία κορυφή, πρόσθεσε τη φθηνότερη ακμή αποκοπής.

Kruskal: ακμές σε αύξουσα σειρά κόστους, πρόσθεσε αν δεν κλείνει κύκλο (με union-find).

Και οι δύο: $O (m lo g n)$ .

Δομές δεδομένων

3 εγγραφές

Δυαδικός σωρός — δείκτες πίνακα

L10 · Δομές δεδομένων

parent (i) = ⌊ i /2 ⌋, left (i) = 2 i, right (i) = 2 i + 1

Ιδιότητα διάταξης: $key (parent) \leq key (child)$ — η ρίζα είναι το ελάχιστο.

Ουρά προτεραιότητας — πολυπλοκότητες

L10 · Δομές δεδομένων

$FindMin$ : $O (1)$ . $Insert$ , $ExtractMin$ , $decreaseKey$ : $O (lo g n)$ (heapify-up / heapify-down). Heapsort: $O (n lo g n)$ .

Union-Find (ξένα σύνολα)

L10 · Δομές δεδομένων

Κάθε σύνολο = κατευθυνόμενο δέντρο με ρίζα = αντιπρόσωπο. Union by size: βάθος $\leq lo g n$ .

Με path compression: $O (α (n))$ ανά πράξη — πρακτικά σταθερό.

Άπληστοι αλγόριθμοι

5 εγγραφές

Χρονοπρογραμματισμός διαστημάτων

L11 · Greedy I (interval scheduling)

Μέγιστο πλήθος συμβατών εργασιών — κριτήριο: μικρότερος χρόνος λήξης. $O (n lo g n)$ . Απόδειξη: «ο άπληστος προηγείται».

Διαμέριση διαστημάτων

L11 · Greedy I (interval scheduling)

Ελάχιστο πλήθος μηχανών = βάθος (μέγιστα ταυτόχρονα διαστήματα). Κριτήριο: μικρότερος χρόνος έναρξης.

Ελάχιστη μέγιστη καθυστέρηση

L12 · Greedy II (lateness, topo sort)

Καθυστέρηση $ℓ_{j} = max {0, f_{j} - d_{j}}$ . Κριτήριο: Earliest Deadline First (αύξουσα προθεσμία).

Απόδειξη: exchange argument — αντιμετάθεση αντιστροφών.

Τοπολογική διάταξη

L12 · Greedy II (lateness, topo sort)

Υπάρχει αν και μόνο αν το γράφημα είναι DAG. Αλγόριθμος: βγάζε επανειλημμένα κορυφή χωρίς εισερχόμενες ακμές — $O (m + n)$ .

Κωδικοποίηση Huffman

L13 · Greedy III (Huffman)

Απροθεματικός κώδικας ελάχιστου κόστους $cost (c) = \sum_{x} f_{x} \cdot ∣ c (x) ∣$ .

Συγχώνευσε επανειλημμένα τους δύο σπανιότερους χαρακτήρες. $O (n lo g n)$ .

Δυναμικός προγραμματισμός

6 εγγραφές

Συνταγή δυναμικού προγραμματισμού

L14 · DP I

1) Χαρακτήρισε τη δομή (όρισε υποπρόβλημα). 2) Αναδρομικός ορισμός της βέλτιστης τιμής. 3) Υπολόγισε την τιμή (memoization / bottom-up). 4) Κατασκεύασε τη λύση.