Jak / kiedy stosuje się rachunek różniczkowy w informatyce?

95

Wiele programów informatycznych wymaga dwóch lub trzech klas rachunku różniczkowego.

Zastanawiam się, jak i kiedy stosuje się rachunek różniczkowy w informatyce? Treść CS pewnego stopnia w dziedzinie informatyki zwykle koncentruje się na algorytmach, systemach operacyjnych, strukturach danych, sztucznej inteligencji, inżynierii oprogramowania itp. Czy zdarzają się sytuacje, w których Rachunek jest przydatny w tych lub innych obszarach informatyki?

education mathematical-analysis Zwycięzca
źródło

6

Nie mamy ścisłej polityki dotyczącej pytań z listy, ale istnieje ogólna niechęć . Proszę zwrócić uwagę również na tę i tę dyskusję; możesz poprawić swoje pytanie, aby uniknąć opisanych tam problemów. Jeśli nie jesteś pewien, jak poprawić swoje pytanie, może pomożemy Ci na czacie z informatyki ?

Raphael

42

Wydaje się, że popełniacie powszechny błąd, zakładając, że treść każdego kursu musi być odpowiednia (dla każdej ścieżki kariery). Czasami chodzi tylko o szkolenie cię, jak myśleć w określony sposób.

Raphael

8

Byłoby to prawdopodobnie pomocne, gdyby to pytanie mogło wyjaśnić, czy pytasz tylko o zastosowania w informatyce właściwe, czy też o wszystkie zastosowania dla studentów, którzy dostają dyplom Comp Sci. Przynajmniej tutaj, w Stanach Zjednoczonych, bardzo duży odsetek absolwentów Comp Sci zostaje inżynierami oprogramowania w niemal każdej możliwej dziedzinie inżynierii. Wiele z tych domen wymaga zrozumienia rachunku różniczkowego do różnych celów. Nie wszystkie grads CS użyje Rachunek w swojej pracy, ale wielu z pewnością będzie (prawdopodobnie ponad którzy myślą, że będzie w trakcie pierwszego roku studiów.)

reirab

1

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

Raphael

Dla mnie było to bardzo przydatne w poczuciu „uznania i ulgi później, gdy poznałem metody numeryczne” . Podczas pracy z dyskretnymi danymi pochodzącymi z rzeczywistych pomiarów, zamiast ciągłych funkcji z matematyki teoretycznej, było tak wielką ulgą, że integracja to tylko suma, a pochodna to tylko odejmowanie, zamiast zbyt skomplikowanych formuł, których potrzebowaliśmy tyle czasu i wysiłku uczyć się wcześniej w naszych klasach rachunku różniczkowego!

vsz 8.04.16

110

Mogę wymyślić kilka kursów, które bezpośrednio wymagałyby rachunku różniczkowego . Użyłem pogrubionej twarzy w przypadku zwykle obowiązkowych dyscyplin w zakresie informatyki, a kursywą w przypadku zwykle opcjonalnych.

