Wie / wann wird in der Informatik Kalkül verwendet?

Dies ist etwas dunkel, aber der Kalkül taucht in algebraischen Datentypen auf. Für jeden gegebenen Typ ist der Typ seiner Ein-Loch-Kontexte die Ableitung dieses Typs. In dieses ausgezeichneten Vortrags finden Sie einen Überblick über das gesamte Thema. Dies ist eine sehr technische Terminologie. Lassen Sie uns dies erklären.

Algebraische Datentypen

Möglicherweise sind Sie auf Tupel gestoßen, die als Produkttypen bezeichnet werden (wenn nicht, weil sie das kartesische Produkt zweier Arten sind). Wir werden dies wörtlich nehmen und die Notation verwenden:

$$ a * b $$

Zur Darstellung ein Tupel, in dem $ a $ und $ b $ beide Typen sind. Als nächstes sind Sie möglicherweise auf etwas gestoßen Summentypen Dies sind Typen, die entweder der eine oder der andere Typ sein können (bekannt als Gewerkschaften , Varianten oder als Entweder Typ (irgendwie) in Haskell). Wir werden diesen auch wörtlich nehmen und die Notation verwenden:

$$ a + b $$

Diese werden so benannt, wie sie sind, denn wenn ein Typ $ a $ $ hat N_a $ -Werte und ein Typ $ b $ haben $ N_b $ -Werte, dann den Typ $ a + b $ hat $ N_a + N_b $ -Werte.

Diese Typen sehen aus wie normale algebraische Ausdrücke und Wir können sie tatsächlich als solche (bis zu einem gewissen Punkt) manipulieren.

Ein Beispiel

In funktionalen Sprachen lautet die übliche Definition einer Liste (hier in Haskell angegeben):

data List a = Empty | Cons a List 

Dies besagt, dass eine Liste entweder leer ist oder ein Tupel eines Werts und einer anderen Liste. Wenn wir das in eine algebraische Notation umwandeln, erhalten wir:

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

Wobei $ 1 $ einen Typ mit einem Wert darstellt (auch bekannt als Einheitentyp). Durch wiederholtes Einfügen können wir dies auswerten, um eine Definition für $ L (a) $ zu erhalten:

$$ 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 … $$

(Wobei $ x ^ n $ ist im Sinne einer wiederholten Multiplikation gemeint.)

Diese Definition besagt dann, dass eine Liste entweder eine Einheit oder ein Tupel von ist ein Element oder ein Tupel aus zwei oder drei Elementen usw., das ist die Definition einer Liste!

Ein-Loch-Kontexte

Nun zu Ein-Loch-Kontexten: Ein Ein-Loch-Kontext erhalten Sie, wenn Sie einen Wert aus einem Produkttyp „herausnehmen“. Geben wir ein Beispiel:

Für ein einfaches 2-Tupel, das homogen ist, $ a ^ 2 $ , wenn wir einen Wert herausnehmen erhalten wir nur ein 1-Tupel, $ a $ .Es gibt jedoch zwei verschiedene Ein-Loch-Kontexte dieses Typs: den ersten und den zweiten Wert des Tupels. Da es sich also um eines von beiden handelt, könnten wir schreiben, dass es sich um $ a + a $ handelt, was natürlich $ 2 ist ein $ . Hier kommt die Differenzierung ins Spiel. Bestätigen wir dies mit einem anderen Beispiel:

Wenn Sie einen Wert aus einem 3-Tupel herausnehmen, erhalten Sie ein 2-Tupel, aber es gibt drei verschiedene Varianten:

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

Abhängig davon, wo wir das Loch platzieren. Dies gibt uns $ 3a ^ 2 $ , was in der Tat die Ableitung von $ a ^ 3 $ ist. Es gibt einen Beweis dafür im Allgemeinen hier .

Verwenden wir für unser letztes Beispiel eine Liste:

Wenn wir unseren ursprünglichen Ausdruck für eine Liste verwenden:

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

Wir können neu anordnen, um Folgendes zu erhalten:

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

