Hvordan / hvornår bruges calculus i datalogi?

Dette er noget uklart, men beregning vises i algebraiske datatyper. For en hvilken som helst given type er typen af dens et-hulssammenhæng afledt af den type. Se denne fremragende tale for en oversigt over hele emnet. Dette er meget teknisk terminologi, så lad os forklare.

Algebraiske datatyper

Du er muligvis stødt på tupler, der kaldes produkttyper (hvis ikke, det er fordi de er det kartesiske produkt af to typer). Vi vil tage dette bogstaveligt og bruge notationen:

$$ a * b $$

At repræsentere en tuple, hvor $ a $ og $ b $ er begge typer. Dernæst er du muligvis stødt på sumtyper disse er typer, som enten kan være en type eller en anden (kendt som fagforeninger , varianter eller som Enten type (kinda) i Haskell). Vi vil også tage denne bogstaveligt og bruge notationen:

$$ a + b $$

Disse navngives som de er, fordi hvis en type $ a $ har $ N_a $ -værdier og en type $ b $ har $ N_b $ -værdier, derefter typen $ a + b $ har $ N_a + N_b $ værdier.

Disse typer ligner normale algebraiske udtryk og Vi kan faktisk manipulere dem som sådan (til et punkt).

Et eksempel

På funktionelle sprog er en fælles definition af en liste (givet i Haskell her) denne:

data List a = Empty | Cons a List 

Dette siger, at en liste er enten tom eller en tuple af en værdi og en anden liste. Omdannelse til algebraisk notation får vi:

$$ L (a) = 1 + a * L (a) $$

Hvor $ 1 $ repræsenterer en type med en værdi (også kaldet enhedstypen). Ved gentagne gange at indsætte kan vi evaluere dette for at få en definition af $ L (a) $ :

$$ L (a) = 1 + a * L (a) $$ $$ L (a) = 1 + a * (1 + a * L ( a)) $$ $$ L (a) = 1 + a + a ^ 2 * (1 + a * L (a)) $$ $$ L (a) = 1 + a + a ^ 2 + a ^ 3 * (1 + a * L (a)) $$ $$ L (a) = 1 + a + a ^ 2 + a ^ 3 + a ^ 4 + a ^ 5 … $$

(Hvor $ x ^ n $ menes i betydningen gentagen multiplikation.)

Denne definition siger så, at en liste er enten enhed eller en tuple af et element eller en tuple på to ting eller tre osv., som er definitionen på en liste!

Kontekster med et hul

Nu på til et-hullers sammenhænge: en et-huls kontekst er hvad du får, når du “tager en værdi ud” af en produkttype. Lad os give et eksempel:

For en simpel 2-tuple, der er homogen, $ a ^ 2 $ , hvis vi tager en værdi ud , vi får bare en 1-tuple, $ a $ .Men der er to forskellige kontekster med et hul af denne type: nemlig den første og anden værdi af tuplen. Så da det er en af disse, kunne vi skrive, at det er $ a + a $ , hvilket naturligvis er $ 2 en $ . Det er her, differentieringen kommer ind for at spille. Lad os bekræfte dette med et andet eksempel:

At tage en værdi ud af en 3-tuple giver en 2-tuple, men der er tre forskellige varianter:

$$ (a, a, \ _) $$ $$ (a, \ _, a) $$ $$ (\ _, a, a) $$

Afhængigt af hvor vi placerer hullet. Dette giver os $ 3a ^ 2 $ som faktisk er afledt af $ a ^ 3 $ . Der er et bevis på dette generelt her .

For vores sidste eksempel, lad os bruge en liste:

Hvis vi tager vores oprindelige udtryk til en liste:

$$ L (a) = 1 + a * L (a) $$

Vi kan omarrangere for at få:

$$ L (a) = \ frac {1} {1 – a} $$

(På overfladen dette kan virke som vrøvl, men hvis du tager taylor-serien af dette resultat, får du den definition, vi afledte tidligere.)

Nu hvis vi differentierer dette, g et interessant resultat:

$$ \ frac {\ partial L (a)} {\ partial a} = (L (a)) ^ 2 $$

Således er en liste blevet et par lister. Dette giver faktisk mening: De to producerede lister svarer til elementerne over og under hullet i den oprindelige liste!

Kommentarer

• Dette var vidunderligt indsigtsfuld. Tak.

Numeriske metoder. Der findes besværlige beregningsproblemer, der er unikke for specifikke applikationer, og de har brug for løsninger hurtigere, end et menneske praktisk talt kan løse uden et program. Nogen skal designe en algoritme, der beregner løsningen. Er det ikke det eneste, der adskiller programmører fra forskere?

