Was sind gute mathematische Formeln für die Programmierung? [geschlossen]

19

Welche etwas gebräuchlichen mathematischen Formeln haben Sie gelernt, um bessere Algorithmen zu schreiben und ein besserer Programmierer zu werden?

Beispiel: Ich habe die ecludian Distanzformel kennengelernt, sqrt((x1-x2)^2+(y1-y2)^2)die mir durch den Vergleich von 2 Faktoren hilft, ähnliche Objekte zu finden.

learning math algorithms GSto
quelle
2
Ich glaube nicht, dass das die euklidische Distanzformel ist.
Greg Hewgill
@Larry @Greg bearbeitet.
GSto
haha wie wäre es mit der Fibo-Sequenz ... gut für Benchmarking
aggietech
1
Fertigstellungstermin = (Voraussichtliches Datum + Anzahl der verbleibenden Tage / 2) ^ (Zeit bei der Arbeit / Zeit zu Hause) * Anzahl der kostenlosen Pizzas
Skizz
7
Vielleicht finden Sie es interessant zu wissen, dass Sie den Schritt überspringen können , wenn Sie nur Entfernungen vergleichen müssen sqrt. Für eine enge innere Schleife könnte das von Bedeutung sein.

Antworten:

16

Es ist praktisch, die Potenzen von 2 zu kennen, insbesondere wenn es sich um bitweise Operationen auf niedriger Ebene handelt.

Ahelly
quelle
+1 - In der Lage zu sein, zu und von den Basen 2, 16, 10 und 8 zu konvertieren, ist ein Muss.
mouviciel
2
Ich bin mir nicht sicher, ob die Basis 8 stimmt, aber ich bin mit 2,16 und 10 Conversions einverstanden. Sie sollten in der Lage sein, dies in einem angemessenen Zeitraum, jedoch nicht unbedingt sofort, zu tun.
Inkognito
Mein einziger Lehrer ist ein Hex-Tier. Konvertiert in seinem Kopf lächerliche Zahlen und ich war ein TA für ihn für ein Jahr oder so, die Klasse war immer beeindruckt, wie ich war.
Chris
Ich hasse Basis 8 :)
1
Mit Hilfe von Makros, Aufzählungen und Bitfelder in modernen Sprachen, in welchen Fällen brauchen Menschen Potenzen von 2 zu wissen, was im Grunde magische Zahlen sind .. setsockopt(...SO_KEEPALIVE..)ist ziemlich viel leichter zu lesen oder zu schreiben , alssetsockopt(...16...)
JBRWilkinson
15

Die Boolesche Algebra wurde bereits erwähnt, aber ich wollte einige praktische Beispiele nennen.

Boolesche Algebra ist sehr oft nützlich, wenn Sie mit komplexen booleschen Ausdrücken arbeiten ( ifz. B. in Anweisungen).

Paar nützliche Ausdrücke und Gesetze:

Verteilungsfähigkeit

A & (B | C) = (A & B) | (A & C)

A | (B & C) = (A | B) & (A | C)

Also, wenn Sie das nächste Mal auf einen solchen Ausdruck stoßen:

if((A || B) && (A || C) && (A || D) && (A || E)) { ... }

Sie können es leicht verkleinern auf:

if(A || (B && C && D && E)) { ... }

Verneinung und De Morgans Gesetz

! (! A) = A

! (A & B) =! A | ! B

! (A | B) =! A &! B

Nehmen wir an, Sie haben eine solche Aussage:

if(!A && !B && !C) {..}

und Sie müssen das Gegenteil davon bauen. Schreiben:

if(!(!A && !B && !C)) {...}

würde funktionieren, sieht aber nicht so cool aus wie dieses Äquivalent:

if(A | B | C) {...}
serg
quelle
2
Das Problem dabei ist, ob dies tatsächliche Geschäftsregeln sind, da diese dazu neigen, sich zu ändern. In diesem Fall müssen Sie den ursprünglichen Ausdruck rekonstruieren, um ihn zu ändern, und ihn dann erneut optimieren. Maintainer neigen dazu, dabei zu meckern.
Und hier kann eine Karnaugh-Karte helfen. Es funktioniert nur mit bis zu 4 Booleschen Flags gleichzeitig, aber wenn Sie mehr brauchen - viel Glück!
Job
3
+1 für De Morgans Gesetz. Ich bin erstaunt darüber, wie wenige Leute es gelernt haben und wissen, wie man es anwendet.
Fortyrunner
Sie haben vergessen , diese ein: (P -> Q) <=> (!P | Q). Ich benutze es die ganze Zeit, da nur sehr wenige Umgebungen einen logischen Implikationsoperator bieten. Dies ist eine sehr praktische Entsprechung für SQL CHECK-Einschränkungen.
mu ist zu kurz
Das Gesetz von Karnaugh und De Morgan ist etwas, das Sie normalerweise in Elektrotechnikkursen lernen, aber nicht in Computerkursen. Was seltsam ist, weil Anwendungen in letzteren zu finden sind, wie die praktische Anwendung des oben erwähnten Gesetzes von De Morgan.
Spoike
9

Nach meiner Erfahrung werden mathematische Formeln für ganz bestimmte Berechnungen verwendet, die möglicherweise für Ihr Projekt gelten oder nicht.

Wenn Sie etwas berechnen müssen, gibt es normalerweise eine Funktion in einer Bibliothek oder einem Beispielquellcode, die es für Sie berechnen kann. Zum Beispiel die Excel-Funktion PMT (), mit der die Zahlungen berechnet werden, die für die Rückzahlung einer Forderung in Höhe von X% über Y Perioden erforderlich sind. Wollen Sie wirklich wissen, wie es berechnet wird, oder reicht es aus, nur das eingebaute aufzurufen?

In den letzten 10 Jahren brauchte ich wohl nichts anderes aus der Mathematikbibliothek als Ceil (), Min () und Max (), was zeigt, dass Computer entwickelt wurden, um mathematikbasierte Probleme zu lösen Heute wird häufig über den Datenfluss entschieden.

Nehmen wir zum Beispiel Facebook, das eine enorme Menge an Code hat. Da ist wahrscheinlich irgendwo etwas Mathematik drin, aber ich vermute hauptsächlich in der Crypto-API, die wahrscheinlich eine Systembibliothek ist. Aber der Datenbankzugriff, die Autorisierungsentscheidungen, der Seitenaufbau und das Weiterleiten von Informationen verbrauchen wahrscheinlich nicht viel Mathematik.

Ja, es gibt Märkte, in denen viel Mathematik benötigt wird - Finanzen, Physik, Ingenieurwesen -, aber in diesen Branchen ist Ihre Hauptdisziplin eher Mathematik / Wirtschaft, Physik, Ingenieurwesen usw. Ihre Frage lautet also: Wie kann ich schreiben? Formel f (x) in Sprache Y? '

Eine bessere Nutzung Ihrer Zeit, IMO, wäre die Untersuchung von Algorithmen (einschließlich Big-O-Notation) und Entwurfsmustern.

JBRWilkinson
quelle
1
+1, weil es sich um eine vernünftige Aussage handelt - es gibt keine bestimmte Formel, die Sie kennen sollten, aber das Konzept der algorithmischen Komplexität (Big O-Notation) ist sehr wichtig.
Michael H.
Jede Menge Mathe ... Entscheiden Sie, mit welchen Anzeigen Sie Probleme haben.
Ich bin damit einverstanden, dass der benötigte Rechenaufwand im Allgemeinen recht gering ist, obwohl meine Erfahrung nicht ganz so gering ist wie Ihre - ich verwende regelmäßig Trigger-Elemente in Grafiken.
Loren Pechtel
7

Es gibt keine Formel, die Sie zu einem besseren Programmierer machen könnte.

Mathematische Fähigkeiten können Sie zu einem besseren Programmierer machen:

  • Wissenschaftliche Methode - mathematisch / naturwissenschaftliche Denkweise und Problemlösung
  • Abstraktion - Fähigkeit, Abstraktionen und Muster zu erkennen
  • Vererbung - Wiederverwendung vorhandener Arbeiten / Methoden zur Lösung neuer Probleme
  • Erfahrung - eine Reihe von Problemen und Lösungen verstehen
Branimir
quelle
-1, fragte der Mann nach nützlichen MATH-FORMELN. Ich kann nicht glauben, dass diese Antwort überhaupt positiv bewertet wurde.
Jas
6

Grundlegende Statistikformeln sind gut zu wissen. Ich habe mindestens ein paar Mal lineare Regression verwendet .

Notiz an mich selbst - denke an einen Namen
quelle
6

Ich möchte Taylor-Reihen erwähnen , die sehr nützlich sind, um schnelle Annäherungen an "schwerere" Funktionen zu erhalten. Zum Beispiel sin(x)kann mit 0 angenähert werden x-(x*x*x/6).

