Programmeringsfilosofien

Logisk tænkning === god software

Programmering er den nye læsefærdighed. Men hvordan skriver vi gode programmer? Her er de tilbagevendende spørgsmål, vi skal løse:

  • Hvordan finder vi algoritmiske løsninger på et problem?
  • Hvordan ved vi så, at løsningen faktisk fungerer?
  • Selvom vi er sikre på, at det fungerer, hvordan fortæller vi computeren at udføre det?

Sjov kendsgerning - hvis du har svært ved at slibe nogle af disse spørgsmål, laver du faktisk filosofi.

For at se hvorfor, lad os undersøge nogle interessante ligheder mellem programmering og filosofisk ræsonnement.

Det første princip: du skal tænke hårdt.

Computere gør intet smartere end vi kan - forskellen er, de gør det med hurtigere hastighed.

Men de kan ikke løse et reelt problem som "hvordan kommer jeg til mit kontor hjemmefra?"

En effektiv metode kan (i princippet) udføres af et menneske uden hjælp fra ethvert maskineri undtagen papir og blyant. - The Church-Turing Thesis

Fordelen ved programmering ligger stadig i ræsonnementet. Det vil sige at oversætte et virkeligt verdensproblem til enkle instruktioner, som en computer kan udføre.

Naturligvis har forskellige programmeringssprog forskellige niveauer af semantiske abstraktioner. Et Python-program kan være kortere end dets C-modstykke. Men det ændrer bare mængden af ​​oversættelser. Vi kan ikke slippe af med oversættelsesarbejdet. Men vi forlader denne diskussion til senere.

En programmørs argumentationsflow

Nu stirrer vi på en eller anden problembeskrivelse. Vi kan først kigge efter eksempler på små input-output for at forstå problemet:

Induktion. Vi har brug for en algoritme, der kan håndtere sådanne eksempler. Nu laver du induktion: generalisering af principper fra erfaring.

Fradrag. Hvordan ved vi, om det fungerer for andre ukendte input? Vi trækker for at bevise rigtigheden af ​​vores algoritme.

Ontologi . Vi skal vedligeholde data i computerens hukommelse. Målet er at gøre dem effektive, så computere kan behandle dem. For ordord, hvilken datastruktur kan bedst opfange den dynamiske strøm af mine oplysninger?

Induktion igen . Derefter kommer den sidste slutfase: debugging. Vi får den buggy del af programmet til at analysere de uventede output.

Et eksempel

Lad os nu undersøge ovenstående proces ved at følge dette virkelige eksempel: at finde den korteste vej fra toppunkt A til toppunkt E.

For småskala problemer kan vi løse dem ved instinkter. Som det er meget ligetil for os at genkende løsningen ACE bare ved at se.

Men hvad med mere komplekse topologier? Hvad med forskellige kantvægte?

Vi har brug for hjælp fra computere. Alligevel er det ikke ligetil at fortælle en computer, hvad man skal gøre. Der er et hul mellem hvordan mennesker tænker og hvordan en computer fungerer.

Processen

1. Generaliser principper fra erfaring: algoritmer

For at fortælle en computer, hvad de skal gøre, skal vi først komme med en algoritmisk procedure.

Grådige strategier er en naturlig måde at gå videre på. Det vil sige at starte fra kildepunktet A og gå hele vejen langs den kendte korteste vej. Bliv ved med at udforske nye hjørner, indtil vi når destination E. Og faktisk opfylder denne tilgang vores eksempel.

Intuitionen er, at langs den korteste sti til en destination besøges også hver mellemliggende node i den korteste sti. (Selvfølgelig antager denne intuition, at alle kanter har positive vægte. Dette er muligvis ikke tilfældet, afhængigt af applikationerne. Vi vil diskutere dette detaljeret senere).

Så her er den algoritmiske procedure:

  1. Noget setup: (1) bogholder de hjørner, vi har besøgt: et sæt ( visited), (2) husk de kendte korteste afstande til hvert toppunkt, der kun bruger opdagede hjørner : et andet sæt distance(u). Hver verteks afstand er oprindeligt uendelig, bortset fra kildepunktet er 0.
  2. Nu begynder vi at udforske: først besøger vi toppunktet, der hidtil har den kendte korteste vej, siger det er u. (Oprindeligt ville det være kildepunktet).
  3. Når vi står ved hjørnet u, kigger vi omkring de udgående kanter. Hver kant, siger (u,v), giver os en sti til toppunkt, vder bruger toppunkt usom det sidste, men kun et trin. Hvis nogen af ​​dem virkelig er en kortere sti til veller den første sti, vi fandt til v, hurra, kan vi opdatere vores sæt korteste stier nu. Ellers ignorere og fortsæt.
  4. Vi er færdige med toppunkt u, så vi tilføjer det i vores visitedsæt.
  5. Gå tilbage til trin 2, fortsæt med at udforske, indtil vi har besøgt alle hjørner.

distancekan nu fortælle os de globale korteste afstande, fordi det bruges til at holde de korteste afstande ved kun at bruge besøgte noder. Og alle hjørner besøges, når algoritmen er færdig.

Vi genopfandt lige Dijkstras algoritme. Der er selvfølgelig mange andre algoritmer til at finde den korteste vej. Men pointen er, at vi har brug for en algoritmisk procedure for at løse problemet.

2. Valider generelle principper ved fradrag

Hvordan sørger vi for, at algoritmens principper er korrekte? Vi kan enten øge vores tillid ved at teste princippet mod flere inputeksempler, eller mere effektivt kan vi finde et strengt matematisk bevis.

Ligesom et a priori-forslag i filosofi er korrektheden af ​​en algoritme uafhængig af dens udførelse. Med andre ord kan test ikke garantere rigtigheden af ​​algoritmer. Vi skal bevise det.

Her er den grundlæggende strøm af beviset:

1. For alle besøgte hjørner finder vi de korteste stier.

2. Destinationen besøges.

3. Derfor finder vi den korteste vej til destinationen.

Virker de ikke noget velkendte? Sådan her:

1. Alle mænd er dødelige.

2. Socrate er en mand.

3. Derfor er Socrate dødelig.

Faktisk er dette Syllogism, en klassisk form for deduktiv ræsonnement. Dette er stort set hvad logikere laver.

En anden interessant historisk kendsgerning: det formelle koncept for beregning kom først op af logikere i 1930'erne. De havde brug for at vide, om visse logiske problemer overhovedet faktisk kan løses (så de kunne undgå at spilde deres tid på at løse noget uløseligt). For at svare på det kommer de med begrebet beregningsevne.

Senere i 1936 udviklede Alonzo Church og Alan Turing den formelle definition af Computability, uafhængigt, på samme tid. Dette papir giver en historisk gennemgang af beregningen.

Konklusionens rigtighed afhænger af de to første forudsætninger. I vores bevis er den anden forudsætning triviel, da vores algoritme bogstaveligt talt besøger alle noder. Alligevel kræver det noget arbejde at bevise den første forudsætning, at vi finder den korteste vej, når vi besøger en knude.

Matematisk induktion kan hjælpe. Det er faktisk en af ​​de mest nyttige teknikker til at bevise rigtigheden af ​​mange andre algoritmer.

Den generelle strømning går som følger. For det første, hvis en algoritme fungerer på input 0, og for det andet, hvis det faktum, at den fungerer på input, nindebærer, at den også fungerer på input n+1 , så fungerer den for alle input, der er større eller lig med 0. På dette tidspunkt er du i stand til at garantere rigtigheden af ​​din algoritme.

For enkelheds skyld henviser jeg dig til denne forelæsningsnotat for det komplette bevis på denne algoritme til at finde vej.

Bemærk, at vi ikke bør forveksle matematisk induktion og filosofisk induktion. Ved den filosofiske definition er matematisk induktion en deduktiv ræsonnementsproces, fordi dens korrekthed er indeholdt i sig selv uden eksterne observationer.

Lektionen er: når vi kommer med en algoritme, skal den være i stand til at håndtere alle mulige eksekveringssager.

I praksis er det måske ikke den mest effektive strategi at gennemgå det strenge matematiske bevis. Men i det mindste vil vi overveje så mange eksekveringssager som muligt, især de kontradiktoriske. Denne praksis vil forbedre robustheden i vores kode.

Du har muligvis bemærket, at det i vores eksempel på stedsøgningsalgoritme ikke virker, hvis kantvægten er negativ. Årsagen kan findes i denne forelæsningsnotat. For at håndtere en graf med negativ vægt kan du bruge Bellman-Ford-algoritmen.

3. Ontologiproblemet: datastruktur

Indtil videre overbeviste vi os selv om, at vi har en korrekt algoritme. Men dette er kun halvdelen af ​​kampen.

Det næste spørgsmål er, hvordan indfører vi oplysningerne til computere? Mennesker kan lide visualiseret information, som grafer eller histogrammer. Men nutidens computere behandler kun binære bits.

Vi er nødt til at komme med en datastruktur, der indeholder de væsentlige oplysninger. Og det skal være effektivt for et program at behandle på samme tid.

