Ασκήσεις αλγορίθμων: ταξινόμηση, δυναμικός προγραμματισμός, αθροίσματα — DedSec Project

Ασκήσεις αλγορίθμων: ταξινόμηση, δυναμικός προγραμματισμός, αθροίσματα Σταθερή ταξινόμηση Python 3 reference program Βασική ιδιότητα Η Python sorted δημιουργεί νέα λίστα και είναι stable…

Σταθερή ταξινόμηση

Python 3 reference program

items = [('Ada', 2),('Grace', 1),('Linus', 2)]
items_sorted = sorted(items, key=lambda item: item[1])
assert items_sorted == [('Grace',1),('Ada',2),('Linus',2)]

Βασική ιδιότητα

Η Python sorted δημιουργεί νέα λίστα και είναι stable: εγγραφές με ίδιο κλειδί διατηρούν την αρχική σχετική σειρά. Στο παράδειγμα Ada και Linus έχουν priority 2, άρα μετά το Grace (priority 1) μένουν με την ίδια μεταξύ τους σειρά.

Γιατί έχει σημασία το key

Το lambda item: item[1] επιλέγει το δεύτερο πεδίο. Δεν συγκρίνει ονόματα, εκτός αν τα βάλεις σε σύνθετο κλειδί (item[1], item[0]). Το δεύτερο πεδίο αλλαγής μπορεί να μεταβάλει το κριτήριο ισοπαλίας. Η sorted δεν τροποποιεί την είσοδο, σε αντίθεση με list.sort.

Αρνητικές περιπτώσεις

Έλεγξε ότι η έξοδος είναι Grace, Ada, Linus και ότι η αρχική λίστα παραμένει ίδια.
Πρόσθεσε άλλη εγγραφή με priority 1 και παρατήρησε τη σειρά των ίσων τιμών.
Ταξινόμησε κατά όνομα: εξήγησε γιατί άλλαξε το αποτέλεσμα παρότι ο αλγόριθμος παραμένει σωστός.
Δημιούργησε εγγραφή χωρίς priority και όρισε πολιτική missing keys αντί για απρόβλεπτο IndexError.
Μίξε ακέραιους και strings ως keys. Στην Python 3 μπορεί να εμφανιστεί TypeError, οπότε απαιτείται validation.

Κόστος και εφαρμογή

Η γενική comparison sort έχει worst-case O(n log n), ενώ η Timsort αξιοποιεί ήδη ταξινομημένες ακολουθίες. Για leaderboard όρισε ρητά την ισοπαλία. Δοκίμασε κενή λίστα, ένα στοιχείο, duplicates και αμετάβλητη αρχική είσοδο.

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

Python 3 reference source

def fibonacci(n):
    if n < 0: raise ValueError('n must be >= 0')
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a
assert [fibonacci(n) for n in range(7)] == [0,1,1,2,3,5,8]

Σχέση και αναλλοίωτη ιδιότητα

F(0)=0, F(1)=1 και για n≥2 ισχύει F(n)=F(n-1)+F(n-2). Η απλή αναδρομή επανυπολογίζει πολλά υποπροβλήματα. Η επαναληπτική λύση κρατά a=F(i) και b=F(i+1) στην αρχή κάθε βήματος και προχωρά με ταυτόχρονη ανάθεση. Μετά από n επαναλήψεις επιστρέφει F(n).

Χρόνος και πραγματική μνήμη

Γίνονται n προσθέσεις με δύο θέσεις αποθήκευσης, δηλαδή O(n) iterations και O(1) θέσεις ακεραίων. Αυτό δεν σημαίνει O(1) bits: για μεγάλα n οι αυθαίρετου μεγέθους ακέραιοι απαιτούν περισσότερα bytes και ακριβότερες πράξεις. Η υλοποίηση απορρίπτει ρητά αρνητικό n.

Δοκιμές

Για n=0..6 περιμένουμε [0,1,1,2,3,5,8].
Για n=-1 απαιτείται ValueError, όχι προεπιλεγμένο μηδέν.
Σύγκρινε fibonacci(10) με memoized recursion και μέτρησε κλήσεις, όχι μόνο δευτερόλεπτα.
Φτιάξε πλήρη DP πίνακα και εξήγησε γιατί κοστίζει O(n) θέσεις αλλά κρατά ενδιάμεσες καταστάσεις.
Για μεγάλο n μέτρησε πόσα bits χρειάζεται ο αριθμός και αναθεώρησε την απλουστευμένη υπόσχεση σταθερής μνήμης.

Γενικό μάθημα

Βρες επαναλαμβανόμενα υποπροβλήματα, διατύπωσε recurrence και base cases, απόδειξε την ενημέρωση. Δεν μπορούν όλες οι λύσεις DP να χρησιμοποιούν μόνο δύο μεταβλητές· συχνά απαιτούνται πίνακες ή πληροφορία ανακατασκευής.

Αθροίσματα προθεμάτων

Python 3 reference source

values = [4, 6, 2, 5]
prefix = [0]
for number in values: prefix.append(prefix[-1] + number)
def range_sum(left, right):
    if not (0 <= left <= right <= len(values)): raise ValueError('range')
    return prefix[right] - prefix[left]
assert range_sum(1, 3) == 8

Αναπαράσταση

Για values [4,6,2,5] φτιάχνουμε prefix [0,4,10,12,17]. Κάθε prefix[i] είναι το άθροισμα των στοιχείων πριν από τη θέση i. Το αρχικό μηδέν επιτρέπει ίδια φόρμουλα και για διάστημα που αρχίζει από το 0.

Ιδιότητα και κόστος

Το άθροισμα του values[left:right] είναι prefix[right]-prefix[left]. Για left=1 και right=3 έχουμε 12-4=8, δηλαδή 6+2. Η δημιουργία πίνακα κοστίζει O(n) χρόνο και O(n) μνήμη· κάθε επόμενο ελεγμένο query O(1) χρόνο. Αυτό συμφέρει όταν εκτελούνται πολλές αναζητήσεις στην ίδια αμετάβλητη λίστα.

Δοκιμές

range_sum(0,0)=0 γιατί το κενό διάστημα έχει άθροισμα μηδέν.
range_sum(0,len(values))=17, το συνολικό άθροισμα.
range_sum(1,3)=8 και range_sum(3,4)=5.
Με left>right, αρνητικό left ή υπέρβαση μήκους πρέπει να προκύπτει ValueError, όχι διαφορετικό Python slicing.
Άλλαξε values[1] μετά την κατασκευή prefix. Ο πίνακας είναι πλέον παλιός και χρειάζεται ενημέρωση ή επανυπολογισμό.

Επέκταση

Για πολλές ενημερώσεις μαζί με queries μελέτησε Fenwick/segment tree και την ανταλλαγή O(log n). Σε γλώσσες με πεπερασμένα integers απαιτείται τύπος αρκετά μεγάλος για το άθροισμα. Έλεγχε πάντα τα όρια πριν την αφαίρεση δεικτών.

Κανονικοποίηση κειμένου

Python 3 reference source

import unicodedata
composed = "é"
decomposed = "e\u0301"
assert composed != decomposed
assert len(composed) == 1 and len(decomposed) == 2
assert unicodedata.normalize("NFC", composed) == unicodedata.normalize("NFC", decomposed)

Μηχανισμός

Το ορατό é μπορεί να είναι ένα code point U+00E9 ή δύο, U+0065 (e) και U+0301 (combining accent). Οι συμβολοσειρές έχουν διαφορετικά bytes και διαφορετικό Python len, αλλά είναι κανονικά ισοδύναμες κατά Unicode. Η unicodedata.normalize('NFC', text) συνθέτει όπου επιτρέπεται τους χαρακτήρες σε κοινή μορφή.