Im Allgemeinen ist die Idee, dass es clevere Möglichkeiten gibt, Dinge schnell zu approximieren, anstatt sie auf die letzte signifikante Ziffer zu berechnen (obwohl für elementare Funktionen die meisten modernen Prozessoren schnelle, festverdrahtete Implementierungen enthalten, die Taylor zur Approximation der Sünde verwenden, möglicherweise nicht so bedeutend Geschwindigkeitsgewinn).

Joonas Pulakka
quelle
3

De Morgans Gesetze über das Transformieren von Booleschen "und" und "oder" in Bezug auf Negationen und einige verwandte, elementarere Leckerbissen über die Boolesche Logik (wie die doppelte Negation).

Peter Eisentraut
quelle
2

Dreierregel (Art der Kreuzmultiplikation)

+1 für grundlegende Statistikformeln.

Ich habe viele Leute gesehen, die Schwierigkeiten hatten, diese einfache Regel auf Basiscode anzuwenden.

Pagotti
quelle
+1 für Kreuzmultiplikation. In einigen Programmen, bei denen es zu Problemen mit dem Überlauf ganzer Zahlen kommt, wird durch Cross-Multiplikation überprüft, ob die Ergebnisse nicht überlaufen.
rwong
2
Keine große Sache. Dies sollte im Kopf eines Abiturienten verankert sein, der CS studieren möchte.
Job
@Job: In einer theoretischen Welt ist das wahr!
Pagotti
2

Gesetz des Kosinus , sehr wichtig für viele geometrische Probleme,

Alt-Text

insbesondere Winkelbestimmung.


quelle
Was ist Gamma in dieser Gleichung?
Matt Ellen
1
@ Matt Ellen: der Winkel der Seite über Seite C (IOW, der Winkel zwischen A und B)
Lie Ryan
2
Und natürlich ein Sonderfall für rechtwinklige Dreiecke:a^2 + b^2 = c^2
Notiz an sich selbst - denken Sie an einen Namen
2

Die Programmierung ist ein sehr weites Feld. Die mathematische Formel hängt davon ab, in welchem ​​Bereich Sie programmieren. Wenn Sie sich mit Grafik und Spielprogrammierung beschäftigen, müssen Sie mehr über Trigonometrie und Geometrie wissen. Spielprogrammierung kann weiter in Bereiche wie Physik, Rendering, Shader eingeteilt werden und die Liste geht weiter. Wenn Sie ein Experte für Physiksimulation sind, sollten Sie sich mit Physik auskennen.
Wenn Sie in Sicherheit sind, müssen Sie ein Zahlentheorie-Experte sein.
Im Allgemeinen können Sie eine Kombination davon wählen, und je nachdem, welches Interesse Sie haben. Lernen tut nie weh.


quelle
2

Methoden des Beweises

Vor allem diejenigen, die ich mit relativer Häufigkeit verwendet habe:

Es gibt noch mehr, und ich habe viele von ihnen an der einen oder anderen Stelle verwendet, aber dies sind die 3, an die ich mich auf einen Blick erinnern kann. Sie sind auch unendlich hilfreich, wenn Sie beim Schreiben von Unit- oder Integrationstests ihre Absicht berücksichtigen können.

Steven Evers
quelle
2

T (n) = aT (n / b) + f (n), a> = 1, b> 1

Der Hauptsatz ist für die Programmierung gut zu wissen. Damit können Sie Wiederholungsrelationen lösen, mit deren Hilfe Sie die Komplexität rekursiver Algorithmen ermitteln können. Dies ist besonders wichtig, wenn Sie einen Divide-and-Conquer-Algorithmus schreiben. Grob gesagt können Sie den Hauptsatz verwenden, um die Komplexität zu ermitteln, wenn Sie die Komplexität jedes "Schritts" und den Verzweigungsfaktor kennen.

Kurtis
quelle
1
warum ist es gut zu wissen, für die Programmierung?
Matt Ellen
@MattEllen: Damit können Sie Wiederholungsrelationen lösen, mit deren Hilfe Sie die Komplexität rekursiver Algorithmen ermitteln können. Dies ist besonders wichtig, wenn Sie einen Divide-and-Conquer-Algorithmus schreiben. Grob gesagt können Sie den Hauptsatz verwenden, um die Komplexität zu ermitteln, wenn Sie die Komplexität jedes "Schritts" und den Verzweigungsfaktor kennen.
Tikhon Jelvis
1
  • Algebra
  • Trigonometrie
  • Vektor (Matrixoperationen)
  • Infinitesimalrechnung
  • [verschiedene Interpolationen und ihre Ableitungen]
  • [Oberflächen, NURBS]

