11 уравнений, которые должен знать каждый уважающий себя инженер!



Доброго вечера всем нашим читателям!

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

Биномиальный коэффициент




Уравнение биномиального коэффициента позволяет построить треугольник Паскаля и дает коэффициенты для Биномиальной теоремы. Эти идеи приписывают Паскалю, хотя некоторые моменты были известны уже в течении тысячелетий.

Весь список из 11 уравнений не содержит какого либо порядка, однако это выражение стоит непременно запомнить, потому что оно является центральным в комбинаторике, которая имеет влияние на многие области математики. Если Вы серьезно занимаетесь компьютерной наукой или сильно связанным с математикой программированием, то Вы непременно должны уметь им пользоваться и восстанавливать по памяти, даже если Вы пьяны, разбужены посреди ночи или находитесь под дулом пистолета.

Закон Деморгана


Логическая форма:




Форма множеств:




Понимать теорию множеств и булеву алгебру очень важно для нашей профессии. А логическая форма закона Деморгана позволит вам упрощать логические выражения.

Собственные векторы и Собственные значения




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

В последнее время линейная алгебра становится краеугольным камнем в том, что мы делаем в нашей профессии. Она активно используется в статистике, машинном обучении. Не стоит забывать и алгоритм PageRank (Google), который базируется на этом уравнении.

Лемма о накачке для регулярных языков




Ни один список предметов изучения компьютерной науки (Computer Science) не может быть полным без теории формальных языков и теории автоматов. Проблема состоит в том, что две последние теории кардинально отличаются от других областей математики в термине «выражение» (уравнение). Обязательно следует упомянуть «лемму о накачке».

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

Энтропия информации


Формула энтропии из теории информации Шеннона:



И, конечно, формула Константы Хайтина, которая связана с алгоритмической теорией информации и Колмогоровской сложностью:



Примечательно, что данная область имеет свои параллели в реальном мире (физика) в терминах термодинамической энтропии. Сет Ллойд показал некоторые интересные связи между вычислениями и физическим миром, включая энтропию и уравнение Больцмана.

Теорема Байеса




Из всех уравнений из списка, теорема Байеса может считаться наиболее узнаваемой, она может считаться главным детищем статистической революции, которая дала стремительный рост нашей индустрии. Она поднялась из небытия, чтобы использоваться в определении спама, задачах классификации, машинном обучении, data-mining'е и многом другом.

Малая теорема Ферма





Эти два уравнения Малой теоремы Ферма в сущности одно и то же уравнение, просто записанное в разных формах.

Эта красивая малая теорема втеории чисел может быть обощена и записана более лаконично с использованием функций Эйлера:



Эта идея крайне важна для понимания алгоритмов шифрования, таких как RSA и его замечательных результатов.

Естественное соединение




Естественное соединение, как и все соединения реляционной алгебры, — это композиция более общих операций: выборка (σ), Проекция (π), Декартово произведение (×), Разность множеств (-) и их объединение (∪). Естественное соединение это декартово произведение двух таблиц с выборкой одинаковых строк и удалением дубликатов.

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

Комбинатор неподвижной точки




Уже было упомянуто несколько «уравнений» теории естественных языков и теории автоматов. Поэтому не стоит обходить стороной и лямбда-исчисление. В данном конкретном случае — нетипизированное лямба-исчисление. И несмотря на то, что комбинатор неподвижной точки важен сам по себе, он хорошо известен благодаря Полу Грэму и его стартап-инкубатору Y-Combinator.

Комбинатор неподвижной точки позволяет реализовать анонимную рекурсию, которая является мощной техникой программирования. Кроме того, он также участвует в более глубоких теоретических аспектах компьютерной науки и логики, как например, комбинаторная логика.

O(N)


Некоторые могут возмутится, некоторые сказать, что это совсем не формула. Однако с этим понятием связано несколько интересных выражений, вот они:




И вот еще определение (lim sup) частичного предела последовательности:



В этом выражение inf — инфимум (infimum, точная нижняя грань) и sup — супремум (supremum, точная верхняя грань), сущности важные, если Вы имеете дела с решетками (теория множеств) и топологией.

И самое главное — O(N) это величина показывающая сложность алгоритмов!

Тождество Эйлера




Тождейство Эйлера — пожалуй одна из самых красивых формул математики.

Надо согласиться, что конкретно эта формула не имеет такого важного влияния на компьютерную науку, как другие. Однако если Вы действительно всерьез занимаетесь ей, то Вы также должны хорошо знать математику.

Кроме того, существует частный случай при θ = π (формула Эйлера):



Эти формулы используются в математике комплексный чисел, которые в свою очередь используются в анализе Фурье, который имеет некоторые применения в компьютерной науке.

Комментарии (0)

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.

Warning: Unknown: write failed: No space left on device (28) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php5) in Unknown on line 0