L01 · Εισαγωγικά

Καλώς ήρθες

Αυτή είναι η αφετηρία για όλο το μάθημα. Στόχος της διάλεξης: μέχρι το τέλος, να ξέρεις τι ακριβώς εννοούμε όταν λέμε «αλγόριθμος», με ποιο εργαλείο τον συγκρίνουμε με άλλους, και ποια διαδρομή θα ακολουθήσουμε από εδώ μέχρι την εξεταστική.

Από πού έρχεται η λέξη «αλγόριθμος»

Από τον Al-Khwarizmi — Πέρση μαθηματικό του 9ου αιώνα. Έγραψε ένα βιβλίο για μεθοδικές διαδικασίες λύσης εξισώσεων· όταν το έργο του μεταφράστηκε στα Λατινικά, το όνομά του παραφθάρηκε σε Algoritmi, και η λέξη επιβίωσε.

Γιατί χάνουμε χρόνο σε ένα μάθημα Αλγορίθμων;

Εύλογο ερώτημα — ειδικά τώρα που υπάρχουν LLMs που λύνουν ασκήσεις. Δύο απαντήσεις:

1. Τα παραδείγματα είναι παντού. Κοινωνικά δίκτυα (ποιους φίλους να σου προτείνει το Instagram), επικοινωνία drones (σε ποιο συντομότερο μονοπάτι να πάει το επόμενο), εύρεση διαδρομών (Google Maps), συναλλαγές (κρυπτογραφία). Κάτω από όλα αυτά κάποιος αλγόριθμος τρέχει, και η ποιότητά του καθορίζει αν η εφαρμογή δουλεύει σε εκατομμύρια χρήστες ή κολλάει στα 100.
2. Τα LLMs σου λένε τι, όχι γιατί. Όταν στην εξέταση δεις μια άσκηση τύπου «σχεδίασε αλγόριθμο που…» θα πρέπει να αναγνωρίσεις ποιο σχήμα εφαρμόζεται, να αποδείξεις ότι δουλεύει, και να αναλύσεις την πολυπλοκότητα. Αυτό το μάθημα είναι ακριβώς αυτή η εξάσκηση.

Οι τρεις στόχοι του εξαμήνου

Όλα όσα κάνουμε καταλήγουν σε ένα από αυτά τα τρία:

Δηλαδή:

1. Αποτίμηση — δοθέντος ενός αλγορίθμου, πόσο χρόνο και μνήμη χρειάζεται;
2. Σύγκριση — δοθέντων δύο αλγορίθμων που λύνουν το ίδιο πρόβλημα, ποιος είναι καλύτερος και υπό ποιες προϋποθέσεις;
3. Σχεδίαση — δοθέντος ενός προβλήματος που δεν έχουμε ξαναδεί, πώς στήνουμε έναν καλό αλγόριθμο για αυτό;

Δύο σημαντικές ερωτήσεις πριν προχωρήσουμε

Είναι όλα τα προβλήματα επιλύσιμα από έναν αλγόριθμο;

Όχι. Υπάρχουν προβλήματα που είναι αποδεδειγμένα μη επιλύσιμα από οποιονδήποτε αλγόριθμο (το διάσημο παράδειγμα: το halting problem — «δοθέντος ενός προγράμματος, θα τερματίσει;»). Στο μάθημα δεν θα μπούμε σε υπολογιστική μη-αποφασισιμότητα, αλλά αξίζει να ξέρεις ότι υπάρχει αυτό το όριο.

Υπάρχει για όλα τα επιλύσιμα προβλήματα ένας «καλός» αλγόριθμος;

Αυτή είναι η ερώτηση που γέννησε ολόκληρο τον τομέα της πολυπλοκότητας. Υπάρχουν προβλήματα επιλύσιμα μεν, αλλά κανείς δεν ξέρει αν υπάρχει «γρήγορος» (=πολυωνυμικός) αλγόριθμος για αυτά. Το αν P=NP είναι ένα από τα 7 «Millennium problems» με 1 εκ. δολάρια έπαθλο.

