Εξηγούνται αλγόριθμοι Brute Force

Οι αλγόριθμοι Brute Force είναι ακριβώς αυτό που ακούγονται - απλές μέθοδοι επίλυσης ενός προβλήματος που βασίζονται σε καθαρή υπολογιστική ισχύ και δοκιμάζουν κάθε δυνατότητα παρά προηγμένες τεχνικές για τη βελτίωση της αποτελεσματικότητας.

Για παράδειγμα, φανταστείτε ότι έχετε ένα μικρό λουκέτο με 4 ψηφία, το καθένα από 0-9. Ξεχάσατε τον συνδυασμό σας, αλλά δεν θέλετε να αγοράσετε άλλο λουκέτο. Επειδή δεν μπορείτε να θυμηθείτε κανένα από τα ψηφία, πρέπει να χρησιμοποιήσετε μια μέθοδο brute force για να ανοίξετε το κλείδωμα.

Ορίστε λοιπόν όλους τους αριθμούς πίσω στο 0 και δοκιμάστε τους έναν προς έναν: 0001, 0002, 0003 και ούτω καθεξής έως ότου ανοίξει. Στη χειρότερη περίπτωση, θα χρειαστούν 104 ή 10.000 προσπάθειες για να βρείτε τον συνδυασμό σας.

Ένα κλασικό παράδειγμα στην επιστήμη των υπολογιστών είναι το πρόβλημα του πωλητή ταξιδιών (TSP). Ας υποθέσουμε ότι ένας πωλητής πρέπει να επισκεφθεί 10 πόλεις σε ολόκληρη τη χώρα. Πώς καθορίζει κανείς τη σειρά με την οποία πρέπει να επισκεφθούν αυτές τις πόλεις έτσι ώστε να ελαχιστοποιηθεί η συνολική απόσταση που διανύθηκε;

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

Η χρονική πολυπλοκότητα της ωμής δύναμης είναι O (m n ) , η οποία μερικές φορές γράφεται ως O (n * m). Επομένως, εάν επρόκειτο να αναζητήσουμε μια συμβολοσειρά χαρακτήρων "n" σε μια σειρά χαρακτήρων "m" χρησιμοποιώντας brute force, θα χρειαζόταν n * m προσπάθειες.

Περισσότερες πληροφορίες για αλγόριθμους

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

Δείτε πώς τα ορίζει η Wikipedia:

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

Υπάρχουν ορισμένες απαιτήσεις που πρέπει να τηρεί ένας αλγόριθμος:

  1. Οριστικότητα: Κάθε βήμα της διαδικασίας δηλώνεται με ακρίβεια.
  2. Αποτελεσματική συμβατότητα: Κάθε βήμα της διαδικασίας μπορεί να πραγματοποιηθεί από έναν υπολογιστή.
  3. Περιοχή: Το πρόγραμμα τελικά θα τερματιστεί με επιτυχία.

Μερικοί συνηθισμένοι τύποι αλγορίθμων περιλαμβάνουν:

  • αλγόριθμοι ταξινόμησης
  • αλγόριθμοι αναζήτησης
  • αλγόριθμοι συμπίεσης.

Οι κατηγορίες αλγορίθμων περιλαμβάνουν

  • Γραφική παράσταση
  • Δυναμικός προγραμματισμός
  • Ταξινόμηση
  • Ερευνητικός
  • Χορδές
  • Μαθηματικά
  • Υπολογιστική Γεωμετρία
  • Βελτιστοποίηση
  • Διάφορα.

Αν και τεχνικά δεν είναι μια κατηγορία αλγορίθμων, οι Δομές Δεδομένων συχνά ομαδοποιούνται μαζί τους.

Αποδοτικότητα

Οι αλγόριθμοι συνήθως εκτιμώνται από την αποτελεσματικότητά τους και το μέγεθος των πόρων υπολογιστών που χρειάζονται για την ολοκλήρωση της εργασίας τους.

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

Αλγόριθμοι ταξινόμησης

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

Γρήγορη ταξινόμηση

Δεν υπάρχει συζήτηση ταξινόμησης που μπορεί να ολοκληρωθεί χωρίς γρήγορη ταξινόμηση. Εδώ είναι η βασική ιδέα: Quick Sort

Συγχώνευση

Ένας αλγόριθμος ταξινόμησης που βασίζεται στην ιδέα του πώς να ταξινομηθούν οι πίνακες συγχωνεύονται για να δώσουν έναν ταξινομημένο πίνακα. Διαβάστε περισσότερα για αυτό εδώ: Mergesort

Το πρόγραμμα σπουδών του freeCodeCamp δίνει ιδιαίτερη έμφαση στη δημιουργία αλγορίθμων. Αυτό συμβαίνει επειδή οι αλγόριθμοι εκμάθησης είναι ένας καλός τρόπος για να εξασκηθείτε στις δεξιότητες προγραμματισμού. Οι ερευνητές συνήθως δοκιμάζουν υποψήφιους αλγόριθμους κατά τη διάρκεια συνεντεύξεων για προγραμματιστές.

Βιβλία για αλγόριθμους σε JavaScript:

Δομές δεδομένων σε JavaScript

  • Δωρεάν βιβλίο που καλύπτει τις δομές δεδομένων σε JavaScript
  • GitBook

Εκμάθηση δομών και αλγορίθμων δεδομένων JavaScript - Δεύτερη έκδοση

  • Καλύπτει αντικειμενοστραφή προγραμματισμό, πρωτότυπη κληρονομιά, αλγόριθμους ταξινόμησης και αναζήτησης, γρήγορη ταξινόμηση, συγχώνευση, δέντρα δυαδικής αναζήτησης και προηγμένες έννοιες αλγορίθμων
  • Αμαζόνα
  • ISBN-13: 978-1785285493

Δομές δεδομένων και αλγόριθμοι με JavaScript: Φέρνοντας κλασικές προσεγγίσεις υπολογιστών στον Ιστό

  • Καλύπτει αλγόριθμους αναδρομής, ταξινόμησης και αναζήτησης, συνδεδεμένων λιστών και δυαδικών δέντρων αναζήτησης.
  • Αμαζόνα
  • ISBN-13: 978-1449364939