(die in Klammern sind eher eine "angewandte" Art)

Es ist schwierig, allgemeine Anweisungen zu geben, da dies stark vom Fachgebiet abhängt, in dem Sie tätig sind. Das oben Gesagte deckt jedoch die Grundlagen vieler Ingenieurabschlüsse ab. Allerdings überlappen sich diese Kategorien häufig (Trigonometrie + Matrixoperationen, Kalkül + Matrixoperationen usw.).

Ich habe immer ein mathematisches Handbuch in der Nähe. Man ist sich oft unsicher und es hilft, wenn man etwas organisiert präsentiert.

Turm
quelle
1

Die Kenntnis der Booleschen Algebra ist sehr hilfreich. Es hält Sie davon ab, Code zu schreiben

if (x < 10)
    return true;
else
    return false;
fredoverflow
quelle
Ich bin mir nicht ganz sicher, ob ich verstehe, wie die Boolesche Algebra einen Benutzer daran hindert, das zu schreiben. Können Sie vorschlagen, was der Benutzer dort schreiben soll? (Ich würde davon ausgehen, dass die Rückgabe x <10 ist, aber möglicherweise irrtümlich.)
Chris
1
Sie haben recht - es sollte return x <10 sein. Denk darüber so. Das Auswerten (x <10) gibt ein boolesches Ergebnis zurück. Die if-Anweisung zerfällt dann in [wenn x tatsächlich kleiner als 10 ist], wenn (true) true zurückgibt. oder [wenn x größer oder gleich 10 ist] if (false) ... else return false;
Eric Olsson
2
Das (x <10) kann zwei Geschäftsfälle trennen. Mit dem ausführlichen Formular können Sie mehr als nur Werte zurückgeben, was im Wartungsmodus sehr
1

Bei Optimierungsproblemen ist es gut, die Log-Wahrscheinlichkeit zu verstehen. Wenn Sie beispielsweise versuchen, eine Quadratsumme zu minimieren, entspricht dies der Maximierung des Wahrscheinlichkeitsprotokolls, da (grob gesagt)

log( Product( exp( -(x[i]-mean)^2 )) )
  =
  - Sum( (x[i]-mean)^2 )

Andere Favoriten im Bereich der Leistungsoptimierung sind Binomial- und Beta-Distributionen. Sie sind sehr einfach zu berechnen.

Wenn Sie 10 zufällige Stichproben des Status eines Programms nehmen und es in einer bestimmten Bedingung für F = 40% der Zeit ist, dann ist es wie ein Münzwurfexperiment mit einer unfairen Münze. Die Häufigkeit, mit der Sie es in diesem Zustand sehen, ist eine Binomialverteilung mit einem Mittelwert von 10 * 0,4 = 4 und einer Standardabweichung von sqrt (10 * 0,4 * 0,6) = sqrt (2,4) = 1,55.

Auf der anderen Seite, wenn Sie 10 Proben nehmen und es zufällig bei 4 Proben in diesem Zustand sehen, was sagt Ihnen das darüber aus, wie groß F ist? Die möglichen Ergebnisse sind 0, 1, 2, 3, 4, ..., 9, 10. Das sind 11 Möglichkeiten, und die Möglichkeit, die Sie gesehen haben (4), ist die 5. Möglichkeit. Also nimm 11 einheitliche (0,1) Zufallszahlen und sortiere sie. Die Verteilung der 5. ist die Verteilung von F, einer Beta-Verteilung. Sein Modus ist 4/10. Sein Mittelwert ist 5/11. Seine Varianz beträgt 5 * 6 / (11 ^ 2 * 12) = 0,021 und die Standardabweichung = 0,144.

Viele Leute denken, dass eine große Anzahl von Beispielen erforderlich ist, um Software-Leistungsprobleme zu lokalisieren und falsche zu vermeiden. Diese Verteilungen zeigen, dass eine kleine Anzahl von Proben viel über ihre Kosten aussagen kann.

Mike Dunlavey
quelle
0

Dies mag ein bisschen einfach sein, ist aber G=(V,E)gut zu bedenken. Mit anderen Worten, ein Graph ist eine Menge von Eckpunkten und Kanten. Diagramme sind einfach so nützlich, um viele Dinge darzustellen.

Jason Baker
quelle