Как / когда исчисление используется в информатике?

96

Многие программы по информатике требуют двух или трех классов исчисления.

Мне интересно, как и когда исчисление используется в информатике? Содержание CS в области компьютерных наук имеет тенденцию фокусироваться на алгоритмах, операционных системах, структурах данных, искусственном интеллекте, разработке программного обеспечения и т. Д. Существуют ли моменты, когда Calculus полезен в этих или других областях компьютерных наук?

Виктор
источник
6
У нас нет строгой политики для вопросов списка, но есть общая неприязнь . Обратите внимание также на это и это обсуждение; Вы можете улучшить свой вопрос, чтобы избежать проблем, описанных там. Если вы не знаете, как улучшить свой вопрос, может быть, мы поможем вам в чате по информатике ?
Рафаэль
44
Вы, кажется, совершаете распространенную ошибку, полагая, что содержание каждого курса должно быть релевантным (для каждой карьеры). Иногда это просто обучение тому, как мыслить определенным образом.
Рафаэль
8
Вероятно, было бы полезно, если бы этот вопрос мог прояснить, спрашиваете ли вы только об использовании в рамках самой информатики или обо всех применениях для студентов, которые получают степень Comp Sci. По крайней мере, здесь, в США, очень большой процент выпускников Comp Sci становятся инженерами-программистами, разбросанными практически по всем мыслимым областям разработки. Многие из этих областей требуют понимания исчисления для различных целей. Не все выпускники CS будут использовать Calculus в своей работе, но многие наверняка будут (вероятно, больше, чем те, кто думает, что они будут в течение их первого курса).
Рейраб
1
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Рафаэль
Для меня это было очень полезно для чувства «благодарности и облегчения позже, когда узнал о численных методах» . При работе с дискретными данными, поступающими из реальных измерений, вместо непрерывных функций из теоретической математики, было таким облегчением, что интегрирование - это просто сумма, а производная - просто вычитание, а не слишком сложные формулы, которые нам требовались так много времени и усилий. учиться в наших классах исчисления раньше!
vsz

Ответы:

112

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

  • Компьютерная графика Обработка / изображение, и здесь вы также должны Аналитическая геометрия и линейная алгебра, сильно ! Если вы пойдете по этому пути, вы также можете изучить некоторую дифференциальную геометрию (для которой многомерное исчисление является минимальной предпосылкой). Но вам понадобится Calculus здесь даже для самых простых вещей: попробуйте поискать, например, «Преобразование Фурье» или «Вейвлеты» - это два очень фундаментальных инструмента для людей, работающих с изображениями.
  • Оптимизация , в основном нелинейная, где многомерное исчисление является основным языком, используемым для разработки всего. Но даже линейная оптимизация извлекает выгоду из исчисления (производная целевой функции абсолютно важна)
  • Вероятность / Статистика . Они не могут быть серьезно изучены без многомерного исчисления.
  • Машинное обучение , которое активно использует статистику (и, следовательно, многомерное исчисление)
  • Data Mining и смежные вопросы, которые также используют много статистики;
  • Робототехника , где вам нужно будет моделировать физические движения робота, поэтому вам нужно будет знать частичные производные и градиенты.
  • Дискретная математика и комбинаторика ( да! Вам может понадобиться исчисление для дискретного счета!) - если вы достаточно серьезно относитесь к генерации функций, вам нужно знать, как интегрировать и выводить определенные формулы. И это полезно для анализа алгоритмов (см. Книгу Седжвика и Флайолета «Анализ алгоритмов»). Точно так же ряды Тейлора и исчисление могут быть полезны при решении некоторых видов рекуррентных отношений, которые используются в анализе алгоритмов.
  • Анализ Алгоритмов , где вы используете понятие предела с самого начала (см. Обозначение Ландау, «маленький о » - оно определяется с использованием предела)

Могут быть и другие - это просто с моей головы.

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

Наконец - вам понадобится исчисление, чтобы хорошо взаимодействовать с людьми из других точных наук и инженерии. И весьма обычно, что Компьютерный Ученый должен не только говорить, но также и работать вместе с Физиком или Инженером.

