Τους χρησιμοποιούμε καθημερινά κι ας μη συνειδητοποιούμε
Ακόμη κι αν δεν το συνειδητοποιούμε, οι αλγόριθμοι κυριαρχούν στην καθημερινότητά μας.
Τι είναι όμως ο αλγόριθμος;
Ως αλγόριθμος ορίζεται μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύουν στην επίλυση ενός προβλήματος. Πιο απλά αλγόριθμο ονομάζουμε μία σειρά από εντολές που έχουν αρχή και τέλος, είναι σαφείς και εκτελέσιμες που σκοπό έχουν την επίλυση κάποιου προβλήματος.
Οι αλγόριθμοι θα πρέπει να πληρούν κάποια πρότυπα και να διατυπώνονται με συγκεκριμένο τρόπο.
Έτσι ένας αλγόριθμος πρέπει να ικανοποιεί τα επόμενα κριτήρια:
-Καθοριστικότητα: Κάθε κανόνας του ορίζεται επακριβώς και η αντίστοιχη διεργασία είναι συγκεκριμένη. Κάθε εντολή πρέπει να καθορίζεται χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσής της.
-Περατότητα: Κάθε εκτέλεση είναι πεπερασμένη, δηλαδή τελειώνει ύστερα από έναν πεπερασμένο αριθμό διεργασιών ή βημάτων. Μία διαδικασία που δεν τελειώνει μετά από συγκεκριμένο/πεπερασμένο αριθμό βημάτων λέγεται απλά υπολογιστική διαδικασία.
-Αποτελεσματικότητα: Είναι μηχανιστικά αποτελεσματικός, δηλαδή όλες οι διαδικασίες που περιλαμβάνει μπορούν να πραγματοποιηθούν με ακρίβεια και σε πεπερασμένο χρόνο «με μολύβι και χαρτί». Κάθε μεμονωμένη εντολή του αλγορίθμου να είναι απλή (και όχι σύνθετη). Δηλαδή μία εντολή δεν αρκεί να έχει ορισθεί αλλά πρέπει να είναι και εκτελέσιμη.
-Επεκτασιμότητα: Κατά την εκκίνηση εκτέλεσης του αλγορίθμου καμία, μία ή περισσότερες τιμές δεδομένων πρέπει να δίνονται ως είσοδοι στον αλγόριθμο. Η περίπτωση που δε δίνονται τιμές δεδομένων εμφανίζεται όταν ο αλγόριθμος δημιουργεί και επεξεργάζεται κάποιες πρωτογενείς τιμές με τη βοήθεια συναρτήσεων παραγωγής τυχαίων αριθμών ή με τη βοήθεια άλλων απλών εντολών.
-Να έχει είσοδο δεδομένων, επεξεργασία και έξοδο αποτελεσμάτων: Δίδει τουλάχιστον ένα μέγεθος ως αποτέλεσμα που εξαρτάται κατά κάποιο τρόπο από τις αρχικές εισόδους. Ο αλγόριθμος πρέπει να δημιουργεί τουλάχιστον μία τιμή (δεδομένων) ως αποτέλεσμα προς το χρήστη ή προς ένα άλλο αλγόριθμο.
(Πηγή: Wikipedia)
Δείτε παρακάτω ποιοι είναι οι πιο κοινοί αλγόριθμοι που χρησιμοποιούμε στην καθημερινότητά μας, σύμφωνα με δημοσίευμα στον ιστότοπο medium.com.
1. Merge Sort, Quick Sort και Heap Sort (αλγόριθμος ταξινόμησης στοιχείων)
Η ταξινόμηση με συγχώνευση (Merge Sort) είναι ένας από τους πιο σημαντικούς αλγορίθμους που έχουμε. Πρόκειται για ένα αλγόριθμο ταξινόμησης που βασίζεται στη σύγκριση που χρησιμοποιεί την προσέγγιση του διαίρει και βασίλευε. Εφευρέθηκε από το μαθηματικό John von Neumann το 1945.
Ο αλγόριθμος Quick Sort είναι μια διαφορετική προσέγγιση στο πρόβλημα διαλογής. Μπορεί να χρησιμοποιήσει in-place partition αλγόριθμους και είναι επίσης ένας διαίρει και βασίλευε αλγόριθμος. Το πρόβλημα με αυτόν τον αλγόριθμο είναι ότι δεν είναι σταθερός, αλλά είναι πολύ αποτελεσματικός για τη διαλογή RAM-based συστοιχιών.
Ο αλγόριθμος Heap Sort χρησιμοποιεί μια σειρά προτεραιότητας που μειώνει το χρόνο αναζήτησης στα δεδομένα.
2. Fourier Transform και Fast Fourier Transform (Μετασχηματισμός Φουριέ)
Ολόκληρος ο ψηφιακός κόσμος χρησιμοποιεί αυτούς τους απλούς αλλά πολύ ισχυρούς αλγόριθμους, που μετατρέπουν τα σήματα από το πεδίο του χρόνου τους στο πεδίο της συχνότητας τους και το αντίστροφο.
Το διαδίκτυο, τα ασύρματα δίκτυα, οι έξυπνες συσκευές, τα τηλέφωνα, οι υπολογιστές, τα router, οι δορυφόροι και οτιδήποτε άλλο έχει μέσα του έναν υπολογιστή, χρησιμοποιεί αυτούς τους αλγόριθμους με κάποιο τρόπο για να λειτουργήσει.
3. Αλγόριθμος Dijkstra
Ο αλγόριθμος του Ντάικστρα (Dijkstra) πήρε το όνομά του από τον Ολλανδό Έντσγκερ Ντάικστρα, ο οποίος τον επινόησε το 1956 και τον δημοσίευσε το 1959. Πρόκειται για έναν αλγόριθμο εύρεσης συντομότερων διαδρομών (single-source shortest path problem) από κοινή αφετηρία σε έναν (κατευθυνόμενο ή μη) γράφο με μη αρνητικά βάρη στις ακμές. Ο αλγόριθμος του Dijkstra είναι άπληστος. Δηλαδή, σε κάθε βήμα επιλέγει την τοπικά βέλτιστη λύση, ώσπου στο τελευταίο βήμα συνθέτει μια συνολικά βέλτιστη λύση. Αν ο γράφος περιέχει αρνητικά βάρη, ο αλγόριθμος του Ντάικστρα δεν δίνει σωστό αποτέλεσμα. Για γράφους που μπορεί να έχουν αρνητικά βάρη στις ακμές, χρησιμοποιούνται πιο περίπλοκοι αλγόριθμοι, όπως αυτός των Bellman και Ford ή των Floyd-Warshall.
Ο αλγόριθμος του Ντάικστρα είναι πλέον ευρέως διαδεδομένος και χρησιμοποιείται σε πολλές εφαρμογές. Χρήση του αλγόριθμου αυτού κάνει το πρωτόκολλο OSPF, το οποίο είναι το εσωτερικό πρωτόκολλο πύλης δικτύου του Διαδικτύου, αναφέρει η Wikipedia.
4. Αλγόριθμος RSA
Ο RSA είναι ένας κρυπταλγόριθμος ασύμμετρου κλειδιού, το όνομα του οποίου προέρχεται από τους δημιουργούς του, Ron Rivest, Adi Shamir and Len Adleman. Επιτρέπει όχι μόνο την κωδικοποίηση μηνυμάτων αλλά μπορεί επίσης να χρησιμοποιηθεί και ως ψηφιακή υπογραφή, σημειώνει η ίδια πηγή.
Ο αλγόριθμος RSA αποτελεί μια λύση σε ένα απλό αλλά σύνθετο πρόβλημα: πώς να μοιράζονται δημόσια κλειδιά μεταξύ ανεξάρτητων πλατφορμών και των τελικών χρηστών, προκειμένου να καταστεί δυνατή κρυπτογραφία.
5. Secure Hash αλγόριθμος
Αυτό δεν είναι ακριβώς ένας αλγόριθμος, αλλά μια οικογένεια κρυπτογραφικών συναρτήσεων κατακερματισμού που αναπτύχθηκε από το National Institute of Standards and Technology (NIST) στις ΗΠΑ.
Η οικογένεια αυτή αλγόριθμων είναι θεμελιώδους σημασίας: από τα app store, το ηλεκτρονικό ταχυδρομείο, τα antivirus, τους browser κ.τ.λ. τα πάντα λειτουργούν χάρη σε αυτούς τους αλγόριθμους.
6. Link Analysis
Η ανάλυση συνδέσμων (link analysis) είναι ένας αλγόριθμος που συνοδεύεται με τους περισσότερους μύθους και σύγχυση στο ευρύ κοινό. Το πρόβλημα είναι ότι υπάρχουν διαφορετικοί τρόποι για να γίνει η ανάλυση συνδέσμων και υπάρχουν επίσης χαρακτηριστικά που καθιστούν κάθε αλγόριθμο κάπως διαφορετικό, αλλά στη βάση τους είναι παρόμοιοι.
Η ιδέα πίσω από την ανάλυση συνδέσμου είναι απλή: μπορεί να εκπροσωπεί ένα γράφημα σε μορφή Matrix καθιστώντας το ένα πρόβλημα ιδιοτιμών. Οι ιδιοτιμές μπορεί να δώσουν μια πραγματικά καλή προσέγγιση της δομής του γραφήματος και τη σχετική σημασία του κάθε κόμβου. Ο αλγόριθμος αναπτύχθηκε το 1976 από τους Gabriel Pinski και Francis Narin.
Τι είναι όμως ο αλγόριθμος;
Ως αλγόριθμος ορίζεται μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύουν στην επίλυση ενός προβλήματος. Πιο απλά αλγόριθμο ονομάζουμε μία σειρά από εντολές που έχουν αρχή και τέλος, είναι σαφείς και εκτελέσιμες που σκοπό έχουν την επίλυση κάποιου προβλήματος.
Οι αλγόριθμοι θα πρέπει να πληρούν κάποια πρότυπα και να διατυπώνονται με συγκεκριμένο τρόπο.
Έτσι ένας αλγόριθμος πρέπει να ικανοποιεί τα επόμενα κριτήρια:
-Καθοριστικότητα: Κάθε κανόνας του ορίζεται επακριβώς και η αντίστοιχη διεργασία είναι συγκεκριμένη. Κάθε εντολή πρέπει να καθορίζεται χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσής της.
-Περατότητα: Κάθε εκτέλεση είναι πεπερασμένη, δηλαδή τελειώνει ύστερα από έναν πεπερασμένο αριθμό διεργασιών ή βημάτων. Μία διαδικασία που δεν τελειώνει μετά από συγκεκριμένο/πεπερασμένο αριθμό βημάτων λέγεται απλά υπολογιστική διαδικασία.
-Αποτελεσματικότητα: Είναι μηχανιστικά αποτελεσματικός, δηλαδή όλες οι διαδικασίες που περιλαμβάνει μπορούν να πραγματοποιηθούν με ακρίβεια και σε πεπερασμένο χρόνο «με μολύβι και χαρτί». Κάθε μεμονωμένη εντολή του αλγορίθμου να είναι απλή (και όχι σύνθετη). Δηλαδή μία εντολή δεν αρκεί να έχει ορισθεί αλλά πρέπει να είναι και εκτελέσιμη.
-Επεκτασιμότητα: Κατά την εκκίνηση εκτέλεσης του αλγορίθμου καμία, μία ή περισσότερες τιμές δεδομένων πρέπει να δίνονται ως είσοδοι στον αλγόριθμο. Η περίπτωση που δε δίνονται τιμές δεδομένων εμφανίζεται όταν ο αλγόριθμος δημιουργεί και επεξεργάζεται κάποιες πρωτογενείς τιμές με τη βοήθεια συναρτήσεων παραγωγής τυχαίων αριθμών ή με τη βοήθεια άλλων απλών εντολών.
-Να έχει είσοδο δεδομένων, επεξεργασία και έξοδο αποτελεσμάτων: Δίδει τουλάχιστον ένα μέγεθος ως αποτέλεσμα που εξαρτάται κατά κάποιο τρόπο από τις αρχικές εισόδους. Ο αλγόριθμος πρέπει να δημιουργεί τουλάχιστον μία τιμή (δεδομένων) ως αποτέλεσμα προς το χρήστη ή προς ένα άλλο αλγόριθμο.
(Πηγή: Wikipedia)
Δείτε παρακάτω ποιοι είναι οι πιο κοινοί αλγόριθμοι που χρησιμοποιούμε στην καθημερινότητά μας, σύμφωνα με δημοσίευμα στον ιστότοπο medium.com.
1. Merge Sort, Quick Sort και Heap Sort (αλγόριθμος ταξινόμησης στοιχείων)
Η ταξινόμηση με συγχώνευση (Merge Sort) είναι ένας από τους πιο σημαντικούς αλγορίθμους που έχουμε. Πρόκειται για ένα αλγόριθμο ταξινόμησης που βασίζεται στη σύγκριση που χρησιμοποιεί την προσέγγιση του διαίρει και βασίλευε. Εφευρέθηκε από το μαθηματικό John von Neumann το 1945.
Ο αλγόριθμος Quick Sort είναι μια διαφορετική προσέγγιση στο πρόβλημα διαλογής. Μπορεί να χρησιμοποιήσει in-place partition αλγόριθμους και είναι επίσης ένας διαίρει και βασίλευε αλγόριθμος. Το πρόβλημα με αυτόν τον αλγόριθμο είναι ότι δεν είναι σταθερός, αλλά είναι πολύ αποτελεσματικός για τη διαλογή RAM-based συστοιχιών.
Ο αλγόριθμος Heap Sort χρησιμοποιεί μια σειρά προτεραιότητας που μειώνει το χρόνο αναζήτησης στα δεδομένα.
2. Fourier Transform και Fast Fourier Transform (Μετασχηματισμός Φουριέ)
Ολόκληρος ο ψηφιακός κόσμος χρησιμοποιεί αυτούς τους απλούς αλλά πολύ ισχυρούς αλγόριθμους, που μετατρέπουν τα σήματα από το πεδίο του χρόνου τους στο πεδίο της συχνότητας τους και το αντίστροφο.
Το διαδίκτυο, τα ασύρματα δίκτυα, οι έξυπνες συσκευές, τα τηλέφωνα, οι υπολογιστές, τα router, οι δορυφόροι και οτιδήποτε άλλο έχει μέσα του έναν υπολογιστή, χρησιμοποιεί αυτούς τους αλγόριθμους με κάποιο τρόπο για να λειτουργήσει.
3. Αλγόριθμος Dijkstra
Ο αλγόριθμος του Ντάικστρα (Dijkstra) πήρε το όνομά του από τον Ολλανδό Έντσγκερ Ντάικστρα, ο οποίος τον επινόησε το 1956 και τον δημοσίευσε το 1959. Πρόκειται για έναν αλγόριθμο εύρεσης συντομότερων διαδρομών (single-source shortest path problem) από κοινή αφετηρία σε έναν (κατευθυνόμενο ή μη) γράφο με μη αρνητικά βάρη στις ακμές. Ο αλγόριθμος του Dijkstra είναι άπληστος. Δηλαδή, σε κάθε βήμα επιλέγει την τοπικά βέλτιστη λύση, ώσπου στο τελευταίο βήμα συνθέτει μια συνολικά βέλτιστη λύση. Αν ο γράφος περιέχει αρνητικά βάρη, ο αλγόριθμος του Ντάικστρα δεν δίνει σωστό αποτέλεσμα. Για γράφους που μπορεί να έχουν αρνητικά βάρη στις ακμές, χρησιμοποιούνται πιο περίπλοκοι αλγόριθμοι, όπως αυτός των Bellman και Ford ή των Floyd-Warshall.
Ο αλγόριθμος του Ντάικστρα είναι πλέον ευρέως διαδεδομένος και χρησιμοποιείται σε πολλές εφαρμογές. Χρήση του αλγόριθμου αυτού κάνει το πρωτόκολλο OSPF, το οποίο είναι το εσωτερικό πρωτόκολλο πύλης δικτύου του Διαδικτύου, αναφέρει η Wikipedia.
4. Αλγόριθμος RSA
Ο RSA είναι ένας κρυπταλγόριθμος ασύμμετρου κλειδιού, το όνομα του οποίου προέρχεται από τους δημιουργούς του, Ron Rivest, Adi Shamir and Len Adleman. Επιτρέπει όχι μόνο την κωδικοποίηση μηνυμάτων αλλά μπορεί επίσης να χρησιμοποιηθεί και ως ψηφιακή υπογραφή, σημειώνει η ίδια πηγή.
Ο αλγόριθμος RSA αποτελεί μια λύση σε ένα απλό αλλά σύνθετο πρόβλημα: πώς να μοιράζονται δημόσια κλειδιά μεταξύ ανεξάρτητων πλατφορμών και των τελικών χρηστών, προκειμένου να καταστεί δυνατή κρυπτογραφία.
5. Secure Hash αλγόριθμος
Αυτό δεν είναι ακριβώς ένας αλγόριθμος, αλλά μια οικογένεια κρυπτογραφικών συναρτήσεων κατακερματισμού που αναπτύχθηκε από το National Institute of Standards and Technology (NIST) στις ΗΠΑ.
Η οικογένεια αυτή αλγόριθμων είναι θεμελιώδους σημασίας: από τα app store, το ηλεκτρονικό ταχυδρομείο, τα antivirus, τους browser κ.τ.λ. τα πάντα λειτουργούν χάρη σε αυτούς τους αλγόριθμους.
6. Link Analysis
Η ανάλυση συνδέσμων (link analysis) είναι ένας αλγόριθμος που συνοδεύεται με τους περισσότερους μύθους και σύγχυση στο ευρύ κοινό. Το πρόβλημα είναι ότι υπάρχουν διαφορετικοί τρόποι για να γίνει η ανάλυση συνδέσμων και υπάρχουν επίσης χαρακτηριστικά που καθιστούν κάθε αλγόριθμο κάπως διαφορετικό, αλλά στη βάση τους είναι παρόμοιοι.
Η ιδέα πίσω από την ανάλυση συνδέσμου είναι απλή: μπορεί να εκπροσωπεί ένα γράφημα σε μορφή Matrix καθιστώντας το ένα πρόβλημα ιδιοτιμών. Οι ιδιοτιμές μπορεί να δώσουν μια πραγματικά καλή προσέγγιση της δομής του γραφήματος και τη σχετική σημασία του κάθε κόμβου. Ο αλγόριθμος αναπτύχθηκε το 1976 από τους Gabriel Pinski και Francis Narin.
|
|
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου