Какие хорошие математические формулы нужно знать для программирования? [закрыто]

19

Какие некоторые математические формулы, которые вы узнали, помогли вам написать лучшие алгоритмы и стать лучшим программистом?

Пример: я узнал о формуле эклюдского расстояния: sqrt((x1-x2)^2+(y1-y2)^2)которая помогла мне понять, как найти похожие объекты, сравнив 2 фактора.

GSto
источник
2
Я не думаю, что это евклидова формула расстояния.
Грег Хьюгилл
@Larry @Greg отредактировано.
до
хаха, как насчет последовательности
Фибоначчи
1
Дата завершения = (Предполагаемая дата + Количество оставшихся дней / 2) ^ (Время на работе / Время дома) * Количество бесплатных
пицц
7
Вам может быть интересно узнать, что если вам просто нужно сравнить расстояния, вы можете пропустить sqrtшаг. Для плотного внутреннего цикла это может иметь значение.

Ответы:

16

Знание степеней 2 удобно, особенно когда речь идет о битовых операциях низкого уровня.

AShelly
источник
+1 - Обязательно конвертировать в базы 2, 16, 10 и 8 и обратно.
Мувичиэль
2
Я не уверен насчет Base-8, но я согласен с 2,16 и 10 конверсиями. Вы должны быть в состоянии сделать это в разумные сроки, но не обязательно мгновенно.
Инкогнито
Мой единственный учитель - гексагон. Обращает в его голове смешные цифры, и я был для него ТА в течение года или около того, класс всегда был впечатлен, как и я.
Крис
Я ненавижу базу 8 :)
1
С макросами, перечислениями и битовыми полями на современных языках, в каких случаях людям нужно знать степени 2, которые являются по сути магическими числами ... setsockopt(...SO_KEEPALIVE..)гораздо легче читать или писать, чемsetsockopt(...16...)
JBRWilkinson
15

Булева алгебра уже упоминалась, но я хотел привести несколько практических примеров.

Булева алгебра очень часто пригодится, когда вы работаете со сложными логическими выражениями (например, в ifвыражениях).

Пара полезных выражений и законов:

Дистрибутивность

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

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

Поэтому в следующий раз вы наткнетесь на такое выражение:

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

Вы можете легко уменьшить его до:

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

Отрицание и закон де Моргана

! (! A) = A

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

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

Допустим, у вас есть такое утверждение:

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

и вам нужно построить противоположность этому. Письмо:

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

будет работать, но выглядит не так круто, как этот эквивалент:

if(A | B | C) {...}
Serg
источник
2
Проблема с этим заключается в том, если это реальные бизнес-правила в реальной жизни, поскольку они имеют тенденцию к ИЗМЕНЕНИЮ. Если это так, вам нужно восстановить исходное выражение, чтобы изменить его, а затем снова оптимизировать. При этом сопровождающие обычно ворчат.
И здесь карта Карно может помочь. Он работает только с 4 логическими флагами одновременно, но если вам нужно больше - удачи!
Работа
3
+1 за закон де Моргана. Я поражен тем, как мало людей, кажется, научили этому и знают, как его применять.
Fortyrunner
Вы забыли это одно: (P -> Q) <=> (!P | Q). Я использую его все время, так как очень немногие среды предлагают оператор логической импликации, это очень удобная эквивалентность для ограничений SQL CHECK.
мю слишком коротко
Закон Карно и де Моргана - это то, что вы обычно учите использовать на уроках электротехники, но не на уроках компьютерной инженерии. Что странно, потому что в последнем случае можно найти приложения, например, практическое использование закона де Моргана, упомянутого выше.
Спойк
9

По моему опыту, математические формулы используются для очень конкретных расчетов, которые могут или не могут применяться к вашему проекту.

Если вам нужно что-то вычислить, обычно в библиотеке или примере исходного кода есть функция, которая может рассчитать это для вас. Например, функция Excel PMT (), которая вычисляет платежи, необходимые для погашения долга, по X% за периоды Y. Вы действительно хотите знать, как он это вычисляет, или достаточно просто вызвать встроенный?

В последние 10 лет я не думаю, что мне нужно было использовать что-либо из библиотеки Math, кроме Ceil (), Min () и Max (), что показывает, что хотя компьютеры были разработаны для решения математических задач Сегодня общепринятым является принятие решений в отношении потока данных.

