Jakie są dobre wzory matematyczne do programowania? [Zamknięte]

19

Jakie są dość powszechne wzory matematyczne dowiedziałeś się, że pomógł Ci pisać lepsze algorytmy i stać się lepszym programistą?

Przykład: Dowiedziałem się o ecludian wzoru dystans: sqrt((x1-x2)^2+(y1-y2)^2)co pomogło mi zrozumieć, jak znaleźć podobne przedmioty porównując 2 czynniki.

GSto
źródło
2
Nie sądzę, że jest to euklidesowa formuła odległości.
Greg Hewgill
@Larry @Greg edytowany.
GSto
haha jak o sekwencji fibo ... dobre dla benchmarkingu
aggietech
1
Data ukończenia = (Szacowana data + pozostała liczba dni / 2) ^ (Czas w pracy / Czas w domu) * Liczba darmowych pizzy
Skizz
7
Może okazać się interesujące wiedzieć, że jeśli wystarczy porównać dystansach, można pominąć ten sqrtkrok. To może mieć znaczenie dla ciasnej pętli wewnętrznej.

Odpowiedzi:

16

Znając potęgi 2 jest przydatny, zwłaszcza gdy mamy do czynienia z działalnością bitowe niskopoziomowych.

AShelly
źródło
+1 - Konieczna jest konwersja do iz baz 2, 16, 10 i 8.
mouviciel
2
Nie jestem pewien bazy-8, ale zgadzam się z 2,16 i 10 konwersje. Powinieneś być w stanie to zrobić w rozsądnym terminie, ale niekoniecznie od razu.
Incognito
Mój jedyny nauczyciel jest zwierzęciem hex. Przekształca się w jego śmieszne liczby, a ja byłem dla niego TA przez około rok, klasa była zawsze pod wrażeniem, tak jak ja.
Chris
Nienawidzę podstawy 8 :)
1
Z makrami, teksty stałe i bitfields we współczesnych językach, w jakich przypadkach ludzie muszą wiedzieć uprawnień 2, które są fundamentalnie magiczne numery .. setsockopt(...SO_KEEPALIVE..)jest dość dużo łatwiejsze do odczytu lub zapisu niżsetsockopt(...16...)
JBRWilkinson
15

Boole'a już wspomniano, ale chciałem przedstawić kilka praktycznych przykładów.

Boole'a przydaje się bardzo często podczas pracy z złożonych wyrażeń logicznych (w ifsprawozdaniu na przykład).

Kilka użytecznych wyrażeń i prawa:

rozdzielność

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

A | (B i C) = (A | B) i (A | C)

Następnym razem natkniesz się na takie wyrażenie:

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

Można łatwo kurczyć go na adres:

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

Negacja i prawa De Morgana

! (! A) = A

! (A i B) =! A | !B

! (A | B) =! A i! B

Powiedzmy, że masz takie oświadczenie:

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

i musisz zbudować coś przeciwnego. Pisanie:

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

działałoby, ale nie wygląda tak fajnie, jak ten odpowiednik:

if(A | B | C) {...}
serg
źródło
2
Problem z zrobieniem tego polega na tym, czy są to rzeczywiste reguły biznesowe, ponieważ mają one tendencję do ZMIANY. Jeśli tak, musisz zrekonstruować oryginalne wyrażenie, aby je zmienić, a następnie ponownie zoptymalizować. Opiekunowie zwykle narzekają podczas tego.
I tu może pomóc mapa Karnaugh. Działa dobrze tylko na 4 flagach logicznych jednocześnie, ale jeśli potrzebujesz więcej - powodzenia!
Job
3
+1 za prawo De Morgana. Dziwi mnie, jak niewiele osób nauczyło się tego i wie, jak go stosować.
Fortyrunner,
Zapomniałeś ten jeden: (P -> Q) <=> (!P | Q). Używam go cały czas, ponieważ bardzo niewiele środowisk oferuje operator logicznej implikacji, jest to bardzo przydatna równoważność ograniczeń SQL CHECK.
mu jest za krótki
Prawo Karnaugh i De Morgana jest czymś, czego zwykle uczy się używania w klasach elektrotechniki, ale nie w klasach inżynierii komputerowej. Co jest dziwne, ponieważ aplikacje można znaleźć w tym drugim, jak praktyczne zastosowanie wspomnianego powyżej prawa De Morgana.
Spoike
9