сойка
источник
35
Возможно, у вас был другой опыт, но я нашел исчисление довольно бесполезным для того, чтобы научиться рассуждать и строго объяснять аргументы. Его обучали механизму и сопоставлению с образцом, как в алгебре и геометрии средней школы. С другой стороны, это было необходимым условием для нескольких старших классов по математике , которые сделали преподавать эти навыки, так что я предполагаю , что это было не совсем бесполезно.
Цлейсон
6
Я могу полностью обратиться к самому последнему пункту (косвенные выгоды). Работая над теорией языков программирования, я редко использовал исчисление напрямую. Возможно, самое прямое применение было в вероятностных вычислительных моделях (например, вероятностные домены Plotkin & Jones). Тем не менее, мой курс исчисления был главным образом о доказательстве вещей, и это было очень, очень ценно. ИМХО один или два курса исчисления необходимы в каждой серьезной программе CS, а также некоторые другие математические (дискретная математика, логика, линейная алгебра, численный анализ, ... и, возможно, категории, топология, алгебра, ...).
Чи
3
Вот пример того , как мне нужно было исчисление в компьютерной графике: Гладкие функции интерполяции будут в основном все быть в форме f(0) = 0, f(1) = 1, f'(0) = f'(1) = 0и вы можете добавить любые другие ограничения , вы заботитесь о, например f'(0.5) = 1. Некоторое время назад я использовал это, чтобы получить несколько различных интерполяционных полиномов для сглаживания изображений.
porglezomp
3
Робототехника, вероятно, может быть расширена до любого вида физического моделирования (которое, я думаю, также охватывает CG, с точки зрения освещения, поэтому давайте назовем это моделированием кинетической физики). Это включает ускорение / скорость, отскоки / пружины / деформации, ПИД-регуляторы, акустику, гравитацию ...
metao
2
Я буду отстаивать косвенную точку зрения следующим образом: лучше, чем любой класс, который они посещают раньше, Calculus учит студентов, что они не могут просто посчитать количество проблем и оценить, сколько работы будет вовлечено.
candied_orange
20

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

Алгебраические типы данных

Возможно, вы встречали кортежи, называемые типами продуктов (если нет, то это потому, что они являются декартовым продуктом двух типов). Мы собираемся принять это буквально и использовать обозначение:

a*б

aб

a+б

aNaбNбa+бNa+Nб .

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

Пример

В функциональных языках общее определение списка (приведенное здесь на Haskell) таково:

data List a = Empty 
            | Cons a List

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

L(a)знак равно1+a*L(a)

1L(a)

L(a)знак равно1+a*L(a)
L(a)знак равно1+a*(1+a*L(a))
L(a)знак равно1+a+a2*(1+a*L(a))
L(a)знак равно1+a+a2+a3*(1+a*L(a))
L(a)знак равно1+a+a2+a3+a4+a5,,,

ИксN

Это определение говорит тогда, что список - это либо единица, либо кортеж из одного элемента, либо кортеж из двух элементов, или из трех и т. Д., Что является определением списка!

Контексты с одним отверстием

Теперь перейдем к контексту с одним отверстием: контекст с одним отверстием - это то, что вы получаете, когда «извлекаете значение» из типа продукта. Давайте приведем пример:

a2aa+a2a

Взятие значения из 3-х кортежей дает 2-кортеж, но есть три разных варианта:

(a,a,_)
(a,_,a)
(_,a,a)

3a2a3

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

Если мы возьмем наше оригинальное выражение для списка:

L(a)знак равно1+a*L(a)

Мы можем переставить, чтобы получить:

L(a)знак равно11-a

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

Теперь, если мы дифференцируем это, мы получим интересный результат:

L(a)aзнак равно(L(a))2

Таким образом, один список стал парой списков. Это на самом деле имеет смысл: два создаваемых списка соответствуют элементам выше и ниже дыры в первоначальном списке!

Туомас Лаакконен
источник
Это было чудесно проницательно. Благодарю.
Д. Бен Кнобл
12

Численные методы. Существуют громоздкие проблемы исчисления, которые являются уникальными для конкретных приложений, и они нуждаются в решениях быстрее, чем человек может практически решить без программы. Кто-то должен разработать алгоритм, который будет вычислять решение. Разве это не единственное, что отделяет программистов от ученых?

Иона Гавел
источник
3
Учитывая «списочную» природу этого вопроса, каждый ответ должен пытаться дать полную картину. Вы уверены, что хотите утверждать, что численные методы являются единственным примером?
Рафаэль
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Рафаэль
12

Автоматизация - Подобно робототехнике, автоматизация может потребовать количественной оценки человеческого поведения.

Расчеты. Поиск решений доказательств часто требует исчисления.

Визуализации. Для использования продвинутых алгоритмов требуется исчисление, такое как cos, sine, pi и e. Особенно, когда вы вычисляете векторы, поля столкновений и сетку.

Логистика и анализ рисков. Определение возможности выполнения задачи, степени риска и вероятности успеха.

Безопасность - большая часть безопасности может быть выполнена без исчисления; однако многие люди, которые хотят объяснений, предпочитают его в математических выражениях.

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

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

Наука и инженерия - При работе практически с любой другой научной дисциплиной требуется исчисление: аэрокосмическая, астрологическая, биологическая, химическая или инженерная.

Многие люди в программировании могут пройти всю свою карьеру без использования исчисления; Тем не менее, это может оказаться неоценимым, если вы готовы сделать работу. Для меня это было наиболее эффективно в автоматизации, логистике и визуализации. Идентифицируя определенные шаблоны, вы можете просто игнорировать шаблон, подражать шаблону или разработать более совершенный метод все вместе.

LJones
источник
7
πе
3
ехр(Икс)е(Икс)знак равное'(Икс)е(0)знак равно1е'(Икс)знак равнограмм(Икс)грамм'(Икс)знак равно-е(Икс)е(0)знак равно0грамм(0)знак равно1
2
@DavidRicherby: Пример: как вы реализуете эти функции, скажем, на микроконтроллере без FPU? Если вы знаете какое-то исчисление, вы сразу же знаете хороший ответ: степенные ряды.
Нейт Элдредж
6

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

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

Скотт Б
источник
9
Ваш первый абзац совершенно неверен и граничит с теорией заговора. Есть достаточно областей компьютерной науки, где исчисление полезно (см. Другие ответы для их бесконечного списка). Конечно, можно обойти все эти области, но вводить в заблуждение исчисление будет неэффективно, если не учитывать оценки.
Дэвид Ричерби
4
В зависимости от вашей программы получения степени, вы можете получить степень, даже не используя исчисление, и я определенно думаю, что специализациям CS не нужно столько, сколько мы получаем. Но если вы плохо справитесь с этим, вы не сможете выбраться из некоторых наиболее интересных областей информатики. После окончания учебы у вас будет достаточно времени, чтобы стать веб-разработчиком; в школе, почему бы не попробовать себя немного подтолкнуть?
Цлейсон
3
@tsleyson Если вы хотите стать веб-разработчиком, сэкономьте деньги на обучение и время, необходимое для получения степени CS.
Рафаэль
8
@ ScottB Вы, кажется, путаете информатику с программированием.
Дэвид Ричерби
3
@ ScottB Кто говорит, что CS = математика + программирование? Я сам выступал против этого ограниченного взгляда целую вечность. Но у вас есть и обратное: математика является неотъемлемой частью CS, как и физика. Нам это нужно , даже если мы не хотим практиковать это. (Тем не менее, это не место для этого обсуждения. Пожалуйста, присоединяйтесь к нам в информатическом чате, если вы хотите продолжить.)
Рафаэль
4

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

Производные регулярного выражения пересмотрены

Если вы знаете автоматы, возможно, этот PDF стоит прочитать.

Aristu
источник
Я не вижу там никакого дифференциального исчисления; Я вижу слово «производная», но не вижу ничего похожего на традиционное дифференциальное исчисление.
2
Это называется «формальная производная», и это в некотором роде связано с исчислением. Вы также увидите, что это сделано с помощью функции «Генерация функций», некоторых формул, связанных с дискретными структурами, и других областей, где у вас фактически нет «гладкой функции».
Jay
@Jay: главное не имя. Как понимание исчисления помогает с этим?
Кристиан
2
Это объясняется на этой странице Википедии . Формальная производная - это операция над элементами аналгебраической структуры, которая содержит многочлены, и формально она «очень похожа» на обычное правило дифференцирования многочленов, однако - в отличие от того, что студент видит в исчислении, - многочлены не являются реальными действительными; они могут быть полиномами над произвольным «кольцом» (другая алгебраическая структура). И есть практические применения формальной производной - я видел по крайней мере одну (алгебраический криптоанализ - не могу вспомнить детали).
Jay
4

Несколько более конкретных примеров:

  • Исчисление используется для выведения дельта-правила , которое позволяет некоторым типам нейронных сетей «учиться».
  • Исчисление можно использовать для вычисления преобразования Фурье осциллирующей функции, что очень важно при анализе сигналов.
  • Исчисление все время используется в компьютерной графике, которая является очень активной областью, поскольку люди постоянно открывают новые методы. Для фундаментального примера посмотрите уравнение рендеринга Кадзиа
  • Исчисление важно в области вычислительной геометрии, исследования кривой и моделирования поверхности.
собака Джонс
источник
3

К этим другим превосходным ответам я добавляю этот пункт: строгость в тестировании .

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

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

Конкретные отрасли, в которых я работал, где требовалось исчисление, включают:

  • Финансы (создание торговой платформы)

  • Страхование (численная интеграция страховых полисов в сценариях «что, если» для расчета ожидаемых потерь полиса)

  • Логистика (оптимизация консолидации транспортных маршрутов)

  • Обработка сигналов

Павел Чернох
источник
3

Исчисление - неотъемлемая часть - используется непосредственно в CS как основа для размышлений о суммировании. Если вы проработаете какую-либо часть раздела «Конкретная математика» Кнута по суммированию, вы быстро поймете соглашения, общие для исчисления: понимание некоторых непрерывных случаев дает вам инструменты для рассмотрения дискретных.

Многие из применений вашего исследования CS включают системы программирования, которые отслеживают изменения или, в некоторых случаях, пытаются предсказать будущее. Математика вокруг этих систем основана на дифференциальных уравнениях и линейной алгебре, а дифференциальные уравнения - это исчисление. Есть такие учителя, как Гиберт Странг, которые выступают за более быстрое продвижение в часть дифференциальных уравнений, но это все еще подмножество исчисления. Когда изменение зависит от изменений в любой системе, оно начинает быть нестабильным (и стабильным) способами, которые не интуитивны и очень хорошо понятны. Чтобы понять, почему ваша разумная линейная система ведет себя нелинейным образом, вам либо нужны инструменты исчисления, либо вам нужно заново изобретать их для своего проблемного пространства.

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

Джесс
источник
«Многие виды использования вашего исследования CS включают в себя системы программирования, которые отслеживают изменения или, в некоторых случаях, пытаются предсказать будущее», - я не думаю, что это является представителем самых популярных курсов обучения CS.
Рафаэль