Kommentarer

• Givet " liste " dette spørgsmåls beskaffenhed, hvert svar skal forsøge at give det fulde billede. Er du sikker på, at du vil hævde, at numeriske metoder er den eneste forekomst?
• Kommentarer er ikke til udvidet diskussion; denne samtale er flyttet til chat .

Automatisering – Svarende til robotik, automatisering kan kræve kvantificering af meget menneskelig adfærd.

Beregninger – At finde løsninger på bevis kræver ofte beregning.

Visualiseringer – Brug af avancerede algoritmer kræver beregning som cos, sinus, pi og e. Især når du beregner ting-vektorer, kollisionsfelter og indgreb.

Logistik og risikoanalyse – Bestemmelse af, om en opgave er mulig, den involverede risiko og mulig succesrate.

Sikkerhed – Mest sikkerhed kan udføres uden beregning men mange mennesker, der ønsker forklaringer, foretrækker det i matematiske udtryk.

AI – Grundlæggende om AI kan bruges uden beregning; dog beregning af avanceret adfærd, sværmeintelligens / bikubesind og komplekse værdibaserede beslutningsprocesser.

Medicinske beregninger – Visualisering af de fleste sundhedsdata kræver beregning såsom EKG-læsning.

Science & Engineering – Når man arbejder med næsten enhver anden videnskabelig disciplin kræver beregning: Rumfart, astrologi, biologi, kemi eller teknik.

Mange mennesker i programmering kan gå hele deres karriere uden ved hjælp af calculus; Det kan dog være uvurderligt, hvis du er villig til at udføre arbejdet. For mig har det været mest effektivt inden for automatisering, logistik og visualisering. Ved at identificere specifikke mønstre kan du simpelthen ignorere mønsteret, efterligne mønsteret eller udvikle et overlegen metode alt sammen.

Kommentarer

• Hvordan er cos, sinus, $ \ pi $ og $ \ mathrm {e} $ calculus?
• Nå, $ \ exp (x) $ kan defineres som den unikke løsning til $ f (x) = f ' (x) $ med $ f ( 0) = 1 $ og ligeledes sin, cos kan defineres som det unikke par funktioner, der tilfredsstiller $ f ' (x) = g (x) $, $ g ' (x) = -f (x) $ med passende randbetingelser (jeg synes $ f (0) = 0 $ og $ g (0) = 1 $ skal fungere).
• @DavidRicherby: Eksempel: hvordan implementerer du disse funktioner på f.eks. en mikrocontroller uden en FPU? Hvis du kender noget beregning, ved du straks et godt svar: power series.

Faktum er at der er meget lille chance for, at du nogensinde bruger calculus. Imidlertid bruger næsten enhver anden videnskabelig disciplin beregning, og du arbejder på en videnskabelig grad. Der er visse forventninger til, hvad en universitetsvidenskabelig grad skal betyde, og en af disse ting er, at du kender beregning. Selvom du aldrig bruger det.

Det er okay, hvis du klarer dig dårligt i beregning, men sørg for at lægge en del indsats i diskret matematik. Der er mange programmeringsproblemer i den virkelige verden, hvor diskret matematik kommer i spil, og uvidenhed om dens principper kan give dig pinlighed foran andre kodere.

Kommentarer

• Dit første afsnit er helt forkert og grænser op til sammensværgelsesteori. Der er masser af områder inden for datalogi, hvor beregning er nyttig (se de andre svar for endeløse lister over dem). Sikker på, det er ' muligt at undgå alle disse områder, men det ' er meget vildledende at hævde, at tab af beregning har nul effekt ud over karakterer.
• Afhængigt af dit uddannelse kunne du gennemføre en grad uden nogensinde at bruge beregning, og jeg tror bestemt, at CS-majors ikke har brug for så meget af det som vi får. Men at gøre dårligt i det vil låse dig ud af nogle af de mest interessante områder inden for datalogi. Der ' har masser af tid til at være webudvikler, når du er færdiguddannet; mens du er i skole, hvorfor ikke prøve at skubbe dig selv lidt?
• @tsleyson Hvis du vil være en webudvikler, skal du spare tid og penge på at få en CS-grad.
• @ScottB Du ser ud til at forveksle datalogi med programmering.
• @ScottB Hvem ' siger CS = matematik + programmering? Selv har jeg i mange aldre fortaler for denne begrænsede opfattelse. Men du har det også baglæns: matematik er integreret i CS, ligesom det er i fysik. Vi har brug for det, selvom vi ikke ' ikke ønsker at øve det. (Når det er sagt, er dette ikke stedet for denne diskussion. Vær venlig at deltage i Computer Science Chat , hvis du vil fortsætte.)

