Η έννοια του αλγορίθμου. Προγραμματισμός

Ενότητες του ιστότοπου

Η επιλογή των συντακτών:

Διαφήμιση

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

Το πρώτο βήμα για την κατανόηση της σημασίας της μελέτης και της γνώσης αλγορίθμων είναι να ορίσουμε με ακρίβεια τι σημαίνει ένας αλγόριθμος. Ένας αλγόριθμος στον προγραμματισμό είναι σαφή και ακριβή σειρά ενεργειώνγραμμένο σε γλώσσα προγραμματισμού Σύμφωνα με το δημοφιλές βιβλίο Algorithms: Construction and Analysis (Cormen, Leiserson, Rivest, Stein), «αλγόριθμος είναι κάθε καλά καθορισμένη υπολογιστική διαδικασία της οποίας η είσοδος δίνεται σε μια ορισμένη ποσότητα ή σύνολο ποσοτήτων. αποτέλεσμα της οποίας είναι μια τιμή εξόδου ή ένα σύνολο τιμών." Με άλλα λόγια, οι αλγόριθμοι είναι σαν τους οδικούς χάρτες για την επίτευξη ενός σαφώς καθορισμένου στόχου. Ο κώδικας για τον υπολογισμό των όρων της ακολουθίας Fibonacci είναι μια υλοποίηση ενός συγκεκριμένου αλγορίθμου. Ακόμη και μια απλή συνάρτηση της πρόσθεσης δύο αριθμών είναι αλγόριθμος, αν και απλός.

Για να δημιουργήσετε έναν αλγόριθμο (πρόγραμμα), πρέπει να γνωρίζετε:

ένα πλήρες σύνολο αρχικών δεδομένων εργασίας (αρχική κατάσταση του αντικειμένου).

ο σκοπός της δημιουργίας του αλγορίθμου (η τελική κατάσταση του αντικειμένου).

το σύστημα εντολών του εκτελεστή (δηλαδή, ένα σύνολο εντολών που ο εκτελεστής κατανοεί και μπορεί να εκτελέσει).

Ο αλγόριθμος (πρόγραμμα) που προκύπτει πρέπει να έχει το ακόλουθο σύνολο ιδιοτήτων:

διακριτικότητα(ο αλγόριθμος χωρίζεται σε ξεχωριστά βήματα - εντολές).

ασάφεια(κάθε εντολή καθορίζει τη μόνη δυνατή ενέργεια του εκτελεστή).

σαφήνεια(όλες οι εντολές αλγορίθμου περιλαμβάνονται στο σύστημα εντολών του εκτελεστή).

αποτελεσματικότητα(ο ερμηνευτής πρέπει να λύσει το πρόβλημα σε έναν πεπερασμένο αριθμό βημάτων).

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

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

Μια γλώσσα προγραμματισμού είναι ένα σύνολο κανόνων για την καταγραφή αλγοριθμικών δομών και δεδομένων.

Ανάλυση χρόνου εκτέλεσης αλγορίθμου

Μία από τις πιο σημαντικές πτυχές του αλγορίθμου είναι η ταχύτητά του. Συχνά είναι εύκολο να βρεθεί ένας αλγόριθμος που λύνει ένα πρόβλημα, αλλά εάν ο αλγόριθμος είναι πολύ αργός, τότε επιστρέφεται για αναθεώρηση. Επειδή η ακριβής ταχύτητα ενός αλγορίθμου εξαρτάται από το πού εκτελείται ο αλγόριθμος, καθώς και από τις λεπτομέρειες υλοποίησης, οι επιστήμονες υπολογιστών συνήθως μιλούν για το χρόνο εκτέλεσης σε σχέση με τα δεδομένα εισόδου. Για παράδειγμα, εάν η είσοδος αποτελείται από N ακέραιους αριθμούς, τότε ο αλγόριθμος μπορεί να έχει χρόνο εκτέλεσης ανάλογο του N 2 , ο οποίος αναπαρίσταται ως O(N 2 ). Αυτό σημαίνει ότι εάν εκτελέσετε την υλοποίηση του αλγορίθμου σε έναν υπολογιστή με είσοδο μεγέθους N, θα χρειαστούν C*N 2 δευτερόλεπτα, όπου C είναι κάποια σταθερά που δεν αλλάζει καθώς αλλάζει το μέγεθος της εισόδου.

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

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

Ονομασία	Περιγραφή	Σημειώσεις
	Έναρξη και τέλος του αλγορίθμου
	Εισαγωγή και έξοδος δεδομένων.	Η έξοδος δεδομένων μερικές φορές αναφέρεται διαφορετικά:
	Δράση	Σε υπολογιστικούς αλγόριθμους αυτό χρησιμοποιείται για να δηλώσει την ανάθεση
	Πιρούνι	Πιρούνι - ένα εξάρτημα απαραίτητο για την εφαρμογή κλαδιών και βρόχων
	Ξεκινώντας έναν βρόχο με μια παράμετρο
	Τυπική διαδικασία	Στον προγραμματισμό - διαδικασίες ή υπορουτίνες
	Μεταβάσεις μεταξύ μπλοκ