Computer Graphics Processing / obrazu, a tu będzie musiała geometrią analityczną i algebry liniowej, mocno ! Jeśli pójdziesz tą ścieżką, możesz również chcieć przestudiować geometrię różnicową (która ma minimalny rachunek różniczkowy jako warunek minimum). Ale potrzebujesz tutaj rachunku nawet dla bardzo podstawowych rzeczy: na przykład wyszukaj „transformatę Fouriera” lub „falki” - są to dwa bardzo podstawowe narzędzia dla osób pracujących z obrazami.
Optymalizacja , głównie nieliniowa, gdzie rachunek wielowymiarowy jest podstawowym językiem używanym do rozwoju wszystkiego. Ale nawet optymalizacja liniowa korzysta z rachunku różniczkowego (pochodna funkcji celu jest absolutnie ważna)
Prawdopodobieństwo / Statystyka . Nie można ich poważnie zbadać bez rachunku różniczkowego.
Uczenie maszynowe , które intensywnie wykorzystuje statystyki (aw konsekwencji rachunek wielowymiarowy)
Data Mining i powiązane tematy, które również korzystają z wielu statystyk;
Robotyka , w której będziesz musiał modelować fizyczne ruchy robota, więc musisz znać pochodne cząstkowe i gradienty.
Dyskretna matematyka i kombinatoryka ( tak! Możesz potrzebować rachunku do dyskretnego zliczania!) - jeśli wystarczająco poważnie podchodzisz do generowania funkcji, musisz wiedzieć, jak integrować i wyprowadzać określone formuły. Jest to przydatne w przypadku analizy algorytmów (patrz książka Sedgewicka i Flajoleta, „Analiza algorytmów”). Podobnie, szereg Taylora i rachunek różniczkowy mogą być przydatne w rozwiązywaniu pewnych rodzajów relacji rekurencyjnych, które są wykorzystywane w analizie algorytmów.
Analiza algorytmów , w której od samego początku używasz pojęcia limitu (patrz notacja Landaua, „trochę ” - jest definiowana przy użyciu limitu) $o$

Mogą być też inne - to jest tuż nad moją głową.

Poza tym pośrednio korzysta się z kursu Rachunku Rachunkowego, ucząc się rozumowania i wyjaśniania argumentów z techniczną dyscypliną. Jest to cenniejsze, niż zwykle myślą uczniowie.

Wreszcie - będziesz potrzebować Calculus, aby, cóż, wchodzić w interakcje z ludźmi z innych ścisłych nauk i inżynierii. I nierzadko informatyk musi nie tylko rozmawiać, ale także współpracować z fizykiem lub inżynierem.

Sójka
źródło

34

Być może miałeś inne doświadczenie, ale uznałem rachunek za całkiem bezużyteczny do nauki rygorystycznego rozumowania i wyjaśniania argumentów. Nauczał go rote i dopasowywanie wzorów, podobnie jak algebra i geometria w szkole średniej. Z drugiej strony, był to warunek wstępny do kilku wyższych klas matematycznych, które zrobił uczyć tych umiejętności, więc przypuszczam, że to nie była całkowicie bezużyteczna.

tsleyson,

6

Mogę całkowicie odnieść się do ostatniego punktu (korzyści pośrednie). Pracując nad teorią języków programowania, rzadko używałem rachunku różniczkowego. Być może najbardziej bezpośrednią aplikacją były probabilistyczne modele obliczeniowe (np. Probabilistyczne domeny mocy Plotkin i Jones). Jednak mój rachunek różniczkowy polegał głównie na sprawdzaniu rzeczy, a to było bardzo, bardzo cenne. W każdym poważnym programie CS potrzebny jest jeden lub dwa kursy rachunku różniczkowego i matematycznego (więcej matematyki, logiki, algebry liniowej, analizy numerycznej, ... i ewentualnie kategorii, topologii, algebry, ...).

chi

3

Oto przykład, jak ja potrzebowałem rachunku w grafice komputerowej: Gładkie funkcje interpolacji będzie w zasadzie wszystko mieć postać f(0) = 0, f(1) = 1, f'(0) = f'(1) = 0, i można dodawać żadnych innych ograniczeń, na których Ci zależy, na przykład f'(0.5) = 1. Jakiś czas temu wykorzystałem to do uzyskania różnych wielomianów interpolacyjnych do wygładzania obrazów.

porglezomp 6.04.16

3

Robotyka może być prawdopodobnie rozszerzona do dowolnego rodzaju modelowania fizyki (które, jak sądzę, obejmuje również CG, jeśli chodzi o oświetlenie, więc nazwijmy to modelowaniem fizyki kinetycznej). Obejmuje przyspieszania / prędkości, odbija / sprężyny / odkształcenia, PID, akustyka, grawitację ...

metao

2

Poprę pośrednio ten punkt w ten sposób: lepiej niż jakakolwiek klasa, którą uczą wcześniej, Rachunek uczy uczniów, że nie mogą po prostu policzyć liczby problemów i oszacować, ile pracy będzie wymagało.

candied_orange 10.04.16

20

Jest to nieco niejasne, ale rachunek różniczkowy pojawia się w algebraicznych typach danych. Dla dowolnego typu typ kontekstów z jednym otworem jest pochodną tego typu. Zobacz tę doskonałą rozmowę, aby uzyskać przegląd całego tematu. To bardzo techniczna terminologia, więc wyjaśnijmy.

Algebraiczne typy danych

Być może natrafiłeś na krotki określane jako typy produktów (jeśli nie, to dlatego, że są to kartezjańskie produkty dwóch rodzajów). Przyjmiemy to dosłownie i użyjemy zapisu:

a * b

$a * b$

Do reprezentowania krotki, gdzie i są oba typy. Następnie możesz natknąć się na typy sum, są to typy, które mogą być albo jednym rodzajem, albo drugim (znanym jako związki , warianty lub jako oba typy (rodzaj) w Haskell). Weźmiemy to również dosłownie i użyjemy zapisu: $a$ $b$

a + b

$a + b$

Są one nazywane jakimi są, ponieważ jeśli typ ma wartości , a typ ma wartości , to typ ma wartości . $a$ $N_a$ $b$ $N_b$ $a + b$ $N_a + N_b$

Te typy wyglądają jak normalne wyrażenia algebraiczne i możemy w rzeczywistości nimi manipulować (do pewnego stopnia).

Przykład

W językach funkcjonalnych powszechną definicją listy (podaną tutaj w Haskell) jest:

data List a = Empty 
            | Cons a List

Oznacza to, że lista jest pusta lub krotka wartości i inna lista. Przekształcając to w notację algebraiczną, otrzymujemy:

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

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

Gdzie oznacza typ o jednej wartości (inaczej typ jednostki). Przez wielokrotne wstawianie możemy to ocenić, aby uzyskać definicję : $1$ $L(a)$

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

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

L (a) = 1 + 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 * (1 + a * L(a))$

L (a) = 1 + a + a^{2} + a^{3} * (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} . . .

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

(Gdzie oznacza wielokrotne mnożenie). $x^n$

Ta definicja mówi wtedy, że lista jest albo jednostką, albo krotką jednego elementu, albo krotką dwóch elementów, albo trzech itd., Co jest definicją listy!

Konteksty z jednym otworem

Przejdźmy teraz do kontekstów z jednym dołkiem: kontekst z jednym dołkiem jest tym, co dostajesz, gdy „bierzesz wartość” z rodzaju produktu. Podajmy przykład:

Dla prostego 2-krotek, który jest jednorodny, , jeśli weźmiemy wartość, otrzymamy po prostu 1-krotkę, . Istnieją jednak dwa różne konteksty z jednym otworem tego typu: mianowicie pierwsza i druga wartość krotki. Skoro jest to którykolwiek z nich, moglibyśmy napisać, że jest , czyli oczywiście . Tutaj właśnie pojawia się zróżnicowanie. Potwierdźmy to innym przykładem: $a^2$ $a$ $a + a$ $2a$

Wyciągnięcie wartości z 3-krotek daje 2-krotkę, ale istnieją trzy różne warianty:

(a, a,_)

$(a, a, \_)$

(a,_, a)

$(a, \_, a)$

(_, a, a)

$(\_, a, a)$

W zależności od tego, gdzie umieszczamy otwór. To daje nam która jest rzeczywiście pochodną . Jest dowodem na to w ogóle tutaj . $3a^2$ $a^3$

W naszym ostatnim przykładzie użyjmy listy:

Jeśli weźmiemy nasze oryginalne wyrażenie na listę:

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

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

Możemy zmienić układ, aby uzyskać:

L (a) = \frac{1}{1 - a}

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

(Na pierwszy rzut oka może to wydawać się nonsensem, ale jeśli weźmiesz serię Taylor tego wyniku, otrzymasz definicję, którą wyprowadziliśmy wcześniej.)

Jeśli to rozróżnimy, otrzymamy ciekawy wynik:

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

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

Tak więc jedna lista stała się parą list. Ma to w rzeczywistości sens: dwie wytworzone listy odpowiadają elementom powyżej i poniżej dziury na oryginalnej liście!

Tuomas Laakkonen
źródło

To było cudownie wnikliwe. Dzięki.

D. Ben Knoble

12

Metody numeryczne. Istnieją kłopotliwe problemy z kamieniami nazębnymi, które są unikalne dla określonych aplikacji i potrzebują rozwiązań szybciej niż człowiek jest w stanie rozwiązać praktycznie bez programu. Ktoś musi zaprojektować algorytm, który obliczy rozwiązanie. Czy to nie jedyna rzecz, która oddziela programistów od naukowców?

Jonasz Havel
źródło

3

Biorąc pod uwagę „listową” naturę tego pytania, każda odpowiedź powinna próbować dać pełny obraz. Czy na pewno chcesz twierdzić, że metody numeryczne są jedyną instancją?

Raphael

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

Raphael

12

Automatyzacja - podobnie jak robotyka, automatyzacja może wymagać ilościowego określenia wielu ludzkich zachowań.

Obliczenia - Znalezienie rozwiązań dla dowodów często wymaga rachunku różniczkowego.

Wizualizacje - wykorzystanie zaawansowanych algorytmów wymaga rachunku różniczkowego, takiego jak cos, sinus, pi i e. Zwłaszcza podczas obliczania wektorów, pól kolizji i tworzenia siatki.

Logistyka i analiza ryzyka - Określenie, czy dane zadanie jest możliwe, związane z nim ryzyko i możliwa stopa sukcesu.

Bezpieczeństwo - Większość zabezpieczeń można wykonać bez rachunku; jednak wiele osób, które chcą wyjaśnień, woli je w wyrażeniach matematycznych.

AI - Podstawy AI można wykorzystać bez rachunku; jednak obliczanie zaawansowanego zachowania, inteligencji roju / umysłu ula i podejmowania decyzji opartych na złożonych wartościach.

Obliczenia medyczne - Wizualizacja większości danych zdrowotnych wymaga rachunku, takiego jak odczyt EKG.

Nauka i inżynieria - podczas pracy z prawie każdą inną dyscypliną naukową wymaga rachunku: kosmonautyka, astrologia, biologia, chemia lub inżynieria.

Wiele osób zajmujących się programowaniem może przejść całą swoją karierę bez rachunku różniczkowego; może jednak okazać się bezcenny, jeśli chcesz wykonać pracę. Dla mnie jest najbardziej skuteczny w automatyce, logistyce i wizualizacji. Identyfikując określone wzorce, możesz po prostu zignorować wzór, naśladować wzór lub wspólnie opracować lepszą metodę.

LJones
źródło

7

Jak wyglądają rachunki cos, sinus, i ?

π

$\pi$

e

$\mathrm{e}$

David Richerby,

3

Cóż, można zdefiniować jako unikalne rozwiązanie dla przy , i podobnie sin, cos można zdefiniować jako unikalną parę funkcji spełniających , w odpowiednich warunkach granicznych (chyba , a powinien pracować).

\exp (x)

$\exp(x)$