(An der Oberfläche dies mag wie Unsinn erscheinen, aber wenn Sie die Taylor-Reihe dieses Ergebnisses nehmen, erhalten Sie die Definition, die wir zuvor abgeleitet haben.)

Wenn wir dies nun differenzieren, g und ein interessantes Ergebnis:

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

Somit ist eine Liste zu einem Listenpaar geworden. Dies ist in der Tat sinnvoll: Die beiden erstellten Listen entsprechen den Elementen über und unter dem Loch in der ursprünglichen Liste!

Kommentare

• Das war wunderbar aufschlussreich. Vielen Dank.

Numerische Methoden. Es gibt umständliche Kalkülprobleme, die nur für bestimmte Anwendungen gelten, und sie benötigen Lösungen, die schneller sind, als ein Mensch ohne Programm praktisch lösen kann. Jemand muss einen Algorithmus entwerfen, der die Lösung berechnet. Ist das nicht das einzige, was Programmierer von Wissenschaftlern unterscheidet?

Kommentare

• Angesichts der " list " Bei dieser Frage sollte jede Antwort versuchen, ein vollständiges Bild zu vermitteln. Sind Sie sicher, dass Sie behaupten möchten, dass numerische Methoden die einzige Instanz sind?
• Kommentare sind nicht für eine ausführliche Diskussion gedacht. Diese Konversation wurde in den Chat verschoben .

Automatisierung – Ähnlich wie Robotik, Automatisierung kann die Quantifizierung vieler menschlicher Verhaltensweisen erfordern.

Berechnungen – Um Lösungen für Beweise zu finden, ist häufig eine Berechnung erforderlich.

Visualisierungen – Die Verwendung fortschrittlicher Algorithmen erfordert Berechnungen wie cos, sinus, pi und e wenn du rechnest Vektoren, Kollisionsfelder und Vernetzung.

Logistik- und Risikoanalyse – Bestimmen, ob eine Aufgabe vorliegt möglich, das damit verbundene Risiko und die mögliche Erfolgsrate.

Sicherheit – Die meiste Sicherheit kann ausgeführt werden ohne Kalkül; Viele Leute, die Erklärungen wünschen, bevorzugen diese jedoch in mathematischen Ausdrücken.

AI – Die Grundlagen der AI kann ohne Kalkül verwendet werden; Berechnen von fortgeschrittenem Verhalten, Schwarmintelligenz / Schwarmgeist und auf komplexen Werten basierenden Entscheidungen.

Medizinische Berechnungen – Für die Visualisierung der meisten Gesundheitsdaten ist ein Kalkül wie ein EKG-Messwert erforderlich.

Wissenschaft & Engineering – Wenn Sie mit fast jeder anderen wissenschaftlichen Disziplin arbeiten, ist Kalkül erforderlich: Luft- und Raumfahrt, Astrologie, Biologie, Chemie oder Ingenieurwesen.

Viele Programmierer können ihre gesamte Karriere ohne sie absolvieren mit Kalkül; Es kann sich jedoch als von unschätzbarem Wert erweisen, wenn Sie bereit sind, die Arbeit zu erledigen. Für mich war es in Bezug auf Automatisierung, Logistik und Visualisierung am effektivsten. Indem Sie bestimmte Muster identifizieren, können Sie das Muster einfach ignorieren, das Muster imitieren oder ein Muster entwickeln überlegene Methode insgesamt.

Kommentare

• Wie sind cos, Sinus, $ \ pi $ und $ \ mathrm {e} $ Kalkül?
• Nun, $ \ exp (x) $ kann als eindeutige Lösung für $ f (x) = f ' (x) $ mit $ f (definiert werden 0) = 1 $ und in ähnlicher Weise sin, cos kann als das eindeutige Funktionspaar definiert werden, das $ f ' (x) = g (x) $, $ g ' (x) = -f (x) $ mit geeigneten Randbedingungen (ich denke, $ f (0) = 0 $ und $ g (0) = 1 $ sollten funktionieren).
• @DavidRicherby: Beispiel: Wie können Sie diese Funktionen beispielsweise auf einem Mikrocontroller ohne FPU implementieren ? Wenn Sie einen Kalkül kennen, kennen Sie sofort eine gute Antwort: Potenzreihen.

Tatsache ist dass es sehr wenig Chancen gibt, dass Sie jemals Kalkül verwenden werden. In praktisch jeder anderen wissenschaftlichen Disziplin wird jedoch Kalkül verwendet, und Sie arbeiten an einem naturwissenschaftlichen Abschluss. Es gibt bestimmte Erwartungen an das, was ein Universitätsabschluss bedeuten soll, und eines dieser Dinge ist, dass Sie sich mit Kalkül auskennen. Selbst wenn Sie es nie verwenden werden.

Es ist in Ordnung, wenn Sie schlecht im Rechnen sind, aber stellen Sie sicher, dass Sie sich etwas Mühe mit diskreter Mathematik geben. Es gibt viele reale Programmierprobleme, bei denen diskrete Mathematik ins Spiel kommt und Unkenntnis ihrer Prinzipien Sie vor anderen Programmierern in Verlegenheit bringen kann.

Kommentare

• Ihr erster Absatz ist völlig falsch und grenzt an Verschwörungstheorie. Es gibt genügend Bereiche der Informatik, in denen Kalkül nützlich ist (siehe die anderen Antworten für endlose Listen von ihnen). Sicher, es ist ' möglich, all diese Bereiche zu vermeiden, aber ' ist sehr irreführend zu behaupten, dass das Löschen von Kalkül darüber hinaus keine Auswirkungen hat Noten.
• Abhängig von Ihrem Studiengang könnten Sie einen Abschluss machen, ohne jemals Kalkül zu verwenden, und ich denke definitiv, dass CS-Majors ' nicht so viel davon benötigen wie wir bekommen. Wenn Sie jedoch schlecht damit umgehen, werden Sie von einigen der interessantesten Bereiche der Informatik ausgeschlossen. ' hat nach Ihrem Abschluss genügend Zeit, um Webentwickler zu werden. Warum versuchen Sie nicht, sich in der Schule ein wenig zu pushen?
• @tsleyson Wenn Sie Webentwickler werden möchten, sparen Sie Geld und Zeit, um einen CS-Abschluss zu erhalten.
• @ScottB Sie scheinen Informatik mit Programmierung zu verwechseln.
• @ScottB Wer ' sagt CS = Mathe + Programmierung? Ich selbst habe mich seit Ewigkeiten gegen diese eingeschränkte Sichtweise ausgesprochen. Aber Sie haben es auch rückwärts: Mathematik ist ein wesentlicher Bestandteil von CS, genau wie es für die Physik ist. Wir brauchen es, auch wenn wir ' es nicht üben wollen. (Dies ist jedoch nicht der Ort für diese Diskussion. Bitte nehmen Sie an Informatik-Chat teil, wenn Sie fortfahren möchten.)

Viele Leute haben bereits Anwendungen in CS bereitgestellt. Aber manchmal finden Sie Calculus, wenn Sie es am wenigsten erwarten:

Derivate mit regulären Ausdrücken erneut untersucht

Wenn Sie wissen Automaten Dieses PDF ist möglicherweise lesenswert.

Kommentare

