Τι είναι αλγόριθμος

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

Η λέξη αλγόριθμος προέρχεται από μία διατριβή του Πέρση μαθηματικού Μοχάμεντ ιμπν Μουσά αλ-Χουαρίζμι, η οποία περιείχε συστηματικές τυποποιημένες λύσεις αλγεβρικών προβλημάτων και αποτελεί ίσως την πρώτη πλήρη πραγματεία άλγεβρας. Ο πλέον γνωστός ιστορικά αλγόριθμος είναι ο αλγόριθμος του Ευκλείδη για τον υπολογισμό του Μέγιστου Κοινού Διαιρέτη δύο ακεραίων.

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

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

Τι είναι ένα Πρόβλημα;

Ένα πρόβλημα στην πληροφορική είναι μια γενική περιγραφή ενός υπολογιστικού ζητήματος που θέλουμε να λύσουμε. Το πρόβλημα είναι η γενική διατύπωση (π.χ., “ταξινόμησε μια λίστα”). Περιλαμβάνει:

• Μια είσοδο (input): Τι δεδομένα λαμβάνει ο αλγόριθμος.
• Μια έξοδο (output): Τι αποτέλεσμα πρέπει να παράγει.
• Μια σχέση εισόδου-εξόδου: Τους κανόνες που καθορίζουν αν μια απάντηση είναι σωστή.

Τι είναι ένα Στιγμιότυπο (Instance);

Ένα στιγμιότυπο είναι μια συγκεκριμένη περίπτωση ενός προβλήματος, δηλαδή μια συγκεκριμένη είσοδος για την οποία θέλουμε να βρούμε την απάντηση. Το στιγμιότυπο είναι μια συγκεκριμένη περίπτωση του προβλήματος

Παράδειγμα Στιγμιότυπου: Για το παραπάνω πρόβλημα της ταξινόμησης, ένα στιγμιότυπο θα μπορούσε να είναι η λίστα: [5, 3, 8, 1, 4] και η επιθυμητή έξοδος θα ήταν: [1, 3, 4, 5, 8]

Πολυπλοκότητα ενός Αλγορίθμου

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

1. Χρονική Πολυπλοκότητα (Time Complexity) – Πόσο χρόνο χρειάζεται ο αλγόριθμος για να εκτελεστεί.
2. Χωρική Πολυπλοκότητα (Space Complexity) – Πόση μνήμη (RAM) χρησιμοποιεί ο αλγόριθμος.

Η πολυπλοκότητα ενός αλγορίθμου αναφέρεται κυρίως σε χρόνο (time complexity) και μνήμη (space complexity) επειδή αυτά είναι οι δύο κύριοι θεωρητικοί περιορισμοί στους υπολογισμούς. Ωστόσο, οι επεξεργαστές (CPU) επηρεάζουν την πραγματική ταχύτητα εκτέλεσης, αλλά δεν είναι άμεσα μέρος της θεωρητικής ανάλυσης πολυπλοκότητας.

Η πολυπλοκότητα ενός Αλγορίθμου είναι ανεξάρτητη από το hardware

Ένας παλιός επεξεργαστής και ένας μοντέρνος μπορεί να εκτελούν τον ίδιο αλγόριθμο με διαφορετικούς χρόνους, αλλά η πολυπλοκότητα παραμένει ίδια. Αν ένας αλγόριθμος τρέχει σειριακά, δεν έχει σημασία αν έχεις 1 ή 100 πυρήνες. Ο αριθμός των επεξεργαστών (πυρήνων) επηρεάζει μόνο παραλληλισμένους αλγορίθμους (Parallel Computing). Αν ένας αλγόριθμος διασπάται σε πολλαπλές διεργασίες (threads), τότε η ταχύτητα του επξεργαστή CPU επηρεάζει την απόδοση. Π.χ., ένας Ryzen 9 7950X τρέχει μια δυαδική αναζήτηση γρηγορότερα από έναν Intel i5, αλλά η πολυπλοκότητα παραμένει ίδια.

Αλγόριθμοι που χρησιμοποιείς Καθημερινά

Καθημερινά, είτε το καταλαβαίνουμε είτε όχι, χρησιμοποιούμε αλγορίθμους παντού! Ακόλουθα παραθέτω μερικούς αλγόριθμους που χρησιμοποιούμε σχεδόν κάθε μέρα:

• Αλγόριθμοι Αναζήτησης
  • Google Search (PageRank Algorithm)
  • Αναζήτηση αρχείων στον υπολογιστή
• Αλγόριθμοι Ταξινόμησης
  • Ταξινόμηση email & μηνυμάτων
  • Σε ηλεκτρονικά καταστήματα ταξινόμηση προιόντων ανά τιμή
• Αλγόριθμοι Πρόβλεψης & AI
  • Συστάσεις στις πλατφόρμες Netflix, YouTube & Spotify
• Αλγόριθμοι Δρομολόγησης
  • Dijkstra, υπολογίσμος συντομότερης διαδρομής σε Google Maps
• Αλγόριθμοι Κρυπτογράφησης & Ασφάλειας
  • Τραπεζικές Συναλλαγές (AES, RSA, SHA-256) χρησιμοποιούν μαθηματικούς αλγορίθμους για ασφάλεια
  • Το HTTPS (TLS) προστατεύει τις ιστοσελίδες από επιθέσεις.
• Αλγόριθμοι Συμπίεσης & Μετάδοσης Δεδομένων
  • Όταν βλέπεις Netflix ή YouTube, τα βίντεο συμπιέζονται για γρηγορότερο streaming (H.264, H.265, AV1)
  • Wi-Fi & 5G

Οι Αλγόριθμοι είναι παντού! Ακόμα κι αν δεν το συνειδητοποιούμε, κάθε φορά που χρησιμοποιούμε το κινητό ή το laptop μας, τρέχουν χιλιάδες αλγόριθμοι στο παρασκήνιο.