Πιο συγκεκριμένα, τα προβλήματα που θα συναντήσεις στο μάθημα μοιράζονται σε τρεις «ζώνες»: αυτά για τα οποία ξέρουμε γρήγορο αλγόριθμο (στο P), αυτά που πιστεύεται ότι ΔΕΝ έχουν γρήγορο αλγόριθμο (NP-πλήρη), και ελάχιστα που ακόμα δεν ξέρουμε σε ποια από τις δύο πλευρές πέφτουν (άγνωστα). Δεν θα κάνουμε θεωρία NP στο K17, αλλά αυτή είναι η γεωγραφία — και έρχεται με μερικές διάσημες παγίδες (π.χ. το συντομότερο μονοπάτι είναι εύκολο, αλλά το μακρύτερο είναι NP-πλήρες):

Αυτή ακριβώς η τριμερής γεωγραφία γίνεται μέγεθος 3–4% του γραπτού στις τρεις πιο πρόσφατες εξεταστικές — σε τρία διαφορετικά σχήματα ερώτησης, που μοιράζονται όλα τον ίδιο ζωολογικό κήπο ως φακό. Αξίζει να τα δεις τώρα που οι ζώνες είναι ακόμη φρέσκες.

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

Η τρίτη ζώνη — τα ακόμη άγνωστα — έχει το δικό της, ξεχωριστό σχήμα ερώτησης, και είναι το μόνο σημείο όπου η σωστή απάντηση δεν είναι ούτε «στο P» ούτε «NP-πλήρες»:

Δυαδική αναζήτηση — ο πρώτος μας αλγόριθμος

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

Δοκίμασέ την μόνος σου — διάλεξε στόχο, και σε κάθε βήμα αποφάσισε ποιο μισό κρατάς:

Πρόσεξε τι έγινε. Σε πίνακα 8 στοιχείων χρειάζονται το πολύ 4 συγκρίσεις στη χείριστη περίπτωση — γιατί κάθε σύγκριση διχοτομεί τον χώρο αναζήτησης. Διπλασίασε τον πίνακα στα 16; γίνονται 5. Στα 1024; γίνονται 11. Στα 1.000.000; γίνονται περίπου 20. Δεν είναι η ίδια συμπεριφορά με τη γραμμική αναζήτηση: εκεί κάθε διπλασιασμός του $n$ διπλασιάζει τη δουλειά· εδώ προσθέτει μία και μόνο σύγκριση. Σύρε το slider και νιώσε το χάσμα:

Αυτή η συμπεριφορά «κάθε βήμα κόβει στη μέση» είναι ο πυρήνας του L02 · Ασυμπτωτική ανάλυση και επιστρέφει στο L03 · D&C.

Πότε ένα πρόγραμμα είναι «χρήσιμο»;

Σύμφωνα με τη διάλεξη:

Ένα πρόγραμμα είναι χρήσιμο όταν, σε λογικό χρόνο και σε λογικό χώρο μνήμης, εξάγει το σωστό αποτέλεσμα.

Αυτή η μία πρόταση κρύβει τρεις απαιτήσεις:

Οι δύο τελευταίες μαζί αποτελούν την πολυπλοκότητα του αλγορίθμου.

Πρόβλημα, στιγμιότυπο, διάσταση — τρία επίπεδα

Στην εκφώνηση «θέλω αλγόριθμο για το πρόβλημα τάδε» κρύβονται τρία επίπεδα που πρέπει να τα ξεχωρίζεις. Όλη η μετέπειτα ανάλυση πατάει πάνω σε αυτή τη διάκριση:

1. Το πρόβλημα — η γενική περιγραφή του τι παίρνουμε και τι ζητάμε. Δεν αναφέρεται σε συγκεκριμένα νούμερα.
2. Το στιγμιότυπο — μία συγκεκριμένη είσοδος του προβλήματος. Πραγματικοί αριθμοί, πραγματικά αντικείμενα. Ένα πρόβλημα γεννά άπειρα στιγμιότυπα.
3. Η διάσταση — ένας αριθμός ανά στιγμιότυπο που μετράει το «μέγεθός» του. Σχεδόν πάντα γράφεται $n$.

Πάτα κάτω «νέο στιγμιότυπο» και άλλαξε tab μεταξύ ταξινόμησης και knapsack. Δες πώς το ίδιο πρόβλημα γεννά πολλά στιγμιότυπα — και πώς το $n$ τα «βάζει σε σειρά» ανεξάρτητα από τα συγκεκριμένα νούμερα του καθενός:

Πώς μετράμε την πολυπλοκότητα

• Μονάδα μέτρησης: η στοιχειώδης (ουσιώδης) πράξη — μια ενέργεια που υποθέτουμε ότι γίνεται σε σταθερό χρόνο. Παραδείγματα: μία πρόσθεση, μία σύγκριση, μία εκχώρηση σε μεταβλητή.
• Συνάρτηση της διάστασης: μετράμε πόσες στοιχειώδεις πράξεις γίνονται ως συνάρτηση του $n$.

Η συνάρτηση αυτή είναι ο χρόνος εκτέλεσης του αλγορίθμου, και θα μάθουμε στο L02 πώς τη συγκρίνουμε με άλλες χρησιμοποιώντας τα $O,\Theta ,\Omega$.

Τρεις τύποι πολυπλοκότητας

Τώρα ένα παράδοξο. Είπαμε ότι η πολυπλοκότητα είναι συνάρτηση της διάστασης $n$. Αλλά δύο διαφορετικά στιγμιότυπα ίδιας διάστασης μπορεί να απαιτούν τελείως διαφορετική δουλειά — π.χ. στη γραμμική αναζήτηση, αν το $x$ είναι στη θέση 1 ή στη θέση $n$, η διαφορά είναι δραματική παρότι το μέγεθος είναι ίδιο. Σε ποιο από τα δύο αναφερόμαστε λοιπόν; Δεν υπάρχει μία απάντηση — υπάρχουν τρεις, και πρέπει να τις διακρίνουμε:

Πιο τυπικά, αν $D_n$ είναι το σύνολο όλων των στιγμιοτύπων διάστασης $n$:

όπου $p(d)$ η πιθανότητα να εμφανιστεί το στιγμιότυπο $d$ ως είσοδος.

Αυτές οι τρεις φόρμουλες είναι πολύ πιο φιλικές αν τις δεις να «γεμίζουν» με συγκεκριμένα νούμερα. Διάλεξε αλγόριθμο, επίλεξε διάσταση, και πάτα κάθε μία από τις τρεις περιπτώσεις:

Παράδειγμα 1: γραμμική αναζήτηση

Παράδειγμα 2: αριθμητικό γινόμενο — όταν οι τρεις συμπίπτουν

Κλείδωσε τις έννοιες

Τρεις λέξεις μπερδεύονται συνεχώς — πρόβλημα, στιγμιότυπο, διάσταση. Συμπλήρωσε τα κενά χωρίς να κοιτάς πίσω:

Το πλάνο του εξαμήνου

Τέσσερις τεχνικές σχεδιασμού αλγορίθμων, μία θεματική ενότητα γραφημάτων, και μία ενότητα δομών δεδομένων — όλα κάθονται πάνω στα θεμέλια που χτίζουμε στις L01–L02.

Η ασυμπτωτική ανάλυση (L02) είναι παντού: σε κάθε ανάλυση χρόνου που θα κάνουμε, σε κάθε σύγκριση αλγορίθμων, σε κάθε απόδειξη βελτιστότητας. Γι' αυτό την παίρνουμε πρώτη.

Βαθμολογία και πρακτικά

• Δύο βαθμοί: Πρόοδος (Π) και Γραπτό (Γ).
• Τελικός βαθμός = $\max \{\Gamma ,0.3\cdot \Pi +0.7\cdot \Gamma \}$ — δηλαδή η πρόοδος βοηθάει, δεν βλάπτει: αν τα πας καλά στην πρόοδο και χάλια στο γραπτό, σε «τραβάει» πάνω· αν τα πας καλύτερα στο γραπτό, αγνοείται η πρόοδος.
• Όριο 40% στο γραπτό για να μετρήσει η πρόοδος.

Βιβλιογραφία

• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS). Η «βίβλος» των αλγορίθμων.
• Kleinberg & Tardos — Algorithm Design. Πιο φιλική στην απόδειξη ορθότητας, εξαιρετική στο D&C και το greedy.
• Dasgupta, Papadimitriou, Vazirani — Algorithms. Συνοπτικότερο, διαθέσιμο ελεύθερα σε pdf.
• Συμπληρωματικά: σημειώσεις και διαφάνειες Β. Ζησιμόπουλου στην eclass.