Ακολουθεί ένα παράδειγμα περιγραφής του αλγορίθμου για την άθροιση δύο μεγεθών με τη μορφή μπλοκ διαγράμματος:

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

Ταξινόμηση

Η ταξινόμηση είναι ένα καλό παράδειγμα αλγορίθμου που χρησιμοποιείται συχνά από προγραμματιστές. Ο ευκολότερος τρόπος για να ταξινομήσετε μια ομάδα στοιχείων είναι να ξεκινήσετε αφαιρώντας το μικρότερο στοιχείο από την ομάδα και βάζοντάς το πρώτο. Στη συνέχεια, το δεύτερο μεγαλύτερο στοιχείο αφαιρείται και τοποθετείται δεύτερο και ούτω καθεξής. Δυστυχώς, ο χρόνος εκτέλεσης αυτού του αλγορίθμου είναι O(N 2), που σημαίνει ότι θα χρειαστεί χρόνος ανάλογος με τον αριθμό των στοιχείων στο τετράγωνο. Αν έπρεπε να ταξινομήσουμε δισεκατομμύρια στοιχεία, τότε αυτός ο αλγόριθμος θα απαιτούσε 10 18 πράξεις. Αν υποθέσουμε ότι οι τυπικοί επιτραπέζιοι υπολογιστές εκτελούν περίπου 109 λειτουργίες ανά δευτερόλεπτο, τότε θα χρειαστούν χρόνια για να ολοκληρωθεί η ταξινόμηση αυτών των δισεκατομμυρίων στοιχείων.

Ευτυχώς, υπάρχουν αρκετοί πιο προηγμένοι αλγόριθμοι, όπως τα Quicksort, Heapsort και mergesort. Αυτοί οι αλγόριθμοι έχουν χρόνο εκτέλεσης O(N * Log(N)). Έτσι, ο αριθμός των λειτουργιών που απαιτούνται για την ταξινόμηση δισεκατομμυρίων στοιχείων μειώνεται σε τόσο λογικά όρια που ακόμη και ο φθηνότερος επιτραπέζιος υπολογιστής μπορεί να εκτελέσει τέτοια ταξινόμηση. Αντί για ένα δισεκατομμύριο τετράγωνες πράξεις (10 18), αυτοί οι αλγόριθμοι απαιτούν μόνο 10 δισεκατομμύρια πράξεις (10 10), δηλ. 100 εκατομμύρια φορές πιο γρήγορα.

Ο συντομότερος τρόπος

Οι αλγόριθμοι για την εύρεση της συντομότερης διαδρομής από το ένα σημείο στο άλλο έχουν μελετηθεί εδώ και πολλά χρόνια. Υπάρχουν πολλά παραδείγματα εφαρμογών αυτών των αλγορίθμων, αλλά για απλότητα της παρουσίασης θα παραμείνουμε στην ακόλουθη δήλωση: πρέπει να βρούμε τη συντομότερη διαδρομή από το σημείο Α στο σημείο Β σε μια πόλη με πολλούς δρόμους και διασταυρώσεις. Υπάρχουν πολλοί διαφορετικοί αλγόριθμοι για την επίλυση αυτού του προβλήματος και όλοι έχουν τα δικά τους πλεονεκτήματα και μειονεκτήματα. Πριν βουτήξουμε σε αυτά, ας δούμε τον χρόνο εκτέλεσης ενός απλού αλγορίθμου ωμής δύναμης. Εάν ένας αλγόριθμος εξετάσει κάθε πιθανή διαδρομή από το Α στο Β (που δεν σχηματίζει κύκλους) είναι απίθανο να τελειώσει στη διάρκεια της ζωής μας, ακόμα κι αν οι Α και Β βρίσκονται σε μια μικρή πόλη. Ο χρόνος εκτέλεσης αυτού του αλγορίθμου είναι εκθετικός, ο οποίος συμβολίζεται ως O(C N) για κάποιο C. Ακόμη και για μικρές τιμές του C, το C N γίνεται αστρονομικός αριθμός όταν το N γίνεται μέτρια μεγάλο.