f (x) = f^{'} (x)

$f(x)=f'(x)$

f (0) = 1

$f(0)=1$

f^{'} (x) = g (x)

$f'(x)=g(x)$

g^{'} (x) = - f (x)

$g'(x) = -f(x)$

f (0) = 0

$f(0)=0$

g (0) = 1

$g(0)=1$

Chris Taylor,

2

@DavidRicherby: Przykład: w jaki sposób realizować te funkcje, na, powiedzmy, mikrokontroler bez FPU? Jeśli znasz rachunek różniczkowy, od razu znasz dobrą odpowiedź: serie mocy.

Nate Eldredge,

6

Faktem jest, że istnieje bardzo mała szansa, że kiedykolwiek użyjesz rachunku różniczkowego. Jednak praktycznie każda inna dyscyplina naukowa korzysta z rachunku różniczkowego i pracujesz nad stopniem naukowym. Istnieją pewne oczekiwania co do znaczenia uniwersyteckiego stopnia naukowego, a jedną z tych rzeczy jest to, że znasz rachunek różniczkowy. Nawet jeśli nigdy go nie użyjesz.

W porządku, jeśli źle radzisz sobie z rachunkiem różniczkowym, ale upewnij się, że włożyłeś trochę wysiłku w dyskretną matematykę. Istnieje wiele rzeczywistych problemów programistycznych, w których pojawia się dyskretna matematyka, a nieznajomość jej zasad może zawstydzić Cię przed innymi programistami.

Scott B.
źródło

9

Twój pierwszy akapit jest całkowicie błędny i graniczy z teorią spiskową. Istnieje wystarczająco dużo obszarów informatyki, w których użyteczny jest rachunek różniczkowy (patrz inne odpowiedzi na niekończące się ich listy). Jasne, można uniknąć tych wszystkich obszarów, ale bardzo mylące jest twierdzenie, że upuszczenie rachunku różniczkowego i zerowego będzie miało większy wpływ niż oceny.

David Richerby,

4

W zależności od programu studiów możesz ukończyć studia bez użycia rachunku różniczkowego i zdecydowanie uważam, że kierunki CS nie potrzebują tak dużo, jak to możliwe. Ale jeśli zrobisz to źle, zablokujesz niektóre z najciekawszych dziedzin informatyki. Po ukończeniu studiów jest dużo czasu na programistę; będąc w szkole, może spróbujesz się trochę popchnąć?

tsleyson,

3

@tsleyson Jeśli chcesz zostać programistą, zaoszczędź pieniądze i czas potrzebny na uzyskanie dyplomu CS.

Raphael

8

@ScottB Wygląda na to, że mylisz informatykę z programowaniem.

David Richerby,

3

@ ScottB Kto mówi, że CS = matematyka + programowanie? Ja od dawna opowiadam się za tym ograniczonym poglądem. Ale masz to również do tyłu: matematyka jest integralną częścią CS, podobnie jak fizyki. My potrzebujemy go, nawet jeśli nie chcemy, aby ćwiczyć go. (To powiedziawszy, to nie jest miejsce na tę dyskusję. Dołącz do nas na Czacie Informatyki, jeśli chcesz kontynuować.)

Raphael

4

Wiele osób już dostarczyło aplikacje w CS. Ale czasami znajdziesz Rachunek, gdy najmniej się spodziewasz:

Ponownie zbadane pochodne o regularnej ekspresji

Jeśli znasz automaty, ten plik PDF może być wart przeczytania.

Aristu
źródło

Nie widzę tam rachunku różniczkowego; Widzę słowo „pochodna”, ale nie widzę niczego, co przypominałoby tradycyjny rachunek różniczkowy.

2

Nazywa się to „formalną pochodną” i jest niejako związane z Rachunkiem. Zobaczysz to również przy pomocy funkcji generowania, niektórych formuł związanych z dyskretnymi strukturami i innych obszarów, w których tak naprawdę nie masz „płynnej funkcji”.

Jay

@Jay: Ważną rzeczą nie jest nazwa. W jaki sposób zrozumienie rachunku różniczkowego pomaga w tym?

Christian

2

Wyjaśniono to na tej stronie Wikipedii . Formalna pochodna jest operacją na elementach struktury analgebraicznej, która zawiera wielomiany, i formalnie jest „całkiem podobna” do zwykłej reguły różnicowania wielomianów, jednak - inaczej niż to, co uczeń widzi w rachunku różniczkowym - wielomiany nie są ponad rzeczywistością; mogą być wielomianami nad dowolnym „pierścieniem” (inną strukturą algebraiczną). I są praktyczne zastosowania formalnej pochodnej - widziałem przynajmniej jedną (Algebraiczna kryptoanaliza - nie pamiętam szczegółów).

Jay

4

Kilka bardziej szczegółowych przykładów:

Rachunek różniczkowy służy do wyprowadzenia reguły delta , która pozwala niektórym typom sieci neuronowych „uczyć się”.
Rachunku można użyć do obliczenia transformaty Fouriera funkcji oscylacyjnej, bardzo ważnej w analizie sygnałów.
Rachunek różniczkowy jest cały czas wykorzystywany w grafice komputerowej, która jest bardzo aktywną dziedziną, ponieważ ludzie nieustannie odkrywają nowe techniki. Podstawowym przykładem jest równanie renderujące Kajiya
Rachunek jest ważny w dziedzinie geometrii obliczeniowej, badania modelowania krzywych i powierzchni.

pies Jones
źródło

3

Do tych innych doskonałych odpowiedzi dodam ten punkt: rygor w testowaniu .

Podczas tworzenia przypadków testowych dla niektórych aplikacji musiałem użyć rachunku różniczkowego, aby przewidzieć oczekiwane czasy działania, rozmiary pamięci i wybrać optymalne parametry podczas dostrajania struktur danych. Obejmuje to zrozumienie oczekiwanego błędu zaokrąglenia itp.

Chociaż statystyki są wspomniane w innych odpowiedziach, chciałbym w szczególności wspomnieć o algorytmach Monte-Carlo , takich jak algorytmy optymalizacji i niektóre oszczędne algorytmy strumieniowania oparte na zasadach matematycznych, które obejmują rachunek różniczkowy.

Konkretne branże, w których pracowałem, w których wymagany był rachunek różniczkowy, obejmują:

Finanse (tworzenie platformy handlowej)
Ubezpieczenia (numeryczna integracja polis ubezpieczeniowych w scenariuszach „co jeśli”, aby obliczyć oczekiwane straty polis)
Logistyka (optymalizacja konsolidacji tras transportowych)
Przetwarzanie sygnałów

Paul Chernoch
źródło

3

Rachunek całkowy - część integralna - jest wykorzystywany bezpośrednio w CS jako podstawa do myślenia o sumowaniu. Jeśli przejrzysz dowolną część sekcji Matematyki konkretnej Knutha na temat sumowania, szybko rozpoznasz konwencje wspólne dla rachunku różniczkowego: zrozumienie niektórych ciągłych przypadków daje ci narzędzia do rozważenia dyskrecji.

Wiele zastosowań twojego badania CS obejmuje systemy programowania, które monitorują zmiany, aw niektórych przypadkach próbują przewidzieć przyszłość. Matematyka wokół tych układów jest zakorzeniona w równaniach różniczkowych i algebrze liniowej, a równania różniczkowe są ... rachunkiem różniczkowym. Są nauczyciele tacy jak Gibert Strang, którzy opowiadają się za szybszym przejściem do części równań różniczkowych, ale wciąż jest to podzbiór rachunku różniczkowego. Kiedy zmiana zależy od zmiany w dowolnym systemie, zaczyna być niestabilna (i stabilna) w sposób, który jest nieintuicyjny i bardzo dobrze zrozumiany. Aby zrozumieć, dlaczego twój rozsądny układ liniowy zachowuje się w nieliniowy sposób, potrzebujesz narzędzi rachunku różniczkowego lub musisz je na nowo wymyślić dla swojej przestrzeni problemów.

I wreszcie, CS często wymaga czytania i rozumienia pracy innych, a rachunek różniczkowy i matematyczny jest pierwszą ekspozycją na wiele wspólnych słowników, konwencji i historii.

Pęto
źródło

„Wiele zastosowań twojego badania CS obejmuje systemy programowania, które monitorują zmiany, aw niektórych przypadkach próbują przewidzieć przyszłość” - nie sądzę, że jest to reprezentatywne dla wielu kursów CS.

Raphael

Jak / kiedy stosuje się rachunek różniczkowy w informatyce?

Odpowiedzi:

Algebraiczne typy danych

Przykład

Konteksty z jednym otworem