Αλγόριθμοι

Σχεδιάγραμμα

Δική μας σύνοψη της ενότητας, για επανάληψη, γραμμένη με τη βοήθεια τεχνητής νοημοσύνης. Μπορεί να έχει λάθη: πηγή είναι πάντα το βιβλίο.

Τι έγινε

1. Η λέξη αλγόριθμος βγαίνει από το όνομα του Πέρση μαθηματικού Αλ Χουαρίζμι. Ένας από τους αρχαιότερους αλγορίθμους είναι του Ευκλείδη για τον ΜΚΔ δύο ακεραίων.
2. Κάθε ερώτηση που λύνει ένας αλγόριθμος λέγεται στιγμιότυπο του προβλήματος· για να δεχτούμε ότι τον λύνει, πρέπει να αποδειχτεί αυστηρά η ορθότητά του.
3. Η ανάλυση αλγορίθμου εκτιμά τους πόρους (χρόνο, μνήμη) που χρειάζεται. Τάξεις πολυπλοκότητας: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ). Οι εκθετικές μένουν πρακτικά μόνο για μικρά προβλήματα.
4. Οι αλγόριθμοι είναι σειριακοί (μία ΚΜΕ) ή παράλληλοι (πολλές ΚΜΕ ταυτόχρονα), και επαναληπτικοί ή αναδρομικοί, όπως το Ν! = Ν·(Ν−1)! με 0! = 1.
5. Αναπαράσταση: φυσική γλώσσα, ψευδογλώσσα, γλώσσα προγραμματισμού (οπτική ή κειμενική) και διάγραμμα ροής με έλλειψη, πλάγιο παραλληλόγραμμο, ορθογώνιο, ρόμβο και βέλη.
6. Τύποι δεδομένων: ακέραιος, πραγματικός, λογικός, αλφαριθμητικός. Δομές δεδομένων: πίνακας, στοίβα (LIFO), ουρά (FIFO), λίστα, δένδρο, γράφος· στατικές ή δυναμικές, γραμμικές ή μη γραμμικές. Κατά τον Wirth, αλγόριθμοι και δομές δεδομένων δίνουν προγράμματα.
7. Στην ψευδογλώσσα: εκχώρηση με ←, Διάβασε/Εμφάνισε ή Δεδομένα/Αποτελέσματα, τελεστές αριθμητικοί, σχεσιακοί, λογικοί (όχι, και, ή) με ιεραρχία, δομές Αν...τότε...αλλιώς_αν και τρεις επαναλήψεις, κλήση με Κάλεσε και αναδρομή.
8. Σε πίνακες εφαρμόζονται εισαγωγή, εκτύπωση, άθροισμα, μέγιστο, σειριακή αναζήτηση και ταξινόμηση με επιλογή (O(n²)). Τα λογικά λάθη βρίσκονται μόνο με έλεγχο και εκτέλεση με το χέρι, και η τεκμηρίωση συνοδεύει όλα τα στάδια.

Πρόσωπα

Αλ Χουαρίζμι (al-Khwārizmī)

Πέρσης μαθηματικός (περ. 825 μ.Χ.), από το όνομά του βγαίνει η λέξη αλγόριθμος

Ευκλείδης

έγραψε τα «Στοιχεία» σε 13 βιβλία και απέδειξε τον αλγόριθμο του ΜΚΔ

Ντόναλντ Κνουθ (Donald Knuth)

χαρακτήρισε τον ευκλείδειο αλγόριθμο τον παλαιότερο που χρησιμοποιείται ακόμη

Νικλάους Βιρθ (Niklaus Wirth)

δημιουργός της Pascal· Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα

Λαμέ (Lamé)

απέδειξε όριο για τα βήματα του ευκλείδειου αλγορίθμου

Όροι

αλγόριθμος

πεπερασμένη σειρά σαφών ενεργειών

καθοριστικότητα

κάθε εντολή εκτελείται χωρίς αμφιβολία

περατότητα

τελειώνει μετά από πεπερασμένα βήματα

αποτελεσματικότητα

κάθε εντολή εκτελείται ακριβώς

στιγμιότυπο

μία συγκεκριμένη ερώτηση του προβλήματος

πολυπλοκότητα

μέτρο του χρόνου εκτέλεσης

O(n log n)

γρήγορη ταξινόμηση (Quicksort)

O(n²)

ταξινόμηση με επιλογή

παράλληλος αλγόριθμος

βήματα ταυτόχρονα σε πολλές ΚΜΕ

αναδρομή

η συνάρτηση καλεί τον εαυτό της

ψευδογλώσσα

υποθετική γλώσσα για αλγορίθμους

ρόμβος στο διάγραμμα ροής

ερώτηση με δύο εξόδους

δομή δεδομένων

οργανωμένα δεδομένα με λειτουργίες

στοίβα

LIFO: τελευταίο μέσα, πρώτο έξω

ουρά

FIFO: πρώτο μέσα, πρώτο έξω

δένδρο

μη γραμμική δομή με ρίζα και φύλλα

εκχώρηση ←

η τιμή δεξιά μπαίνει στη μεταβλητή

Όσο...επανάλαβε

ελέγχει τη συνθήκη στην αρχή

Επανάλαβε...Μέχρις_ότου

σταματά όταν η συνθήκη γίνει αληθής

εκσφαλμάτωση

εύρεση των λογικών λαθών