Ένας από τους ταχύτερους αλγόριθμους για την επίλυση αυτού του προβλήματος έχει χρόνο εκτέλεσης O(E+V*Log(V)), όπου E είναι ο αριθμός των τμημάτων του δρόμου και V είναι ο αριθμός των διασταυρώσεων. Ο αλγόριθμος θα χρειαστεί περίπου 2 δευτερόλεπτα για να βρει το συντομότερο μονοπάτι σε μια πόλη με 10.000 διασταυρώσεις και 20.000 οδικά τμήματα (συνήθως περίπου 2 οδικά τμήματα ανά διασταύρωση). Αυτός ο αλγόριθμος είναι γνωστός ως αλγόριθμος Dijkstra, είναι αρκετά περίπλοκος και απαιτεί τη χρήση μιας δομής δεδομένων ουράς προτεραιότητας. Ωστόσο, σε ορισμένες περιπτώσεις, ακόμη και αυτός ο χρόνος εκτέλεσης είναι πολύ αργός (πάρτε για παράδειγμα την εύρεση της συντομότερης διαδρομής από τη Νέα Υόρκη στο Σαν Φρανσίσκο - υπάρχουν εκατομμύρια διασταυρώσεις στις ΗΠΑ), σε τέτοιες περιπτώσεις οι προγραμματιστές προσπαθούν να βελτιώσουν τον χρόνο εκτέλεσης χρησιμοποιώντας το - που ονομάζεται ευρετική. Μια ευρετική είναι μια προσέγγιση του κάτι που σχετίζεται με μια εργασία. Σε ένα πρόβλημα συντομότερης διαδρομής, για παράδειγμα, μπορεί να είναι χρήσιμο να γνωρίζουμε πόσο απέχει ένα σημείο από έναν προορισμό. Γνωρίζοντας αυτό, μπορείτε να αναπτύξετε έναν πιο γρήγορο αλγόριθμο (για παράδειγμα, ο αλγόριθμος αναζήτησης A* σε ορισμένες περιπτώσεις λειτουργεί πολύ πιο γρήγορα από τον αλγόριθμο του Dijkstra). Αυτή η προσέγγιση δεν βελτιώνει πάντα τον χρόνο εκτέλεσης του αλγορίθμου στη χειρότερη περίπτωση, αλλά στις περισσότερες εφαρμογές του πραγματικού κόσμου ο αλγόριθμος θα εκτελείται πιο γρήγορα.

Κατά προσέγγιση αλγόριθμοι

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

Στην πραγματικότητα, υπάρχουν πολλά σημαντικά προβλήματα για τα οποία οι επί του παρόντος γνωστοί αλγόριθμοι παράγουν το βέλτιστο αποτέλεσμα πολύ αργά. Η πιο διάσημη ομάδα αυτών των προβλημάτων ονομάζεται NP (μη ντετερμινιστικό πολυώνυμο). Εάν ένα πρόβλημα ονομάζεται NP-complete ή NP-hard, σημαίνει ότι κανείς δεν γνωρίζει έναν αρκετά καλό τρόπο για να βρει τη βέλτιστη λύση. Επίσης, εάν κάποιος αναπτύξει έναν αποτελεσματικό αλγόριθμο για την επίλυση ενός προβλήματος NP-hard, τότε αυτός ο αλγόριθμος μπορεί να εφαρμοστεί σε όλα τα NP-hard προβλήματα.

Ένα καλό παράδειγμα ενός προβλήματος NP-hard είναι το πρόβλημα του ταξιδιώτη πωλητή. Ένας πωλητής θέλει να επισκεφτεί Ν πόλεις και ξέρει πόσο χρόνο χρειάζεται για να ταξιδέψει από τη μια πόλη στην άλλη. Το ερώτημα είναι πόσο γρήγορα μπορεί να επισκεφτεί όλες τις πόλεις; Ο ταχύτερος γνωστός αλγόριθμος για την επίλυση αυτού του προβλήματος είναι πολύ αργός - και πολλοί πιστεύουν ότι θα είναι πάντα - έτσι οι προγραμματιστές αναζητούν αλγόριθμους που είναι αρκετά γρήγοροι για να δώσουν μια καλή λύση, αλλά συχνά όχι τη βέλτιστη.

Τυχαίοι αλγόριθμοι

Μια άλλη προσέγγιση που χρησιμοποιείται για την επίλυση ορισμένων προβλημάτων είναι να γίνει ο αλγόριθμος τυχαίος. Αυτή η προσέγγιση δεν βελτιώνει τον χρόνο στη χειρότερη περίπτωση του αλγορίθμου, αλλά αρκετά συχνά λειτουργεί καλά στη μέση περίπτωση. Ο αλγόριθμος γρήγορης ταξινόμησης είναι ένα καλό παράδειγμα χρήσης της τυχαιοποίησης. Στη χειρότερη περίπτωση, ο αλγόριθμος γρήγορης ταξινόμησης ταξινομεί μια ομάδα στοιχείων στο O(N 2), όπου N είναι ο αριθμός των στοιχείων. Εάν χρησιμοποιείται τυχαιοποίηση σε αυτόν τον αλγόριθμο, τότε οι πιθανότητες για μια χειρότερη περίπτωση γίνονται αμελητέα μικρές και κατά μέσο όρο ο αλγόριθμος γρήγορης ταξινόμησης εκτελείται σε χρόνο O(N*Log(N)). Άλλοι αλγόριθμοι εγγυώνται χρόνο λειτουργίας O(N*Log(N)) ακόμη και στη χειρότερη περίπτωση, αλλά είναι πιο αργοί στη μέση περίπτωση. Αν και και οι δύο αλγόριθμοι έχουν χρόνο εκτέλεσης ανάλογο με το N*Log(N), ο αλγόριθμος γρήγορης ταξινόμησης έχει έναν μικρότερο σταθερό παράγοντα - π.χ. Απαιτεί C*N*Log(N), ενώ άλλοι αλγόριθμοι απαιτούν περισσότερες από 2*C*N*Log(N) πράξεις.