Mange mennesker leverede allerede applikationer i CS. Men nogle gange finder du Calculus, når du mindst forventer:

Derivater med regulært udtryk undersøges igen

Hvis du ved automatisk denne pdf kan være værd at læse.

Kommentarer

• Jeg kan ikke ' ikke se nogen differentiel beregning der; Jeg ser ordet " afledt ", men jeg kan ikke ' ikke se noget ligner traditionel differentieret beregning.
• Det ' kaldes " formelt derivat ", og det er på en måde relateret til Calculus. Du vil også se dette gjort med Generering af funktioner, nogle formler relateret til diskrete strukturer og andre områder, hvor du ikke ' t har faktisk en " glat funktion ".
• @Jay: Det vigtige er ikke ' t navnet. Hvordan forstås det ng beregning hjælpe med det?
• Det forklares på denne Wikipedia-side . Det formelle afledte er en operation på elementer af analgebraisk struktur, der indeholder polynomer, og det er formelt " ligesom " den sædvanlige regel til differentiering polynomer, dog – forskelligt fra hvad en studerende ser i beregning – er polynomierne ikke over virkelige; de kan være polynomer over en vilkårlig " ring " (en anden algebraisk struktur). Og der er praktiske anvendelser af det formelle derivat – jeg har set mindst en (algebraisk kryptanalyse – kan ' ikke huske detaljerne).

Nogle mere specifikke eksempler:

• Calculus bruges til at udlede delta-regel , hvilket er det, der gør det muligt for nogle typer neurale netværk at “lære”.
• Calculus kan bruges til at beregne Fourier-transformationen af en oscillerende funktion, meget vigtig i signalanalyse.
• Calculus bruges hele tiden i computergrafik, hvilket er et meget aktivt felt, da folk hele tiden opdager nye teknikker. For et grundlæggende eksempel, tjek Kajiyas gengivelsesligning
• Beregning er vigtig inden for beregningsgeometri, undersøg kurve- og overflademodellering.

Til disse andre fremragende svar tilføjer jeg dette punkt: stringens i test .

Ved oprettelse af testcases til nogle applikationer har jeg været nødt til at bruge beregning til at forudsige forventede driftstider, hukommelsesstørrelser, og vælg optimale parametre, når du indstiller datastrukturer. Dette inkluderer forståelse af forventet afrundingsfejl osv.

Mens statistik nævnes i andre svar, vil jeg specifikt nævne Monte-carlo-algoritmer , såsom optimeringsalgoritmer og nogle sparsomme streamingalgoritmer , der er baseret på matematiske principper, der inkluderer calculus.

Specifikke brancher, hvor jeg har arbejdet, hvor calculus var påkrævet, inkluderer:

• Finance (oprettelse af en handelsplatform)

• Forsikring (numerisk integration af forsikringspolicer i hvad-hvis-scenarier til beregning af forventede forsikringstab)

• Logistik (optimering af konsolidering af transportruter)

• Signalbehandling

Calculus – den integrerede del – bruges direkte i CS som et fundament til at tænke på summering. Hvis du arbejder igennem en del af Knuths afsnit om konkret matematik om opsummering, vil du hurtigt genkende konventioner, der er fælles for beregning: At forstå nogle af de kontinuerlige tilfælde giver dig værktøjer til at overveje det diskrete.

Mange af anvendelserne i din CS-undersøgelse involverer programmeringssystemer, der overvåger ændringer eller i nogle tilfælde forsøger at forudsige fremtiden. Matematikken omkring disse systemer er forankret i differentialligninger og lineær algebra, og differentialligninger er … calculus. Der er lærere som Gibert Strang, der fortaler for at bevæge sig hurtigere ind i differentialligningsdelen, men det er stadig en delmængde af beregning. Når ændring afhænger af ændringer i ethvert system, begynder det at være ustabil (og stabil) på måder, der både er ikke-intuitive og For at forstå, hvorfor dit fornuftige lineære system opfører sig på ikke-lineære måder, har du enten brug for beregningsværktøjerne, eller du skal genopfinde dem til dit problemrum.

Og til sidst, CS ofte kræver læsning og forståelse af andres arbejde, og beregning er den første eksponering for en masse fælles ordforråd, konvention og historie.

Kommentarer

• " Mange af anvendelserne i din CS-undersøgelse involverer programmeringssystemer, der overvåger ændringer, eller i nogle tilfælde forsøge at forudsige fremtiden " – Jeg tror ikke ' at dette er repræsentativt for CS-studier.