• ' Ich sehe keine Differentialrechnung Ich sehe das Wort " Ableitung ", aber ich sehe ' nichts ähnelt der traditionellen Differentialrechnung.
• ' heißt " formale Ableitung ", und es hängt in gewisser Weise mit Calculus zusammen. Sie werden dies auch mit Generierungsfunktionen sehen, einige Formeln, die sich auf diskrete Strukturen beziehen, und andere Bereiche, in denen Sie nicht ' t haben tatsächlich eine " glatte Funktion ".
• @Jay: Das Wichtigste ist nicht ' t den Namen. Wie versteht man ng Kalkül helfen dabei?
• Es wird auf dieser Wikipedia-Seite erklärt. Die formale Ableitung ist eine Operation für Elemente der analgebraischen Struktur, die Polynome enthält, und sie ist formal " ziemlich ähnlich wie " die übliche Regel zur Differenzierung Polynome jedoch – anders als das, was ein Schüler in Calculus sieht – sind die Polynome nicht über Real; Sie können Polynome über einem beliebigen " Ring " (einer anderen algebraischen Struktur) sein. Und es gibt praktische Anwendungen der formalen Ableitung – ich habe mindestens eine gesehen (Algebraische Kryptoanalyse – kann sich ' nicht an die Details erinnern).

Einige spezifischere Beispiele:

• Der Kalkül wird verwendet, um die Delta-Regel , mit der einige Arten von neuronalen Netzen „lernen“ können.
• Die Berechnung kann zur Berechnung der Fourier-Transformation einer oszillierenden Funktion verwendet werden Signalanalyse.
• Kalkül wird ständig in der Computergrafik verwendet. Dies ist ein sehr aktives Feld, da die Menschen ständig neue Techniken entdecken. Ein grundlegendes Beispiel finden Sie in Kajiyas Rendering-Gleichung .
• Die Berechnung ist im Bereich der rechnerischen Geometrie wichtig.

Zu diesen anderen hervorragenden Antworten füge ich diesen Punkt hinzu: Genauigkeit beim Testen .

Beim Erstellen von Testfällen für einige Anwendungen musste ich Kalkül verwenden, um erwartete Laufzeiten, Speichergrößen usw. vorherzusagen. und wählen Sie optimale Parameter beim Optimieren von Datenstrukturen. Dies beinhaltet das Verständnis des erwarteten Rundungsfehlers usw.

Während Statistiken in anderen Antworten erwähnt werden, möchte ich speziell Monte-Carlo-Algorithmen , z. B. Optimierungsalgorithmen und einige sparsame Streaming-Algorithmen , die auf mathematischen Prinzipien basieren, die Folgendes umfassen Kalkül.

Zu den spezifischen Branchen, in denen ich gearbeitet habe, in denen Kalkül erforderlich war, gehören:

• Finanzen (Erstellen einer Handelsplattform)

• Versicherung (numerische Integration von Versicherungspolicen in Was-wäre-wenn-Szenarien zur Berechnung der erwarteten Policenverluste)

• Logistik (Optimierung der Konsolidierung von Transportwegen)

• Signalverarbeitung

Kalkül – Der integrale Teil – wird direkt in CS als Grundlage für das Nachdenken über die Summierung verwendet. Wenn Sie einen Teil von Knuths Abschnitt „Konkrete Mathematik“ zur Summierung durcharbeiten, werden Sie schnell die für die Analysis üblichen Konventionen erkennen: Wenn Sie einige der fortlaufenden Fälle verstehen, können Sie die diskreten Konventionen berücksichtigen.

Viele der Verwendungszwecke In Ihrer CS-Studie geht es um Programmiersysteme, die Veränderungen überwachen oder in einigen Fällen versuchen, die Zukunft vorherzusagen. Die Mathematik um diese Systeme basiert auf Differentialgleichungen und linearer Algebra, und Differentialgleichungen sind … Kalkül. Es gibt Lehrer wie Gibert Strang, der sich dafür einsetzt, schneller in den Teil der Differentialgleichungen einzusteigen, aber es ist immer noch eine Teilmenge des Kalküls. Wenn die Änderung von der Änderung in einem System abhängt, beginnt sie auf nicht intuitive und sehr intuitive Weise instabil (und stabil) zu werden Um zu verstehen, warum sich Ihr vernünftiges lineares System nichtlinear verhält, benötigen Sie entweder die Werkzeuge der Analysis oder Sie müssen sie für Ihren Problembereich neu erfinden.

Und schließlich häufig CS erfordert das Lesen und Verstehen der Arbeit anderer, und Kalkül ist die erste Begegnung mit vielen gemeinsamen Vokabeln, Konventionen und Geschichten.

Kommentare

• " Viele der Anwendungen Ihrer CS-Studie umfassen Programmiersysteme, die Änderungen überwachen. oder versuchen Sie in einigen Fällen, die Zukunft vorherzusagen. " – Ich glaube nicht, dass dies repräsentativ für moust CS-Studiengänge ist. '