Ένας άλλος αλγόριθμος που χρησιμοποιεί τυχαίους αριθμούς αναζητά τη διάμεσο μιας ομάδας αριθμών και ο μέσος χρόνος εκτέλεσης της είναι O(N). Αυτό είναι πολύ πιο γρήγορο σε σύγκριση με τον αλγόριθμο που ταξινομεί τους αριθμούς και παίρνει τον μέσο όρο και εκτελείται σε O(N*Log(N)). Υπάρχουν ντετερμινιστικοί αλγόριθμοι (όχι τυχαίοι) που μπορούν να βρουν τη διάμεσο σε χρόνο O(N), αλλά ο τυχαίος αλγόριθμος είναι πιο κατανοητός και συχνά πιο γρήγορος από αυτούς τους ντετερμινιστικούς αλγόριθμους.

Η κύρια ιδέα του αλγόριθμου αναζήτησης διάμεσης είναι να επιλέξετε έναν τυχαίο αριθμό μεταξύ των αριθμών και να μετρήσετε πόσοι αριθμοί στην ομάδα είναι λιγότεροι από τον επιλεγμένο αριθμό. Ας υποθέσουμε ότι υπάρχουν N αριθμοί, οι K από αυτούς είναι μικρότεροι ή ίσοι με τον επιλεγμένο αριθμό. Αν το K είναι μικρότερο από το μισό N, τότε γνωρίζουμε ότι η διάμεσος είναι ο (N/2-K)οος αριθμός που είναι μεγαλύτερος από τον τυχαίο αριθμό, επομένως απορρίπτουμε τους K αριθμούς μικρότερους ή ίσους με τον τυχαίο αριθμό. Τώρα ας πούμε ότι θέλουμε να βρούμε τον (Ν/2-Κ)ο μικρότερο αριθμό, αντί για τη διάμεσο. Ο αλγόριθμος είναι ο ίδιος, απλώς επιλέγουμε τυχαία έναν αριθμό και επαναλαμβάνουμε τα βήματα που περιγράφονται.

Συμπίεση

Μια άλλη κατηγορία αλγορίθμων έχει σχεδιαστεί για τη συμπίεση δεδομένων. Αυτός ο αλγόριθμος δεν έχει αναμενόμενο αποτέλεσμα (όπως ένας αλγόριθμος ταξινόμησης), αλλά βελτιστοποιεί σύμφωνα με ορισμένα κριτήρια. Στην περίπτωση της συμπίεσης δεδομένων, ένας αλγόριθμος (για παράδειγμα, LZW) προσπαθεί να κάνει τα δεδομένα να καταλαμβάνουν όσο το δυνατόν λιγότερα byte, αλλά ταυτόχρονα, ώστε να μπορούν να αποσυμπιεστούν στην αρχική τους μορφή. Σε ορισμένες περιπτώσεις, αυτός ο τύπος αλγορίθμων χρησιμοποιεί τις ίδιες μεθόδους με άλλους αλγόριθμους, με αποτέλεσμα ένα καλό αποτέλεσμα, αλλά όχι το βέλτιστο. Για παράδειγμα, τα JPG και MP3 συμπιέζουν δεδομένα με τέτοιο τρόπο ώστε το τελικό αποτέλεσμα να είναι χαμηλότερης ποιότητας από το πρωτότυπο, αλλά και μικρότερο σε μέγεθος. Η συμπίεση MP3 δεν διατηρεί όλα τα χαρακτηριστικά του αρχικού αρχείου ήχου, αλλά προσπαθεί να διατηρήσει αρκετές λεπτομέρειες για να παρέχει αποδεκτή ποιότητα, ενώ μειώνει σημαντικά το μέγεθος του αρχείου. Η μορφή JPG ακολουθεί την ίδια αρχή, αλλά οι λεπτομέρειες είναι σημαντικά διαφορετικές επειδή... ο στόχος είναι η συμπίεση της εικόνας, όχι του ήχου.

Γιατί πρέπει να γνωρίζετε όλα τα είδη αλγορίθμων;

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

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

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

Πραγματικά παραδείγματα

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

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

Αλγόριθμος για την εύρεση της μέγιστης ροής

Το πρόβλημα της εύρεσης της μέγιστης ροής είναι να χρησιμοποιήσετε το υπάρχον δίκτυο για να μετακινήσετε καλύτερα κάτι από το ένα μέρος στο άλλο. Το συγκεκριμένο πρόβλημα προέκυψε για πρώτη φορά τη δεκαετία του 1950 σε σχέση με τις σιδηροδρομικές γραμμές της Σοβιετικής Ένωσης. Οι Ηνωμένες Πολιτείες ήθελαν να μάθουν πόσο γρήγορα θα μπορούσε η Σοβιετική Ένωση να μεταφέρει υλικά στα δορυφορικά κράτη της στην Ανατολική Ευρώπη μέσω του σιδηροδρομικού της δικτύου.

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

