Τυπολόγιο

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

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

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}

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

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))

Γραφήματα

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)$ .

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

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

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))$ ανά πράξη — πρακτικά σταθερό.

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

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

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)$ .

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

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

L14 · DP I

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

Σταθμισμένος χρονοπρογραμματισμός

L14 · DP I

$p (j)$ = τελευταίο συμβατό προηγούμενο αίτημα.

OPT (j) = max {v_{j} + OPT (p (j)), OPT (j - 1)}

$O (n lo g n)$ με ταξινόμηση κατά χρόνο λήξης.

Σακίδιο (0/1 knapsack)

L15 · DP II (knapsack)

OPT (i, w) = max {OPT (i - 1, w), v_{i} + OPT (i - 1, w - w_{i})}

$Θ (nW)$ — ψευδοπολυωνυμικό. Το πρόβλημα απόφασης είναι NP-πλήρες.

Μέγιστη κοινή υπακολουθία (LCS)

L15 · DP II (knapsack)

OPT (i, j) = {1 + OPT (i - 1, j - 1) max {OPT (i - 1, j), OPT (i, j - 1)} x_{i} = y_{j} x_{i} \neq = y_{j}

Χρόνος $Θ (mn)$ .

Απόσταση επεξεργασίας / ευθυγράμμιση

L16 · DP III (LCS, edit distance)

OPT (i, j) = min ⎩ ⎨ ⎧ α_{x_{i} y_{j}} + OPT (i - 1, j - 1) δ + OPT (i - 1, j) δ + OPT (i, j - 1)

$Θ (mn)$ χρόνος· Hirschberg → $O (m + n)$ χώρος.

Bellman-Ford (αρνητικά βάρη)

L17 · DP IV (DP on graphs)

$OPT (i, v)$ = συντομότερο $v \to t$ μονοπάτι με $\leq i$ ακμές.

OPT (i, v) = min {OPT (i - 1, v), (v, w) \in A min (ℓ_{v w} + OPT (i - 1, w))}

$Θ (mn)$ . Αρνητικός κύκλος ⇒ δεν υπάρχει λύση.

Last-minute friendly

Σώσε το εξάμηνο

Just-in-time learning για όσους έχουν 10, 5, 3, ή 1 μέρα μέχρι την εξέταση. Δεν χρειάζεται να ξέρεις όλη τη θεωρία πριν αρχίσεις τις ασκήσεις.

1. Λύσε

Ξεκίνα από την πιο εύκολη άσκηση. Δοκίμασέ την, ακόμα κι αν δεν ξέρεις τίποτα.

2. Διάβασε ό,τι λείπει

Σου λέμε ακριβώς ποιο κομμάτι θεωρίας χρειάζεσαι για ΑΥΤΗ την άσκηση. Επιστρέφεις με ένα κλικ.

3. Επόμενη

Κάθε άσκηση που λύνεις = ένα νέο εργαλείο που μπορεί να πέσει στην εξέταση. Σου μετράμε το πραγματικό βάρος.

Γιατί δουλεύει

Είναι ασφαλέστερο. Το να διαβάσεις 200 σελίδες θεωρίας πριν δεις άσκηση δεν εγγυάται ότι θα ξέρεις τι να κάνεις στην εξέταση. Το να λύσεις 30 ασκήσεις σε εγγυάται ότι έχεις 30 εργαλεία.
Είναι σε σωστή σειρά. Οι ασκήσεις είναι ταξινομημένες ανά θεωρητική δυσκολία. Οι πρώτες χρειάζονται μόνο ασυμπτωτική ανάλυση· οι τελευταίες DP πάνω σε γραφήματα. Δεν θα κολλήσεις σε DP χωρίς να έχεις δει greedy.
Παρακολουθούμε αληθινό βάρος. Όχι «έχεις λύσει το 30%» αλλά «έχεις καλύψει το 32% του εξεταστικού βάρους βάσει 6 παλαιών εξεταστικών». Πραγματικός αριθμός που σου λέει πόσο έχεις απομείνει.
Κάθε άσκηση έρχεται με coaching. Δεν είναι απλά «να η λύση». Σε κάθε πρόβλημα παίρνεις «τι κρατάς» (το pattern), «πώς θα το αναγνωρίσεις στην εξέταση», και 2-3 παρόμοιες ασκήσεις για περισσότερη εξάσκηση.

Το «εξεταστικό βάρος» υπολογίζεται από τα παλαιότερα θέματα του K17 (Ιούνιος/Σεπτέμβριος 2020 → 2025, πρόοδοι, αρχείο Ζησιμόπουλου). Δεν είναι πρόβλεψη για το επόμενο εξεταστικό — είναι μέτρηση του τι έχεις ήδη δουλέψει.