Η φιλοσοφία του προγραμματισμού

Λογική σκέψη === καλό λογισμικό

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

  • Πώς καταλήγουμε με αλγοριθμικές λύσεις σε ένα πρόβλημα;
  • Τότε, πώς ξέρουμε ότι η λύση λειτουργεί πραγματικά;
  • Ακόμα κι αν είμαστε σίγουροι ότι λειτουργεί, πώς λέμε στον υπολογιστή να τον εκτελέσει;

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

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

Η πρώτη αρχή: πρέπει να σκεφτείτε σκληρά.

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

Αλλά δεν μπορούν να λύσουν ένα πραγματικό πρόβλημα όπως "πώς μπορώ να φτάσω στο γραφείο μου από το σπίτι;"

Μια αποτελεσματική μέθοδος μπορεί (κατ 'αρχήν) να πραγματοποιηθεί από έναν άνθρωπο χωρίς βοήθεια από οποιοδήποτε μηχάνημα εκτός από χαρτί και μολύβι. - The Church-Turing Thesis

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

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

Ροή συλλογισμού ενός προγραμματιστή

Τώρα κοιτάζουμε κάποια περιγραφή του προβλήματος. Μπορούμε πρώτα να αναζητήσουμε παραδείγματα εισόδου-εξόδου μικρής κλίμακας για να κατανοήσουμε το πρόβλημα:

Επαγωγή. Χρειαζόμαστε έναν αλγόριθμο που μπορεί να χειριστεί τέτοια παραδείγματα. Τώρα κάνετε επαγωγή: γενίκευση των αρχών από την εμπειρία.

Αφαίρεση. Πώς ξέρουμε αν λειτουργεί για άλλες άγνωστες εισόδους; Κάνουμε αφαίρεση για να αποδείξουμε την ορθότητα του αλγορίθμου μας.

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

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

Ενα παράδειγμα

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

Για προβλήματα μικρής κλίμακας, μπορούμε να τα λύσουμε με ένστικτα. Όπως, είναι πολύ απλό για εμάς να αναγνωρίσουμε τη λύση ACE απλά κοιτάζοντας.

Τι γίνεται όμως με πιο περίπλοκες τοπολογίες; Τι γίνεται με διαφορετικά βάρη άκρων;

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

Η διαδικασία

1. Γενικεύστε τις αρχές από την εμπειρία: αλγόριθμοι

Για να πούμε σε έναν υπολογιστή τι να κάνουμε, πρέπει πρώτα να βρούμε μια αλγοριθμική διαδικασία.

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

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

Ορίστε λοιπόν η αλγοριθμική διαδικασία:

  1. Μερικές ρυθμίσεις: (1) φυλάξτε τις κορυφές που έχουμε επισκεφτεί: ένα σετ ( visited), (2) θυμάται τις γνωστές μικρότερες αποστάσεις από κάθε κορυφή που χρησιμοποιούν μόνο ανακαλυφθείσες κορυφές : ένα άλλο σετ distance(u). Η απόσταση κάθε κορυφής είναι αρχικά άπειρο, εκτός από την κορυφή κορυφής είναι 0.
  2. Τώρα αρχίζουμε να εξερευνούμε: πρώτα επισκεφτούμε την κορυφή που έχει τη γνωστή συντομότερη διαδρομή μέχρι τώρα, ας πούμε ότι είναι u. (Αρχικά θα ήταν η κορυφή της πηγής).
  3. Όταν στέκεται στην κορυφή u, κοιτάζουμε γύρω από τις εξερχόμενες άκρες. Κάθε άκρη, ας πούμε (u,v), μας δίνει μια διαδρομή προς την κορυφή vπου χρησιμοποιεί την κορυφή uως το τελευταίο αλλά μόνο ένα βήμα. Εάν κάποιο από αυτά είναι πράγματι μια πιο σύντομη διαδρομή vή η πρώτη διαδρομή που βρήκαμε v, σήμερα μπορούμε να ενημερώσουμε το σύνολο των πιο σύντομων διαδρομών μας τώρα. Διαφορετικά αγνοήστε και συνεχίστε.
  4. Έχουμε τελειώσει με την κορυφή u, έτσι το προσθέτουμε στο visitedσετ μας .
  5. Επιστρέψτε στο βήμα 2, συνεχίστε την εξερεύνηση έως ότου επισκεφτήκαμε όλες τις κορυφές.

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

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

2. Επικυρώστε τις γενικές αρχές με έκπτωση

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

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

Εδώ είναι η βασική ροή της απόδειξης:

1. Για όλες τις κορυφές που έχετε επισκεφθεί, βρίσκουμε τις πιο σύντομες διαδρομές.

2. Ο προορισμός επισκέπτεται.

3. Επομένως, βρίσκουμε τη συντομότερη διαδρομή προς τον προορισμό.

Δεν φαίνονται κάπως οικεία; Σαν αυτό:

1. Όλοι οι άντρες είναι θνητοί.

2. Ο Σωκράτης είναι άντρας.

3. Επομένως, ο Σωκράτης είναι θνητός.

Στην πραγματικότητα, αυτός είναι ο Συλογισμός, μια κλασική μορφή συλλογικής συλλογιστικής. Αυτό κάνουν σχεδόν όλοι οι λογικοί.

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

Αργότερα το 1936, η Εκκλησία Alonzo και ο Alan Turing ανέπτυξαν τον επίσημο ορισμό της Υπολογιστικότητας, ανεξάρτητα, την ίδια στιγμή. Αυτό το άρθρο δίνει μια ιστορική ανασκόπηση του υπολογισμού.

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

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

Η γενική ροή έχει ως εξής. Πρώτον, εάν ένας αλγόριθμος λειτουργεί στην είσοδο 0και δεύτερος, εάν το γεγονός ότι λειτουργεί στην είσοδο nσυνεπάγεται ότι λειτουργεί και στην είσοδο n+1 , τότε λειτουργεί για όλες τις εισόδους μεγαλύτερες ή ίσες με 0. Σε αυτό το σημείο μπορείτε να εγγυηθείτε την ορθότητα του αλγορίθμου σας.

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

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

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

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

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

3. Το πρόβλημα οντολογίας: δομή δεδομένων

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

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

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

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

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

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

Μια οπτική αναπαράσταση βρίσκεται στην παραπάνω εικόνα. Αυτή η αναπαράσταση είναι αποδοτική στη μνήμη. Είναι επίσης πιο αποτελεσματικό για την επεξεργασία του προγράμματος.

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

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

4. Μια εκ των υστέρων πρόταση: εντοπισμός σφαλμάτων

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

Για παράδειγμα, τα σφάλματα τμηματοποίησης σε προγράμματα C προκαλούνται συχνά από αναφορές μηδενικού δείκτη. Το έμαθα αφού ασχολήθηκα με τόνους σφαλμάτων τμηματοποίησης C / C ++. Φυσικά, υπάρχουν πιο λεπτές περιπτώσεις που σχετίζονται με προσωπικές συνήθειες προγραμματισμού.

Το ακόλουθο παράδειγμα είναι ένα συντακτικό λάθος που έκανε ένας προγραμματιστής. Η συνθήκη if θα έπρεπε να ήταν is_float==1, αλλά ο προγραμματιστής έκανε λάθος τον λογικό ίσο τελεστή ==ως χειριστή αξιολόγησης =. Αυτό θα περάσει ακόμα τον έλεγχο του μεταγλωττιστή, επειδή και οι δύο είναι σωστή σύνταξη.

if (is_float = 1) { // do something}

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

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

Θα πρέπει να παρακολουθείτε τα επαναλαμβανόμενα μοτίβα στους κωδικούς σας με λάθη. Όταν εντοπίσετε ένα σφάλμα, η διόρθωσή του δεν είναι αρκετή. Χρειάζεστε κάποια επιπλέον ανάλυση αιτίου-αποτελέσματος στη δική σας πρακτική προγραμματισμού. Αναρωτηθείτε: αυτό το μέρος των συνηθειών προγραμματισμού μου είναι ιδιαίτερα ευάλωτο σε τέτοιου είδους σφάλματα;

Γιατί λοιπόν έχει σημασία;

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

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

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

βιβλιογραφικές αναφορές

  • Υπολογισμός, Φιλοσοφικά θέματα για. Matthias Scheutz.
  • Η διατριβή της εκκλησίας-Turing.
  • Σκεφτείτε σαν προγραμματιστής: Μια εισαγωγή στη δημιουργική επίλυση προβλημάτων. V. Anton Spraul.