Ο πρώτος αποτελεσματικός αλγόριθμος για την εύρεση της μέγιστης ροής εφευρέθηκε από τους επιστήμονες Ford και Fulkerson. Ο αλγόριθμος ονομάστηκε στη συνέχεια αλγόριθμος Ford-Fulkerson και είναι ένας από τους πιο διάσημους αλγόριθμους στον τομέα της επιστήμης των υπολογιστών. Τα τελευταία 50 χρόνια, ο αλγόριθμος έχει υποστεί αρκετές βελτιώσεις, καθιστώντας τον ταχύτερο (αν και ορισμένες από αυτές τις βελτιώσεις είναι τρομακτικές ως προς την πολυπλοκότητά τους).

Δεδομένου ότι η εργασία ήταν σαφώς καθορισμένη, ανακαλύφθηκαν πολλές διαφορετικές εφαρμογές. Ο αλγόριθμος συνδέεται απευθείας με το Διαδίκτυο, όπου είναι σημαντικό να μεταφέρονται όσο το δυνατόν περισσότερα δεδομένα από το ένα σημείο στο άλλο. Το πρόβλημα εμφανίζεται επίσης σε μια ποικιλία επιχειρηματικών διαδικασιών και αποτελεί σημαντικό μέρος της επιχειρησιακής έρευνας. Για παράδειγμα, εάν υπάρχουν N υπάλληλοι και N εργασίες που πρέπει να γίνουν, αλλά δεν μπορεί κάθε υπάλληλος να χειριστεί κάθε εργασία, τότε η εύρεση της μέγιστης ροής θα δώσει μια λύση για την ανάθεση σε N υπαλλήλους σε εργασίες έτσι ώστε κάθε εργασία να ολοκληρωθεί υπό τον όρο ότι Ίσως . Το πρόβλημα Graduation από το TopCoder SRM 200 είναι ένα καλό παράδειγμα ενός προβλήματος μέγιστης ροής.

Σύγκριση αλληλουχίας

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

Για παράδειγμα, λάβετε υπόψη τις ακολουθίες "AABAA" και "AAAB". Για να μετατρέψετε την πρώτη ακολουθία στη δεύτερη, το απλούστερο πράγμα που πρέπει να κάνετε είναι να αφαιρέσετε το Β στη μέση και να αλλάξετε το τελευταίο Α σε Β. Αυτός ο αλγόριθμος έχει πολλές εφαρμογές, συμπεριλαμβανομένων ορισμένων προβλημάτων που σχετίζονται με το DNA και την ανίχνευση λογοκλοπής. Ωστόσο, πολλοί προγραμματιστές το χρησιμοποιούν κυρίως για να συγκρίνουν εκδόσεις του ίδιου αρχείου πηγαίου κώδικα. Εάν τα στοιχεία της ακολουθίας είναι γραμμές σε ένα αρχείο, τότε αυτός ο αλγόριθμος σάς επιτρέπει να μάθετε ποιες γραμμές πρέπει να διαγραφούν, να εισαχθούν, να αλλάξουν προκειμένου να μετατραπεί μια έκδοση του αρχείου σε άλλη.

Χωρίς δυναμικό προγραμματισμό, πρέπει να περάσετε από έναν εκθετικό αριθμό μετασχηματισμών για να μεταβείτε από τη μια ακολουθία στην άλλη. Ωστόσο, ο δυναμικός προγραμματισμός μειώνει τον χρόνο εκτέλεσης του αλγορίθμου σε O(N*M), όπου N και M είναι ο αριθμός των στοιχείων σε δύο ακολουθίες.

συμπέρασμα

Όσο πολλά διαφορετικά προβλήματα υπάρχουν, τόσοι διαφορετικοί αλγόριθμοι για την επίλυσή τους. Ωστόσο, υπάρχει μεγάλη πιθανότητα το πρόβλημα που προσπαθείτε να λύσετε να μοιάζει με κάποιο άλλο πρόβλημα. Αναπτύσσοντας μια βαθιά κατανόηση ενός ευρέος φάσματος αλγορίθμων, θα μπορείτε να επιλέξετε τον σωστό αλγόριθμο και να τον εφαρμόσετε για να λύσετε ένα πρόβλημα. Επιπλέον, η επίλυση προβλημάτων σε διαγωνισμούς στο TopCoder θα σας βοηθήσει να βελτιώσετε τις δεξιότητές σας σε αυτόν τον τομέα. Πολλά από αυτά τα προβλήματα φαίνονται τεχνητά και μη ρεαλιστικά, αλλά απαιτούν το ίδιο σύνολο αλγοριθμικών γνώσεων που απαιτείται καθημερινά στον πραγματικό κόσμο.