Lad os fortsætte på vores vej til at finde et eksempel. En sti er en ordnet liste. Men det er irriterende at håndtere, sammenlignet med et heltal. Bemærk, at vi i vores algoritme skal finde den korteste vej fra vores sæt opdagede stier. Og derefter gentage hele vejen til slutningen. Det ser ud til, at vi er nødt til at dedikere en matrix eller hukommelse til at gemme hver sti.

Kunne vi gøre det bedre? Bemærk, at i en gyldig sti skal på hinanden følgende udseende af elementer svare til en kant i grafen. Men vi har allerede kantinformationen, og de er de samme for alle stier. Hvorfor kan vi ikke slippe af med disse overflødige oplysninger?

Nå kan vi slippe af med listen. Det viser sig, at for at samle den korteste vej er det mellemliggende trin at bestemme, hvad der er det næste hop, du har brug for. Alt, hvad vi har brug for for at hente den korteste sti fra kilde A til ethvert målknudepunkt, er kun selve grafen og den korteste afstand fra A til hver knude.

En visuel repræsentation er i ovenstående billede. Denne repræsentation er hukommelseseffektiv. Det er også mere effektivt for programmet at behandle.

Dette konstruerer den korteste sti ved kun at bruge afstandsvektoren. Start fra destinationspunktet og en tom sti. Slå mellemliggende hjørner op gennem indgående kanter. Vælg den med den laveste værdi i distance. Føj det til stiens hoved. Gentag indtil vi når kilden. Dette trick har faktisk en formel notation kaldet back-tracking.

Filosoffer søger den evige sandhed. Og programmører ønsker at finde ud af den nøjagtige datastruktur, der bedst fanger informationsdynamikken. Som du ser i eksemplet med sti, er alt, hvad der er brug for for at give en korteste sti, kun en vektor, der fortæller dig de korteste afstande til hvert toppunkt. Dette gælder for enhver graf, uanset antallet af hjørner eller kanter.

4. A posteriori proposition: debugging

De fleste programmører har gennemgået denne ræsonnement mange gange. Jeg vedder på, at dette er en af ​​de mest vanskelige og tidskrævende dele af enhver programmeringsopgave.

For eksempel er segmenteringsfejl i C-programmer ofte forårsaget af nulmarkeringsreferencer. Jeg lærte dette efter at have håndteret tonsvis af C / C ++ segmenteringsfejl. Selvfølgelig er der mere subtile tilfælde, der vedrører personlige programmeringsvaner.

Følgende eksempel er en syntaksfejl foretaget af en programmør. Hvis-betingelsen skulle have været is_float==1, men programmøren tog fejl af den logiske lige operator ==som en evalueringsoperator =. Dette vil stadig passere kompilatorens kontrol, fordi den ene er korrekt syntaks.

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

Dette er en induktiv ræsonnementsproces. Din fejlfindingsdiagnose giver kun mening, hvis du har observeret nok programudførelser.

Her er hvor værdien af ​​praksis kommer ind. Uanset hvilken slags teknikker du lærer, skal du samle nok praktiske data. Ellers ville du ikke have nok erfaring til at gennemføre induktion.

Du bør holde øje med de tilbagevendende mønstre i dine buggykoder. Når du finder en fejl, er det ikke nok at rette det. Du har brug for nogle ekstra årsagseffektanalyser på din egen programmeringspraksis. Spørg dig selv: er denne del af mine programmeringsvaner særlig sårbare over for denne slags fejl?

Så hvorfor betyder det noget?

Programmering handler ikke kun om at skrive kode, det er en systematisk måde at resonnere på. Fordi kode eller instruktioner bare er et middel til et mål. Med udviklingen af ​​programsyntese-teknikken gider du måske ikke engang at skrive kode og debugge dig selv. Alt, hvad der betyder noget, er, hvis du kan fortælle computeren, hvad den skal gøre.

Som det første skridt i retning af at forbedre dine programmeringsfærdigheder afslører denne artikel det underliggende ræsonnementsmønster, som vi måske ikke engang genkender, da vi programmerede. De fleste af os stoler på ubevidst, automatisk refleksion for at afslutte de fleste af vores daglige opgaver. Men hvor kommer forbedring fra? Det kommer først fra at bemærke nogle fejl eller fejl, vi har lavet i vores ræsonnementsproces.

For praktisk rådgivning anbefaler jeg denne artikel om, hvordan man tænker som en programmør, og denne bog om det samme emne, men med flere detaljer.

Referencer

  • Beregning, filosofiske spørgsmål om. Matthias Scheutz.
  • The Church-Turing-afhandlingen.
  • Tænk som en programmør: En introduktion til kreativ problemløsning. V. Anton Spraul.