Z mojego doświadczenia wynika, że ​​formuły matematyczne są używane do bardzo szczegółowych obliczeń, które mogą, ale nie muszą dotyczyć twojego projektu.

Jeśli musisz coś obliczyć, zwykle w bibliotece lub przykładowym kodzie źródłowym jest funkcja, która może to obliczyć. Na przykład funkcja PMT () programu Excel, która oblicza płatności wymagane do spłaty zadłużenia w wysokości X% w okresach Y. Czy naprawdę chcesz wiedzieć, jak to oblicza, czy wystarczy wywołać wbudowany?

W ciągu ostatnich 10 lat nie sądzę, że musiałem używać czegokolwiek z biblioteki Math innej niż Ceil (), Min () i Max (), co pokazuje, że nawet jeśli komputery zostały opracowane w celu rozwiązania problemów matematycznych , dziś powszechnym zastosowaniem jest podejmowanie decyzji dotyczących przepływu danych.

Weźmy na przykład Facebooka, który ma ogromną ilość kodu. Prawdopodobnie gdzieś tam jest trochę matematyki, ale podejrzewam, że głównie w API Crypto, które prawdopodobnie jest biblioteką systemową. Ale dostęp do bazy danych, decyzje autoryzacyjne, tworzenie stron i routing informacji prawdopodobnie nie używają dużo matematyki.

Tak, są rynki, które potrzebują dużo matematyki - finanse, fizyka, inżynieria - ale w tych branżach twoją podstawową dyscypliną jest matematyka / ekonomia, fizyka, inżynieria itp., Więc twoje pytania brzmiałyby: „jak napisać wzór f (x) w języku Y? ”

Lepszym wykorzystaniem twojego czasu, IMO, byłoby zbadanie algorytmów (w tym notacji Big O) i wzorców projektowych.

JBRWilkinson
źródło
1
+1, ponieważ wydaje się to rozsądnym stwierdzeniem - nie ma konkretnej formuły, którą powinieneś znać, ale koncepcja złożoności algorytmicznej (notacja Big O) jest bardzo ważna.
Michael H.
Dużo matematyki ... Decyduje, które reklamy Cię zepsuć.
Zgadzam się, że potrzebna matematyka jest na ogół dość niska, chociaż moje doświadczenie nie jest tak niskie jak twoje - co jakiś czas używam elementów graficznych do wyzwalania.
Loren Pechtel,
7

Nie ma formuły, która mogłaby uczynić cię lepszym programistą.

Umiejętności matematyczne mogą sprawić, że będziesz lepszym programistą:

  • Metoda naukowa - matematyka / naukowy sposób myślenia i rozwiązywania problemów
  • Abstrakcja - umiejętność rozpoznawania abstrakcji i wzorów
  • Dziedziczenie - ponowne wykorzystanie istniejącej pracy / metod do rozwiązywania nowych problemów
  • Doświadczenie - zrozumienie zestawu problemów i rozwiązań
Branimir
źródło
-1, mężczyzna zapytał o przydatne FORMUŁY MATOWE. Nie mogę uwierzyć, że ta odpowiedź została w ogóle oceniona.
Jas
6

Podstawowe formuły statystyk są dobrze znane. Użyłem regresji liniowej co najmniej kilka razy.

Uwaga do siebie - myślę o nazwie
źródło
6

Chciałbym wspomnieć o seriach Taylora, które są dość przydatne do szybkiego przybliżania „cięższych” funkcji. Na przykład sin(x)około 0 można przybliżać za pomocą x-(x*x*x/6).

Ogólnie rzecz biorąc, pomysł, że istnieją sprytne sposoby szybkiego przybliżenia rzeczy, zamiast liczenia ich do ostatniej znaczącej cyfry (chociaż w przypadku funkcji elementarnych większość współczesnych procesorów zawiera szybkie implementacje przewodowe, więc użycie Taylora do przybliżenia grzechu może nie być tak znaczące przyrost prędkości).

Joonas Pulakka
źródło
3

Prawa De Morgana dotyczące przekształcania logiki „i” i „lub” w stosunku do negacji oraz kilka powiązanych bardziej elementarnych ciekawostek na temat logiki boolowskiej (takich jak podwójna negacja).

Peter Eisentraut
źródło
2

Reguła trzech (rodzaj mnożenia krzyżowego)

+1 za podstawowe formuły statystyk.

Widziałem wielu facetów mających trudności z zastosowaniem tej prostej reguły do ​​kodu podstawowego.

Pagotti
źródło
+1 za pomnożenie krzyżowe. W niektórych programach, które są podatne na problemy z przepełnieniem liczb całkowitych, mnożenie krzyżowe służy do sprawdzenia, czy wyniki się nie przepełniają.
rwong
2
Nic takiego. Powinno to być zakorzenione w głowie absolwenta szkoły średniej, który chce studiować CS.
Job
@Job: W teoretycznego świata, to prawda!
Pagotti
2

Prawo Cosinusów , bardzo ważne dla wielu problemów geometrycznych,

alternatywny tekst

szczególnie określenie kąta.


źródło
czym jest gamma w tym równaniu?
Matt Ellen,
1
@Matt Ellen: kąt boku w poprzek strony C (IOW, kąt między A i B)
Lie Ryan,
2
I oczywiście szczególny przypadek dla prostokątnych trójkątów:a^2 + b^2 = c^2
Uwaga dla siebie - wymyśl nazwę
2

Programowanie jest bardzo szeroką dziedziną. Formuła matematyczna zależy od tego, w jakim obszarze programowania jesteś. Jeśli interesujesz się grafiką, programowaniem gier, musisz znać więcej trygonometrii, geometrii. Programowanie gier można dalej podzielić na takie obszary, jak fizyka, rendering, shader ... i lista jest długa. Więc jeśli jesteś ekspertem od symulacji fizyki, powinieneś wiedzieć rzeczy związane z fizyką.
Jeśli jesteś w bezpieczeństwie, musisz być ekspertem w dziedzinie teorii liczb.
Ogólnie rzecz biorąc, możesz wybrać kombinację tych, i które zawsze są twoje zainteresowania. Uczenie się nigdy nie boli.


źródło
2

Metody sprawdzania

W szczególności te, których użyłem z względną częstotliwością:

Jest ich więcej i użyłem wielu z nich w tym czy innym momencie, ale są to 3, które mogę sobie przypomnieć, na pierwszy rzut oka. Są również nieskończenie pomocne, jeśli możesz mieć na uwadze ich zamiary podczas pisania testów jednostkowych lub integracyjnych.

Steven Evers
źródło
2

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

Twierdzenie Master jest dobrze znane z programowania. Pozwala rozwiązać relacje rekurencyjne, które mogą pomóc Ci znaleźć złożoność algorytmów rekurencyjnych. Jest to szczególnie ważne przy pisaniu algorytmu typu „dziel i rządź”. Z grubsza mówiąc, możesz użyć twierdzenia głównego, aby uzyskać złożoność, jeśli znasz złożoność każdego „kroku” i współczynnik rozgałęzienia.

Kurtis
źródło
1
dlaczego warto wiedzieć o programowaniu?
Matt Ellen,
@MattEllen: Pozwala rozwiązać relacje rekurencyjne, które mogą pomóc Ci znaleźć złożoność algorytmów rekurencyjnych. Jest to szczególnie ważne przy pisaniu algorytmu typu „dziel i rządź”. Z grubsza mówiąc, możesz użyć twierdzenia głównego, aby uzyskać złożoność, jeśli znasz złożoność każdego „kroku” i współczynnik rozgałęzienia.
Tikhon Jelvis
1
  • algebra
  • trygonometria
  • Wektor (działanie macierzowe)
  • rachunek różniczkowy
  • [różne interpolacje i ich pochodne]
  • [powierzchnie, NURBS]

(te w nawiasach są bardziej „stosowane”)

Trudno jest podać ogólne kierunki, ponieważ silnie zależy to od dziedziny, w której się znajdujesz. Ale powyższe obejmuje podstawy dość wielu stopni inżynieryjnych. Pamiętaj, że te kategorie często się pokrywają (trygonometria + operacje na macierzach, rachunek różniczkowy + operacje na macierzach itd.).

Zawsze mam w pobliżu podręcznik matematyki. Często się czegoś nie ma i pomaga to zorganizować w sposób zorganizowany.

Wieża
źródło
1

Znajomość algebry boolowskiej bardzo pomaga. To powstrzymuje cię przed pisaniem kodu jak

if (x < 10)
    return true;
else
    return false;
fredoverflow
źródło
Nie jestem do końca pewien, czy rozumiem, w jaki sposób algebra boolowska pomaga zapobiec pisaniu tego przez użytkownika? Czy możesz zaproponować, co użytkownik powinien tam pisać? (Przypuszczam, że zwrot x <10; ale mogę się mylić.)
Chris
1
Masz rację - powinien być zwrot x <10. Pomyśl o tym w ten sposób. Ocena (x <10) zwróci wynik logiczny. Instrukcja if następnie dzieli się na [jeśli x jest rzeczywiście mniejszy niż 10], jeśli (prawda) zwraca true; lub [gdy x jest większa lub równa 10] Jeżeli (fałsz) ... inny zwrot fałszywe;
Eric Olsson,
2
(X <10) może oddzielać dwa przypadki biznesowe. Dzięki pełnemu formularzowi możesz zrobić coś więcej niż tylko zwracanie wartości, co w trybie konserwacji jest bardzo miłe, ponieważ możesz ograniczyć zmiany do minimum
1

W przypadku problemów z optymalizacją dobrze jest zrozumieć prawdopodobieństwo dziennika. Na przykład, jeśli próbujesz zminimalizować sumę kwadratów, to to samo, co maksymalizacja dziennika prawdopodobieństwa, ponieważ (z grubsza mówiąc)

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

Innymi ulubionymi w dziedzinie strojenia wydajności są rozkłady dwumianowe i beta. Są bardzo proste do obliczenia.

Jeśli weźmiesz 10 losowych próbek stanu programu i jest on w pewnym stanie przez F = 40% czasu, to jest to jak eksperyment rzucania monetą z nieuczciwą monetą. Liczba wyświetleń w tym stanie to rozkład dwumianowy ze średnią 10 * 0,4 = 4 i standardowym odchyleniem sqrt (10 * 0,4 * 0,6) = sqrt (2,4) = 1,55.

Z drugiej strony, jeśli weźmiesz 10 próbek i zobaczysz je w tym stanie na 4 próbkach, co to mówi o tym, jak duże jest F? Możliwe wyniki to 0, 1, 2, 3, 4, ..., 9, 10. To 11 możliwości, a możliwość, którą widziałeś (4), to piąta. Weź więc 11 jednolitych (0,1) liczb losowych i posortuj je. Rozkład piątego to rozkład F, rozkład Beta. Jego tryb jest 4/10. Jego średnia wynosi 5/11. Jego wariancja wynosi 5 * 6 / (11 ^ 2 * 12) = 0,021, a odchylenie standardowe = 0,144.

Wiele osób uważa, że ​​potrzebna jest duża liczba próbek, aby zlokalizować problemy z wydajnością oprogramowania i uniknąć znalezienia fałszywych. Te rozkłady pokazują, że niewielka liczba próbek może wiele powiedzieć o ich koszcie.

Mike Dunlavey
źródło
0

Może to być nieco proste, ale G=(V,E)warto o tym pamiętać. Innymi słowy, wykres to zestaw wierzchołków i krawędzi. Wykresy są bardzo przydatne do reprezentowania wielu rzeczy.

Jason Baker
źródło