Για να γράψετε εφαρμογές διαφορετικών επιπέδων πολυπλοκότητας, πρέπει πρώτα να αποκτήσετε γνώσεις για το πώς να το κάνετε. Και καλό είναι να ξεκινήσετε με τα ίδια τα βασικά του αλγοριθμισμού και του προγραμματισμού. Θα μιλήσουμε γι 'αυτούς στο άρθρο.

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

Τι κάνει αυτή;

Η επιστήμη των υπολογιστών αντιμετωπίζει τις ακόλουθες προκλήσεις:

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

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

Παρουσίαση Αλγορίθμων

Μπορούν να γραφτούν με σημαντικό αριθμό τρόπων. Τα πιο δημοφιλή είναι τα ακόλουθα:

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

Ψευδοκώδικας. Σκίτσο του σκελετού του προγράμματος.

Καταγραφή του αλγορίθμου

Πώς να ξεκινήσετε να δημιουργείτε το δικό σας πρωτότυπο ενός προγράμματος, μιας λειτουργίας ή μιας διαδικασίας; Για να γίνει αυτό, αρκεί να χρησιμοποιήσετε αυτές τις γενικές συστάσεις:

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

Μέθοδοι καταγραφής

Μπορεί να υπάρχουν έως και πέντε αναπαραστάσεις του αλγορίθμου. Αλλά υπάρχουν μόνο δύο τρόποι για να γράψετε:

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

Αναπτύσσουμε μια δομή προγράμματος

Υπάρχουν τρεις κύριοι τύποι:

Γραμμικός. Με αυτή τη δομή, όλες οι ενέργειες εκτελούνται διαδοχικά με τη σειρά και μόνο μία φορά. Το διάγραμμα μοιάζει με μια ακολουθία μπλοκ, τακτοποιημένα από πάνω προς τα κάτω, ανάλογα με τη σειρά με την οποία εκτελούνται. Τα πρωτογενή και ενδιάμεσα δεδομένα που προκύπτουν δεν μπορούν να επηρεάσουν την κατεύθυνση της υπολογιστικής διαδικασίας.
Διακλάδωση. Έχει βρει ευρεία εφαρμογή στην πράξη κατά την επίλυση σύνθετων προβλημάτων. Έτσι, εάν είναι απαραίτητο να ληφθούν υπόψη οι αρχικές συνθήκες ή τα ενδιάμεσα αποτελέσματα, τότε εκτελούνται οι απαραίτητοι υπολογισμοί σύμφωνα με αυτούς και η κατεύθυνση της υπολογιστικής διαδικασίας μπορεί να αλλάξει ανάλογα με το αποτέλεσμα που προκύπτει.

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

Προγραμματισμός

Είναι σημαντικό σε ποια προγράμματα θα δημιουργηθούν. Θα πρέπει να σημειωθεί ότι πολλά από αυτά είναι «προσαρμοσμένα» σε συγκεκριμένες συνθήκες λειτουργίας (για παράδειγμα, σε πρόγραμμα περιήγησης). Γενικά, οι γλώσσες προγραμματισμού χωρίζονται σε δύο ομάδες:

Λειτουργικός.
Αίθουσες χειριστών:

Όχι διαδικαστικά.

Διαδικαστικός.

Μπορείτε να μαντέψετε ποια χρησιμοποιούνται συχνότερα; Διαδικαστικό χειριστή - αυτή είναι η απάντηση. Μπορούν να είναι μηχανοκεντρικά ή ανεξάρτητα. Το πρώτο περιλαμβάνει συναρμολογητές, αυτόματους κωδικούς και συμβολική κωδικοποίηση. Οι ανεξάρτητοι χωρίζουν με βάση τον προσανατολισμό τους:

διαδικαστικός;
προβληματικός;
αντικείμενο.

Κάθε ένα από αυτά έχει το δικό του πεδίο εφαρμογής. Αλλά για τη σύνταξη προγραμμάτων (χρήσιμες εφαρμογές ή παιχνίδια), οι αντικειμενοστρεφείς γλώσσες χρησιμοποιούνται συχνότερα. Φυσικά, μπορείτε να χρησιμοποιήσετε άλλα, αλλά το γεγονός είναι ότι είναι τα πιο ανεπτυγμένα για τη δημιουργία τελικών καταναλωτικών προϊόντων για τις μάζες. Ναι, και αν δεν έχετε ακόμη ένα ακριβές όραμα για το πού να ξεκινήσετε, σας προτείνω να δώσετε προσοχή στα βασικά του αλγοριθμισμού και του αντικειμενοστρεφούς προγραμματισμού. Τώρα αυτή είναι μια πολύ δημοφιλής κατεύθυνση όπου μπορείτε να βρείτε πολύ εκπαιδευτικό υλικό. Σε γενικές γραμμές, τα βασικά στοιχεία του αλγοριθμισμού και των γλωσσών προγραμματισμού χρειάζονται πλέον λόγω του γεγονότος ότι υπάρχει έλλειψη ειδικευμένων προγραμματιστών και η σημασία τους θα αυξηθεί μόνο στο μέλλον.