Γιατί δεν αρκεί για ασφάλεια

Η normalization είναι ρητή επιλογή σύγκρισης ή αποθήκευσης. Δεν εντοπίζει homoglyph phishing, δεν κάνει αυτόματα σωστό locale sorting και δεν αποδεικνύει ότι ένα identifier είναι ασφαλές. Το casefold είναι ξεχωριστή πράξη. Σε ψηφιακές υπογραφές και forensic logs ίσως απαιτείται διατήρηση των αρχικών bytes.

Πειράματα

Έλεγξε ότι οι δύο αρχικές συμβολοσειρές διαφέρουν αλλά γίνονται ίσες μετά από NFC.
Σύγκρινε πλήθος code points (1 έναντι 2) και αρχικά UTF-8 bytes.
Με NFD αντί NFC παρατήρησε αποσυντεθειμένη μορφή, κρατώντας την κανονική ισοδυναμία.
Σε απλό ASCII identifier, η normalization δεν πρέπει να αλλάζει τίποτα.
Σχεδίασε κανόνα για filenames και search titles: κράτησε ξεχωριστά κανονικοποιημένο κλειδί και αυθεντικό κείμενο εμφάνισης.

Πρακτική εφαρμογή

Κάνε normalization σε ένα τεκμηριωμένο σημείο εισόδου και μη μεταβάλλεις αθόρυβα καταγεγραμμένη αρχική πηγή. Δοκίμασε συνθετικά ελληνικά τονισμένα δεδομένα και κατέγραψε Unicode/Python έκδοση και μορφή NFC/NFD.

09 sorting — έλεγχος ορίων

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

Η sorted() φτιάχνει νέα λίστα, ενώ η .sort() αλλάζει την αρχική. Τα κλειδιά πρέπει να συγκρίνονται· None μαζί με ακέραιους μπορεί να προκαλέσει TypeError.

12 fibonacci dp — έλεγχος ορίων

Ο δυναμικός προγραμματισμός αντικαθιστά επαναλαμβανόμενους υπολογισμούς με αποθήκευση αποτελεσμάτων. Στη Fibonacci αρκούν δύο προηγούμενες τιμές ώστε η βοηθητική μνήμη να μείνει σταθερή.

Συμφώνησε πρώτα τον ορισμό F(0)=0 και F(1)=1. Έλεγξε n=0, n=1, n=2 και μεγάλο n, καθώς οι ακέραιοι μεγαλώνουν ακόμη κι αν η βοηθητική μνήμη παραμένει O(1).

13 prefix sums — έλεγχος ορίων

Με prefix[0]=0 και prefix[i+1]=prefix[i]+values[i], το άθροισμα του ημιανοικτού [left,right) είναι prefix[right]-prefix[left]. Το αρχικό μηδέν αποφεύγει ειδική περίπτωση για αριστερό όριο μηδέν.

Η προετοιμασία κοστίζει O(n) και κάθε ερώτημα O(1). Έλεγξε left<=right<=n, συμπεριλαμβανομένου κενού εύρους με ίσα όρια.

14 safe text normalization — έλεγχος ορίων

Η κανονικοποίηση είναι ρητή απόφαση δεδομένων, όχι αυτόματη λύση ασφάλειας. Η Unicode NFC ενοποιεί ισοδύναμες συνθέσεις και η .casefold() βοηθά σε συγκρίσεις χωρίς διάκριση πεζών· δεν ταυτίζει κάθε οπτικά όμοιο χαρακτήρα.

Πριν κανονικοποιήσεις usernames αποφάσισε αν οι τόνοι έχουν σημασία. Κράτησε την αρχική είσοδο για έλεγχο, απόρριψε ανεπιθύμητους χαρακτήρες ελέγχου και δοκίμασε οπτικά όμοια αλλά διαφορετικά κείμενα.