Взять, к примеру, Facebook, который имеет огромное количество кода. Возможно, где-то там есть математика, но я подозреваю, что в основном в Crypto API, который, вероятно, является системной библиотекой. Но доступ к базе данных, решения об авторизации, построение страниц и маршрутизация информации, вероятно, не используют много математики.

Да, есть рынки, которые нуждаются в большом количестве математики - финансы, физика, инженерия - но в этих отраслях вашей основной дисциплиной, скорее всего, будет математика / экономика, физика, инженерия и т. Д., Поэтому ваши вопросы будут: «Как я могу написать формула f (x) на языке Y? '

Лучше использовать ваше время, IMO, для изучения алгоритмов (включая обозначение Big O) и шаблонов проектирования.

JBRWilkinson
источник
1
+1, потому что это кажется разумным утверждением - вы не должны знать никакой конкретной формулы, но концепция алгоритмической сложности (обозначение Big O) очень важна.
Майкл Х.
Множество математики ... Решает, какие объявления вас обидеть.
Я согласен с тем, что необходимое количество математики, как правило, довольно низкое, хотя мой опыт не такой низкий, как у вас, - я периодически заканчиваю тем, что использую триггеры в графике.
Лорен Печтел
7

Нет формулы, которая может сделать вас лучшим программистом.

Навыки, связанные с математикой, могут сделать вас лучшим программистом:

  • Научный метод - математическое / научное мышление и решение проблем
  • Абстракция - способность распознавать абстракции и шаблоны
  • Наследование - повторное использование существующих работ / методов при решении новых задач
  • Опыт - понимание множества проблем и решений
Бранимир
источник
-1, человек спросил о полезных МАТУСНЫХ ФОРМУЛАХ. Я не могу поверить, что за этот ответ вообще проголосовали.
Jas
6

Основные статистические формулы хорошо знать. Я использовал линейную регрессию по крайней мере несколько раз.

Примечание для себя - придумай имя
источник
6

Я хотел бы упомянуть ряды Тейлора, которые весьма полезны для быстрого приближения к «более тяжелым» функциям. Например, sin(x)около 0 можно приблизить с помощью x-(x*x*x/6).

В общем, идея о том, что есть умные способы быстрого приближения вещей вместо вычисления их до последней значащей цифры (хотя для элементарных функций большинство современных процессоров содержат быстрые аппаратные реализации, поэтому использование Тейлора для приближения к греху может быть не столь значительным) увеличение скорости).

Joonas Pulakka
источник
3

Законы де Моргана о преобразовании логических «и» и «или» относительно отрицаний, и несколько связанных более элементарных лакомых слов о булевой логике (таких как двойное отрицание).

Питер Айзентраут
источник
2

Правило трех (тип перекрестного умножения)

+1 для основных статистических формул.

Я видел много ребят с трудом применять это простое правило на базовом коде.

Pagotti
источник
+1 для кросс-умножения. В некоторых программах, которые подвержены проблемам с целочисленным переполнением, перекрестное умножение используется для проверки того, что результаты не переполняются.
Rwong
2
Не так уж и важно. Это должно быть укоренено в голове выпускника средней школы, который хочет изучать CS.
Работа
@Job: В теоретическом мире это правда!
Паготти
2

Закон косинусов , очень важный для многих геометрических задач,

альтернативный текст

особенно определение угла.


источник
что такое гамма в этом уравнении?
Мэтт Эллен
1
@Matt Ellen: угол стороны поперек стороны C (IOW, угол между A и B)
Ли Райан
2
И, конечно же, особый случай для прямоугольных треугольников:a^2 + b^2 = c^2
Примечание для себя - придумайте имя
2

Программирование - очень широкая область. Математическая формула зависит от того, в какой области программирования вы находитесь. Если вы увлекаетесь графикой, программированием игр, вам необходимо знать больше тригонометрии, геометрии. Программирование игр может быть далее разделено на такие области, как физика, рендеринг, шейдер ... и этот список можно продолжить. Так что если вы эксперт по моделированию физики, то вы должны знать вещи, связанные с физикой.
Если вы в безопасности, вы должны быть экспертом по теории чисел.
В общем, вы можете пойти на комбинацию из них, и когда-либо ваш интерес. Обучение никогда не повредит.


источник
2

Методы доказательства

В частности, те, которые я использовал с относительной частотой:

Их больше, и я использовал многие из них в тот или иной момент, но я могу вспомнить те 3, которые я использовал с первого взгляда. Они также очень полезны, если вы помните их намерения при написании модульных или интеграционных тестов.

Стивен Эверс
источник
2

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

Основная теорема полезна для программирования. Это позволяет вам решать рекуррентные отношения, которые могут помочь вам найти сложность рекурсивных алгоритмов. Это особенно важно при написании алгоритма «разделяй и властвуй». Грубо говоря, вы можете использовать основную теорему, чтобы получить сложность, если вы знаете сложность каждого «шага» и фактор ветвления.

Куртис
источник
1
почему это полезно знать для программирования?
Мэтт Эллен
@MattEllen: Это позволяет вам решать рекуррентные отношения, которые могут помочь вам найти сложность рекурсивных алгоритмов. Это особенно важно при написании алгоритма «разделяй и властвуй». Грубо говоря, вы можете использовать основную теорему, чтобы получить сложность, если вы знаете сложность каждого «шага» и фактор ветвления.
Тихон Джелвис
1
  • алгебра
  • тригонометрия
  • вектор (матричные операции)
  • исчисление
  • [различные интерполяции и их производные]
  • [поверхности, NURBS]

(те, что в скобках, более «прикладные»)

Трудно дать общие указания, так как это сильно зависит от области, в которой вы находитесь. Но вышеизложенное охватывает основы довольно большого количества инженерных степеней. Имейте в виду, эти категории часто пересекаются (тригонометрия + матричные операции, исчисление + матричные операции и т. Д.).

У меня всегда есть математический справочник рядом. Часто кто-то не уверен в чем-то, и это помогает представить его организованно.

ладья
источник
1

Знание булевой алгебры очень помогает. Это мешает вам писать код как

if (x < 10)
    return true;
else
    return false;
fredoverflow
источник
Я не совсем уверен, что понимаю, как булева алгебра помогает предотвратить написание этого пользователем? Можете ли вы предложить, что пользователь должен писать там? (Я бы предположил, что возвращение х <10; но я могу ошибаться.)
Крис
1
Вы правы - должно быть возвращено х <10. Подумай об этом так. Оценка (x <10) вернет логический результат. Тогда оператор if разбивается на [если x действительно меньше 10], если (true) возвращает true; или [если x больше или равен 10] if (false) ... иначе возвращает false;
Эрик Олссон
2
(X <10) может разделять два бизнес-случая. С подробной формой вы можете делать больше, чем просто возвращать значения, что в режиме обслуживания очень удобно, так как вы можете сохранить изменения до минимума
1

Для задач оптимизации хорошо понимать логарифмическую вероятность. Например, если вы пытаетесь минимизировать сумму квадратов, это то же самое, что максимизировать логарифмическую вероятность, потому что (грубо говоря)

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

Другими фаворитами в области настройки производительности являются биномиальные и бета-версии. Их очень просто рассчитать.

Если вы берете 10 случайных выборок состояния программы, и она находится в определенном состоянии для F = 40% времени, то это похоже на эксперимент с подбрасыванием недобросовестной монеты. Количество раз, которое вы увидите в этом состоянии, является биномиальным распределением со средним значением 10 * 0,4 = 4 и стандартным отклонением sqrt (10 * 0,4 * 0,6) = sqrt (2,4) = 1,55.

С другой стороны, если вы берете 10 сэмплов и видите его в таком состоянии на 4 сэмплах, что это говорит вам о том, каков большой F? Возможные результаты: 0, 1, 2, 3, 4, ..., 9, 10. Это 11 вариантов, и вероятность, которую вы видели (4), является пятой. Итак, возьмем 11 одинаковых (0,1) случайных чисел и отсортируем их. Распределение 5-го является распределением F, бета-распределением. Его режим 4/10. Его среднее значение 5/11. Его дисперсия составляет 5 * 6 / (11 ^ 2 * 12) = 0,021, а стандартное отклонение = 0,144.

Многие люди думают, что большое количество образцов необходимо для выявления проблем с производительностью программного обеспечения и избегания поиска ложных. Эти распределения показывают, что небольшое количество образцов может многое рассказать об их стоимости.

Майк Данлавей
источник
0

Это может быть немного просто, но G=(V,E)стоит помнить. Другими словами, граф - это множество вершин и ребер. Графики просто полезны для представления многих вещей.

Джейсон Бейкер
источник