συμπέρασμα

Όταν εργάζεστε με αλγόριθμους (και στη συνέχεια με προγράμματα), θα πρέπει να προσπαθήσετε να σκεφτείτε όλες τις λεπτομέρειες μέχρι και τις πιο μικρές. Στη συνέχεια, ο εντοπισμός κάθε τμήματος κώδικα που δεν έχει αναπτυχθεί θα οδηγήσει μόνο σε πρόσθετη εργασία, αύξηση του κόστους ανάπτυξης και χρόνου ολοκλήρωσης εργασιών. Ο προσεκτικός σχεδιασμός και η επεξεργασία όλων των αποχρώσεων θα εξοικονομήσει σημαντικά χρόνο, προσπάθεια και χρήματα. Λοιπόν, τώρα μπορούν να πουν ότι αφού διαβάσετε αυτό το άρθρο έχετε κατανοήσει τα βασικά του αλγοριθμισμού και του προγραμματισμού. Το μόνο που μένει είναι να εφαρμόσουμε αυτή τη γνώση. Εάν θέλετε να μελετήσετε το θέμα με περισσότερες λεπτομέρειες, μπορώ να προτείνω το βιβλίο "Βασικές αρχές αλγορίθμου και προγραμματισμού" (Semakin, Shestakov) 2012.

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

Για να δημιουργήσετε προγράμματα που έχουν σχεδιαστεί για την επίλυση ενός προβλήματος σε έναν υπολογιστή, είναι απαραίτητο να συντάξετε έναν αλγόριθμο για την επίλυσή του.

Οι αλγόριθμοι, για παράδειγμα, είναι οι κανόνες πρόσθεσης, πολλαπλασιασμού, επίλυσης αλγεβρικών εξισώσεων, πολλαπλασιασμού πινάκων κ.λπ. Η λέξη αλγόριθμος προέρχεται από το algoritmi, το οποίο είναι μια λατινική μεταγραφή του αραβικού ονόματος του μαθηματικού του 9ου αιώνα Khwarezmian al-Khwarizmi. Χάρη στη λατινική μετάφραση της πραγματείας του al-Khwarizmi, οι Ευρωπαίοι τον 12ο αιώνα εξοικειώθηκαν με το σύστημα αριθμών θέσης και στη μεσαιωνική Ευρώπη ο αλγόριθμος ονομαζόταν δεκαδικό σύστημα αριθμών θέσης και οι κανόνες μέτρησης σε αυτό.

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

Μια εντολή γίνεται αλγόριθμος μόνο όταν ικανοποιεί ορισμένες απαιτήσεις. Μία από τις απαιτήσεις του αλγορίθμου είναι η μονοσημία, δηλ. αν εφαρμοστεί στα ίδια δεδομένα θα δώσει το ίδιο αποτέλεσμα.

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

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

· διακριτικότητα.

· βεβαιότητα.

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

· μαζικός χαρακτήρας.

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

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

Αποδοτικότητασημαίνει τη δυνατότητα απόκτησης αποτελέσματος μετά την εκτέλεση ενός πεπερασμένου αριθμού πράξεων.

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

Για να καθορίσετε έναν αλγόριθμο, είναι απαραίτητο να περιγράψετε τα ακόλουθα στοιχεία του:

· ένα σύνολο αντικειμένων που αποτελούν το σύνολο των πιθανών αρχικών δεδομένων, ενδιάμεσων και τελικών αποτελεσμάτων.

· κανόνας έναρξης.

· τον κανόνα της άμεσης επεξεργασίας των πληροφοριών (περιγραφή της σειράς των ενεργειών).

· Τελικός κανόνας.

· κανόνας εξαγωγής αποτελεσμάτων.

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

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

Έτσι, μπορούμε να δώσουμε τον ακόλουθο ορισμό ενός προγράμματος υπολογιστή:

Οι κύριοι τρόποι περιγραφής αλγορίθμων περιλαμβάνουν τους ακόλουθους:

· λεκτική-τυπική (στη φυσική γλώσσα).

· δομικό ή μπλοκ διάγραμμα.

· Χρήση ειδικών αλγοριθμικών γλωσσών.

· χρησιμοποιώντας διαγράμματα γραφημάτων (γραφική παράσταση είναι μια συλλογή σημείων και γραμμών στις οποίες κάθε γραμμή συνδέει δύο σημεία. Τα σημεία ονομάζονται κορυφές, οι γραμμές ονομάζονται ακμές).

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

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

Ας, για παράδειγμα, πρέπει να βρείτε την τιμή της ακόλουθης έκφρασης:

y = 4a – (x + 3).

Με προφορικό και τυπικό τρόπο, ο αλγόριθμος για την επίλυση αυτού του προβλήματος μπορεί να γραφτεί με την ακόλουθη μορφή:

1. Εισαγάγετε τις τιμές των a και x.

2. Προσθέστε x και 3.

3. Πολλαπλασιάστε το a με το 4.

4. Αφαιρέστε το άθροισμα (x+3) από το 4α.

5. Έξοδος y ως αποτέλεσμα της αξιολόγησης της παράστασης.

Στο ΟΙΚΟΔΟΜΙΚΟ ΤΕΤΡΑΓΩΝΟ-σχηματική περιγραφήο αλγόριθμος απεικονίζεται με γεωμετρικά σχήματα (μπλοκ) που συνδέονται με γραμμές ελέγχου (κατευθύνσεις ροής) με βέλη. Τα μπλοκ καταγράφουν μια ακολουθία ενεργειών.

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

Ο σχεδιασμός των προγραμμάτων πρέπει να πληροί ορισμένες απαιτήσεις (Εικ. 2.). Επί του παρόντος, υπάρχει ένα ενιαίο σύστημα τεκμηρίωσης προγράμματος (USPD), το οποίο καθορίζει τους κανόνες για την ανάπτυξη, την εκτέλεση προγραμμάτων και την τεκμηρίωση του προγράμματος. Το ESPD ορίζει επίσης τους κανόνες για το σχεδιασμό διαγραμμάτων ροής αλγορίθμων (GOST 10.002-80 ESPD, GOST 10.003-80 ESPD).

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

Οποιαδήποτε υπολογιστική διαδικασία μπορεί να αναπαρασταθεί ως συνδυασμός στοιχειωδών αλγοριθμικών δομών:

· ΕΠΟΜΕΝΟ. Προϋποθέτει τη διαδοχική εκτέλεση εντολών από πάνω προς τα κάτω. Εάν ένας αλγόριθμος αποτελείται μόνο από δομές ακολουθίας, τότε είναι γραμμικός.

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

· Κύκλος. Προϋποθέτει τη δυνατότητα επαναλαμβανόμενης επανάληψης ορισμένων ενεργειών. Ο αριθμός των επαναλήψεων εξαρτάται από την κατάσταση του κύκλου.

· Λειτουργία (υπορουτίνα). Οι εντολές που χωρίζονται από το κύριο πρόγραμμα εκτελούνται μόνο εάν καλούνται από το κύριο πρόγραμμα (από οπουδήποτε σε αυτό). Η ίδια λειτουργία μπορεί να κληθεί από το κύριο πρόγραμμα όσες φορές θέλετε.

Υπάρχουν τρεις κύριοι τύποι αλγορίθμων:

Τα σύγχρονα συστήματα προγραμματισμού συνήθως παρέχουν στους χρήστες ισχυρά και βολικά εργαλεία ανάπτυξης προγραμμάτων. Αυτά περιλαμβάνουν:

· Μεταγλωττιστής ή διερμηνέας.

· ολοκληρωμένο περιβάλλον ανάπτυξης;

· εργαλεία για τη δημιουργία και την επεξεργασία κειμένων προγράμματος.

· Εκτεταμένες βιβλιοθήκες τυπικών προγραμμάτων και λειτουργιών.

· προγράμματα εντοπισμού σφαλμάτων, π.χ. προγράμματα που βοηθούν στην εύρεση και διόρθωση σφαλμάτων στο πρόγραμμα.

· Φιλικό προς τον χρήστη περιβάλλον διαλόγου.

· Τρόπος λειτουργίας πολλαπλών παραθύρων.

· ισχυρές βιβλιοθήκες γραφικών. βοηθητικά προγράμματα για εργασία με βιβλιοθήκες.

· ενσωματωμένος συναρμολογητής.

· ενσωματωμένο γραφείο βοήθειας.

· άλλα ειδικά χαρακτηριστικά.

Το πρώτο βήμα για την κατανόηση της σημασίας της μελέτης και της γνώσης αλγορίθμων είναι να ορίσουμε με ακρίβεια τι σημαίνει ένας αλγόριθμος. Σύμφωνα με το δημοφιλές βιβλίο Algorithms: Construction and Analysis (Cormen, Leiserson, Rivest, Stein) «αλγόριθμος είναι κάθε καλά καθορισμένη υπολογιστική διαδικασία της οποίας η είσοδος δίδεται μια συγκεκριμένη ποσότητα ή σύνολο ποσοτήτων και το αποτέλεσμα της οποίας είναι μια έξοδος ( έξοδος) τιμή ή σύνολο τιμών." Με άλλα λόγια, οι αλγόριθμοι είναι σαν χάρτες πορείας για την επίτευξη ενός σαφώς καθορισμένου στόχου. Ένα κομμάτι κώδικα για τον υπολογισμό των μελών της ακολουθίας Fibonacci είναι μια υλοποίηση ενός συγκεκριμένου αλγορίθμου. Ακόμη και μια απλή συνάρτηση της πρόσθεσης δύο αριθμών είναι αλγόριθμος, αν και απλός.