bigpo.ru
добавить свой файл
1
СЛОВАРЬ ТЕРМИНОВ


«Алгоритм это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)


«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)


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


«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)


«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)


Алгебраический порядок точности численного метода (порядок точности численного метода, степень точности численного метода, порядок точности, степень точности) — наибольшая степень полинома, для которой численный метод даёт точное решение задачи.


Биекция – отображение, являющееся одновременно сюръективным (т.е. любому элементу из Y сопоставлен свой прообраз) и инъективным (разные элементы множества X переводятся в разные элементы множества Y).


Бисекции метод или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.


Булевой алгеброй называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:







ассоциативность






коммутативность






законы поглощения






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






дополнительность



Диаграммы Эйлера — Венна, изображают все 2n комбинаций n свойств, то есть конечную булеву алгебру. При n = 3 диаграмма Эйлера — Венна обычно изображается в виде трёх кругов с центрами в вершинах равностороннего треугольника и одинаковым радиусом, приблизительно равным длине стороны треугольника.


Дискретная математика - область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. К числу таких структур могут быть отнесены конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, конечные автоматы, машины Тьюринга и так далее. Это примеры структур конечного (финитного) характера. Раздел дискретной математики, изучающий их, называется конечной математикой. Иногда само это понятие расширяют до дискретной математики. Помимо указанных конечных структур, дискретная математика изучает некоторые алгебраические системы, бесконечные графы, вычислительные схемы определённого вида, клеточные автоматы и т. д. В качестве синонима иногда употребляется термин «дискретный анализ».


Интерполяционные формулы Ньютона формулы вычислительной математики, применяющиеся для полиномиального интерполирования.

Если узлы интерполяции равноотстоящие и упорядочены по величине, так что xi + 1xi = h = const, то есть xi = x0 + ih, то интерполяционный многочлен можно записать в форме Ньютона.

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


Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n + 1 пар чисел , где все xi различны, существует единственный многочлен L(x) степени не более n, для которого L(xi) = yi.

В простейшем случае (n = 1) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.


Интерполяция алгебраическими многочленами функции f(x) на отрезке [a, b] — построение многочлена Pn(x) степени меньшей или равной n, принимающего в узлах интерполяции x0, x1, ..., xn значения f(xi)


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


Итерация — это организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (не путать с рекурсией)


Класс NP (от англ. non-deterministic polynomial) - множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за время, не превосходящее полинома от размера данных) проверить на машине Тьюринга.

Эквивалентно класс NP можно определить как содержащий задачи, которые можно «быстро» решить на недетерминированной машине Тьюринга.


Класс P (от англ. polynomial) - множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов.


Класс эквивалентности C(a) элемента a - подмножество элементов, эквивалентных a.


Количество размещений из n по k, обозначаемое , равно убывающему факториалу:



При k=n количество размещений равно количеству перестановок порядка n:




Комбинаторный анализ - раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).


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


Маши́на Тью́ринга абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен


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


Ньютона метод, алгоритм Ньютона (также известный как метод касательных) —итерационный численный метод нахождения корня (нуля) заданной функции. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.


Объединение множеств - множество, содержащее в себе все элементы исходных множеств. Объединение двух множеств A и B обозначается как.


Отношение эквивалентности на множестве X – бинарное отношение, для которого выполнены условия рефлексивности, симметричности и транзитивности.


Пересечение множеств - множество, которому принадлежат те и только те элементы, которые одновременно принадлежат всем данным множествам. Пересечение множеств A и B обозначается как.


Перестановка из n элементов (скажем, чисел 1,2,…,n) – любой упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.


Прямоугольников методметод численного интегрирования функции одной переменной, заключающийся в замене подынтегральной функции на многочлен нулевой степени, то есть константу, на каждом элементарном отрезке. Если рассмотреть график подынтегральной функции, то метод будет заключаться в приближённом вычислении площади под графиком суммированием площадей конечного числа прямоугольников, ширина которых будет определяться расстоянием между соответствующими соседними узлами интегрирования, а высота — значением подынтегральной функции в этих узлах. Алгебраический порядок точности равен 0.

Разбиение числа n - всякое представление n в виде неупорядоченной суммы целых положительных чисел.


Разложе́ние Холе́цкогопредставление симметричной положительно-определённой матрицы A в виде A = LLT, где L — нижняя треугольная матрица со строго положительными элементами на диагонали. Иногда разложение записывается в эквивалентной форме: A = UTU, где U = LT — верхняя треугольная матрица. Разложение Холецкого всегда существует и единственно для любой симметричной положительно-определённой матрицы.


Разность двух множеств - множество, в которое входят все элементы первого множества, не входящие во второе множество. Разность множеств A и B обозначается как .


Размещение из n элементов по k есть упорядоченный набор из k различных элементов некоторого n-элементного множества (ср. сочетание).


Рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.


Рефлексивность: бинарное отношение R на множестве X называется рефлексивным, если всякий элемент этого множества находится в отношении R с самим собой, т.е. если .


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


Симметричность: бинарное отношение R на множестве X называется симметричным, если для каждой пары элементов множества (a,b) выполнение отношения влечёт выполнение отношения , т.е. если .


Сочетание из n по k - набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений (ср. размещение).


Теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения проблемы, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа и выхода?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжера длина входа пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (оптимального маршрута в задаче коммивояжера).

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


Транзитивность: бинарное отношение R на множестве X называется транзитивным, если для любых трёх элементов множества a,b,c выполнение отношений aRb и bRc влечёт выполнение отношения aRc., т.е. если .


Трапеций метод — метод численного интегрирования функции одной переменной, заключающийся в замене на каждом элементарном отрезке подынтегральной функции на многочлен первой степени, то есть линейную функцию. Площадь под графиком функции аппроксимируется прямоугольными трапециями. Алгебраический порядок точности равен 1.


Формула Симпсона (также Ньютона-Симпсона) относится к приёмам численного интегрирования. Получила название в честь британского математика Томаса Симпсона (1710—1761). Суть приёма заключается в приближении подынтегральной функции на отрезке интерполяционным многочленом второй степени , то есть приближение графика функции на отрезке параболой. Метод Симпсона имеет порядок погрешности 4 и алгебраический порядок точности 3.


Численное интегрирование (историческое название: (численная) квадратура) — вычисление значения определённого интеграла (как правило, приближённое). Под численным интегрированием понимают набор численных методов отыскания значения определённого интеграла.


Число сочетаний из n по k равно биномиальному коэффициенту