Γλωσσάρι: backtracking και πολυπλοκότητα αναζήτησης — DedSec Project

Backtracking

Πώς συμπεριφέρεται η έννοια

Search που δοκιμάζει υποψήφια λύση, απορρίπτει παραβίαση και επαναφέρει state για άλλο branch. Χρήσιμο σε Sudoku/permutations, αλλά μπορεί να έχει εκθετικό κόστος.

Μικρό παράδειγμα

def choices(xs):
    if not xs: yield []
    else:
        for i,x in enumerate(xs):
            for tail in choices(xs[:i]+xs[i+1:]): yield [x]+tail
assert len(list(choices([1,2,3])))==6

Πρακτική διερεύνηση

Πρόσθεσε constraint που απορρίπτει prefix και μέτρησε branches που παραλείπονται.

Δοκιμή ορίου

Για Οπισθοδρόμηση, δοκίμασε δεύτερη είσοδο που αλλάζει το αποτέλεσμα. Σημείωσε αναμενόμενη συμπεριφορά πριν το run και εξήγησε τον κανόνα που παραβιάζεται.

Big O

Πώς συμπεριφέρεται η έννοια

Ασυμπτωτικό άνω φράγμα αύξησης σε σχέση με input size, όχι ακριβή δευτερόλεπτα. O(n log n) μπορεί να είναι πιο αργό σε μικρό input λόγω constants.

Μικρό παράδειγμα

def contains(items,x):
    return x in items
assert contains([1,2,3],2)

Πρακτική διερεύνηση

Μέτρησε lookup σε lists διαφορετικών μηκών και σύγκρινε με set συμπεριλαμβάνοντας construction cost.

Δοκιμή ορίου

Για Συμβολισμός Big O, δοκίμασε δεύτερη είσοδο που αλλάζει το αποτέλεσμα. Σημείωσε αναμενόμενη συμπεριφορά πριν το run και εξήγησε τον κανόνα που παραβιάζεται.

Binary search — ορισμός

Πώς συμπεριφέρεται η έννοια

Search σε sorted data με υποδιπλασιασμό διαστήματος ανά βήμα. Έχει O(log N) comparisons· unsorted data παραβιάζουν την προϋπόθεση.

Μικρό παράδειγμα

def find(a,x):
    lo,hi=0,len(a)
    while lo<hi:
        m=(lo+hi)//2
        if a[m]<x: lo=m+1
        else: hi=m
    return lo if lo<len(a) and a[lo]==x else None
assert find([1,3,5],3)==1

Πρακτική διερεύνηση

Παρακολούθησε lo/hi/m σε missing number· δοκίμασε duplicates και empty array σε σύγκριση με bisect_left.

Δοκιμή ορίου

Για Δυαδική αναζήτηση, δοκίμασε δεύτερη είσοδο που αλλάζει το αποτέλεσμα. Σημείωσε αναμενόμενη συμπεριφορά πριν το run και εξήγησε τον κανόνα που παραβιάζεται.

Bit

Πώς συμπεριφέρεται η έννοια

Μικρότερη binary πληροφοριακή μονάδα με τιμές 0/1. Bit masks κωδικοποιούν flags· signed interpretation αλλάζει αποτελέσματα.

Μικρό παράδειγμα

READ=1;WRITE=2;EXEC=4
permissions=READ|WRITE
assert permissions&READ
assert not permissions&EXEC

Πρακτική διερεύνηση

Πρόσθεσε EXEC και αφαίρεσε WRITE. Πρόβλεψε αποτελέσματα των &, | και ~ πριν το run.

Δοκιμή ορίου

Για Δυαδικό ψηφίο, δοκίμασε δεύτερη είσοδο που αλλάζει το αποτέλεσμα. Σημείωσε αναμενόμενη συμπεριφορά πριν το run και εξήγησε τον κανόνα που παραβιάζεται.

Boolean

Πώς συμπεριφέρεται η έννοια

Λογική true/false για conditions. Στην Python το bool είναι subclass του int, οπότε isinstance(True,int) είναι True· αυστηρό numeric validation ίσως χρειάζεται type(x) is int.

Μικρό παράδειγμα

assert (2<3) is True
assert isinstance(True,int)
assert type(True) is bool

Πρακτική διερεύνηση

Σχεδίασε JSON schema όπου max_items=True απορρίπτεται παρότι bool αριθμητικά μοιάζει με 1.

Δοκιμή ορίου

Για Λογική τιμή, δοκίμασε δεύτερη είσοδο που αλλάζει το αποτέλεσμα. Σημείωσε αναμενόμενη συμπεριφορά πριν το run και εξήγησε τον κανόνα που παραβιάζεται.