ΑΛΓΟΡΙΘΜΟΣ
Μια θεμελιωδης εννοια της πληροφορικης
ΟΡΙΣΜΟΣ
Αλγόριθμος είναι μια σειρά από σαφείς οδηγίες που περιγράφουν βήμα-βήμα τη λύση ενός προβλήματος
Ο ΑΛΓΟΡΙΘΜΟΣ ΤΟΥ ΕΥΚΛΕΙΔΗ
(ΣΕ ΨΕΥΔΟΓΛΩΣΣΑ)
- Αν Β=0 τότε σταμάτησε τον αλγόριθμο με αποτέλεσμα το Α
- Αλλιώς Επανάλαβε τα παρακάτω βήματα μέχρι να έχουμε Β=0
- Θέσε Υ ← υπόλοιπο της διαίρεσης A : B
- Θέσε A ← B
- Θέσε Β ← Υ
- Σταμάτησε τον αλγόριθμο με αποτέλεσμα το Α
Ο όρος "αλγόριθμος" προέρχεται από τον μεγάλο Πέρση μαθηματικό του 9ου αιώνα
Αλ Χουαριζμι
Μέσω αλγορίθμων μπορούμε να αυτοματοποιήσουμε εργασίες όπως:
- Υπολογισμοί (πχ υπολογισμός του Μέγιστου Κοινού Διαιρέτη)
- Επεξεργασία δεδομένων (πχ ταξινόμηση ενός συνόλου στοιχείων)
- Λήψη αποφάσεων (πχ λογισμικό χρηματιστηριακών συναλλαγών)
ΕΡΩΤΗΣΗ
Πήγαινε στο μπακάλικο και πάρε ένα ψωμί.
Αν έχει αυγά, πάρε δέκα.
- Ένα ψωμί και δέκα αυγά
- Δέκα ψωμιά και κανένα αυγό
- Οποιοδήποτε από τα δύο
ΕΡΩΤΗΣΗ
Τι θα απαντήσει ο παρακάτω αλγόριθμος;
- Έστω Αθροισμα=0 και Ν=1
- Πρόσθεσε στο Άθροισμα το Ν
- Διπλασίασε το Ν
- Αν το Ν είναι ζυγός αριθμός, επανάλαβε από το βήμα 2
- Η απάντηση είναι η τιμή του Αθροίσματος
ΤΡΟΠΟΙ ΕΚΦΡΑΣΗΣ ΑΛΓΟΡΙΘΜΩΝ
- Ελεύθερο κείμενο
- Ψευδογλώσσα
- Διάγραμμα ροής
- Γλώσσα προγραμματισμού
ΠΡΟΓΡΑΜΜΑ
είναι ένας αλγόριθμος γραμμένος σε γλώσσα προγραμματισμού, ο οποίος μπορεί να εκτελεστεί από ένα ηλεκτρονικό υπολογιστή
Αλγόριθμους όμως συναντάμε από την αρχαιότητα
ΓΛΩΣΣΕΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ
Ποια γλώσσα προγραμματισμού είναι η καλύτερη;
Κάθε γλώσσα προγραμματισμού είναι Turing Complete, δηλαδή μπορεί να εκφράσει οποιοδήποτε αλγόριθμο.
Η επιλογή της γλώσσας αφορά τη χρήση για την οποία προορίζεται το πρόγραμμα.
ΓΛΩΣΣΕΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ
- C/C++:Προγράμματα που αλληλεπιδρούν άμεσα με το υλικό του υπολογιστή(hardware)
- Java:Προγράμματα που είναι ανεξάρτητα από το είδος της συσκευής που εκτελούνται
- Javascript/php:Προγραμματισμός ιστοσελίδων Παγκόσμιου Ιστού(www)
- Python:Εύκολη στη χρήση
ΕΡΩΤΗΣΗ
Ποιό από τα παρακάτω ΔΕΝ ΤΑΙΡΙΑΖΕΙ με την έννοια του αλγορίθμου
- Οι συνταγές μαγειρικής
- Οι χοροί
- Οι Δέκα Εντολές
ΤΑ ΣΥΣΤΑΤΙΚΑ ΕΝΟΣ ΑΛΓΟΡΙΘΜΟΥ
- Δομή ακολουθίας
- Δομή επιλογής
- Δομή επανάληψης
ΕΡΩΤΗΣΗ
Ποιό από τα παρακάτω ΔΕΝ ΙΣΧΥΕΙ για τους αλγορίθμους;
- Συνδυάζοντας αλγόριθμους, προκύπτουν νέοι αλγόριθμοι
- Οι αλγόριθμοι μπορεί να αξίζουν εκατομμύρια
- Πολλές φορές ένα πρόβλημα λύνεται από περισσότερους από έναν αλγόριθμους
- Υπάρχουν προβλήματα που είναι αδύνατο να λυθούν
- Η απόδειξη ότι ένας αλγόριθμος όντως λύνει ένα πρόβλημα, είναι εύκολη
ΠΑΡΑΔΕΙΓΜΑΤΑ
- Πολύπλοκοι αλγόριθμοι, πολλές φορές προκύπτουν από το συνδυασμό απλούστερων.
- O αλγόριθμος PageRank, με τον οποίο η Google ταξινομεί τα αποτέσματα αναζήτησης, αξίζει δισεκατομμύρια δολλάρια(180 το 2008).
ΠΑΡΑΔΕΙΓΜΑΤΑ
- Υπάρχουν πολλοί αλγόριθμοι ταξινόμησης και αναζήτησης
- Ο πρωτοπόρος της πληροφορικής και μεγάλος μαθηματικός Alan Turing, απέδειξε ότι υπάρχουν προβλήματα που δεν έχουν λύση.
ΟΡΘΟΤΗΤΑ ΑΛΓΟΡΙΘΜΩΝ
Πότε ένας αλγόριθμος θεωρείται σωστός;
Αν παράγει πάντα σωστά αποτελέσματα, χωρίς να εκτελείται για πάντα ή να προκύπτουν σφάλματα κατά την εκτέλεση.
ΟΡΘΟΤΗΤΑ ΑΛΓΟΡΙΘΜΩΝ
- Η ΜΑΘΗΜΑΤΙΚΗ μέθοδος. Δύσκολη, αλλά ασφαλής.
- Η ΕΜΠΕΙΡΙΚΗ μέθοδος. Ευκολότερη, αλλά δεν μας δίνει σίγουρη απάντηση. Κατάλληλη για προγράμματα.
- Χρησιμοποιώντας ΥΠΑΡΧΟΝΤΕΣ ΟΡΘΟΥΣ αλγόριθμους στην κατασκευή νέων, διευκολύνουμε την απόδειξη της οθρότητάς τους
ΠΡΟΒΛΗΜΑ ΛΟΓΙΚΗΣ 1
Έστω ότι υπάρχουν δύο ομάδες ανθρώπων. Οι Ειλικρινείς και οι Ψεύτες.
Κάθε ειλικρινής άνθρωπος λέει πάντα την αλήθεια και μόνο την αλήθεια.
Κάθε ψεύτης άνθρωπος λέει πάντα ψέματα και μόνο ψέματα.
Δεν υπάρχουν άνθρωποι που να είναι ταυτόχρονα ειλικρινείς και ψεύτες.
Ο Νίκος λέει: "Η Μαρία και εγώ ανήκουμε στην ίδια ομάδα".
Σε ποιά ομάδα ανήκει η Μαρία;
ΠΡΟΒΛΗΜΑ ΛΟΓΙΚΗΣ 2
Στις ομάδες του παραπάνω προβλήματος, ρωτήσαμε το Νίκο σε ποιά ομάδα ανήκει και μας απάντησε:
"Ανήκω στους ψεύτες"
Σε ποιά ομάδα ανήκει ο Νίκος;
Εξέτασε πρώτα την περίπτωση να μας είπε την αλήθεια και μετά την περίπτωση να μας είπε ψέματα
Η ΔΥΝΑΜΗ ΤΗΣ ΛΟΓΙΚΗΣ
Στο πρόβλημα 1, καταλήξαμε σε ένα συμπέρασμα απόλυτα ΒΕΒΑΙΟ, αλλά ΚΑΘΟΛΟΥ ΠΡΟΦΑΝΕΣ.
Η ΑΔΥΝΑΜΙΑ ΤΗΣ ΛΟΓΙΚΗΣ
Στο πρόβλημα 2, καταλήξαμε σε δύο αντικρουόμενες απαντήσεις. Αυτό λέγεται ΠΑΡΑΔΟΞΟ και δείχνει τα όρια της λογικής.
ΠΡΟΒΛΗΜΑ ΛΟΓΙΚΗΣ 3
Αν ο Νίκος μας απαντούσε:
"Η Μαρία και εγώ ανήκουμε στους ψεύτες"
τι συμπέρασμα θα βγάζαμε;
Η πρόταση αυτή μας οδηγεί σε ένα σίγουρο συμπέρασμα ή μήπως μας οδηγεί σε παράδοξο;
ΤΑΧΥΤΗΤΑ ΑΛΓΟΡΙΘΜΩΝ
Όλοι οι αλγόριθμοι έχουν την ίδια ταχύτητα.
- ΣΩΣΤΟ
- ΛΑΘΟΣ
Η ταχύτητα των αλγορίθμων εξαρτάται από το πλήθος των εντολών/βημάτων που εκτελούν μέχρι να καταλήξουν στο αποτέλεσμα.
Για το ίδιο πρόβλημα,
καλύτερος είναι ο αλγόριθμος που το λύνει με τα λιγότερα βήματα.
Η ταχύτητα των αλγορίθμων ΔΕΝ εξαρτάται από την ταχύτητα του υπολογιστή.
Το πλήθος των βημάτων που εκτελεί ένας αλγόριθμος μέχρι να φτάσει στο αποτέλεσμα, εξαρτάται από το πλήθος των δεδομένων του.
Εκτός από τα άλυτα, υπάρχουν και προβλήματα που οι αλγόριθμοι τους είναι τόσο αργοί που είναι πρακτικά μη εφαρμόσιμοι.
Διάσημο είναι το "πρόβλημα του περιοδεύοντος πωλητή"(traveling salesman problem)
Τέτοιο είναι και το πρόβλημα του σπασίματος των κωδικών που έχουν κρυπτογραφηθεί με σύγχρονο τρόπο.
Αυτό τους κάνει ασφαλείς!!!
ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ "ΠΕΡΙΟΔΕΥΟΝΤΟΣ ΠΩΛΗΤΗ"
Ένας πωλητής θα πρέπει να επισκεφτεί ένα σύνολο πόλεων, των οποίων γνωρίζουμε τον τρόπο διασύνδεσης και τις αποστάσεις μεταξύ τους.
Ποιος είναι ο συντομότερος δρόμος για να επισκεφτεί ο πωλητής ΟΛΕΣ τις πόλεις;
ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ "ΠΕΡΙΟΔΕΥΟΝΤΟΣ ΠΩΛΗΤΗ"
Ένας απλός αλγόριθμος, θα υπολόγιζε τις αποστάσεις όλων των δυνατών διαδρομών, και θα έβρισκε τη μικρότερη.
Αν Ν είναι το πλήθος των πόλεων, τότε οι πιθανές διαδρομές είναι (Ν-1)! δηλ 1 Χ 2 Χ 3 Χ ... (Ν-1)
Για 20 πόλεις θα πρέπει να εξετάσουμε 19!=121.645.100.408.832.000 διαδρομές.
Ένας σύγχρονος υπολογιστής που μπορεί να εξετάσει 1.000.000.000 διαδρομές το δευτερόλεπτο, θα χρειαζόνταν περίπου 4 χρόνια για να βρει τη λύση!!!
Το πλήθος των βημάτων που απαιτεί ένας αλγόριθμος, αποτελεί την ΠΟΛΥΠΛΟΚΟΤΗΤΑ του.