Построение выпуклой оболочки набора точек

Триангуляция

Диаграмма Вороного

Локализация точки (англ.)

Пересечения

Вращающиеся калиперы (англ.)

Компьютерная графика

Компьютерное зрение

Криптографические алгоритмы

Шифрование с симметричным (скрытым) ключом:

· ГОСТ 28147-89

· AES (англ. Advanced Encryption Standard) — победитель соревнования NIST, также известен как Rijndael

· Blowfish

· DES (англ. Data Encryption Standard) — иногда, алгоритм DEA (англ. Data Encryption Algorithm), победитель соревнования NBS, заменён на AES для большинства применений

· RC2

· IDEA (англ. International Data Encryption Algorithm)

· RC4

Асимметричное шифрование (с публичным ключом)

· RSA

Цифровая обработка сигналов

Цифрова́ я обрабо́ тка сигна́ лов (ЦОС, DSP - англ. digital signal processing) — преобразование сигналов, представленных в цифровой форме.

Линейная фильтрация — селекция сигнала в частотной области; синтез фильтров, согласованных с сигналами; частотное разделение каналов; цифровые преобразователи Гильберта и дифференциаторы; корректоры характеристик каналов

Спектральный анализ — обработка речевых, звуковых, сейсмических, гидроакустических сигналов; распознавание образов

Частотно-временной анализ — компрессия изображений, гидро- и радиолокация, разнообразные задачи обнаружения сигнала

Адаптивная фильтрация — обработка речи, изображений, распознавание образов, подавление шумов, адаптивные антенные решетки

Нелинейная обработка — вычисление корреляций, медианная фильтрация; синтез амплитудных, фазовых, частотных детекторов, обработка речи, векторное кодирование

Многоскоростная обработка — интерполяция (увеличение) и децимация (уменьшение) частоты дискретизации в многоскоростных системах телекоммуникации, аудиосистемах

Свертка - традиционные типы

Секционная свертка

Разработка программного обеспечения

Генетические алгоритмы

Генети́ ческий алгори́ тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Медицинские алгоритмы

Нейронные сети

· Метод обратного распространения ошибки

· Самоорганизующееся отображение (Карты Кохонена, SOM)

· Метод коррекции ошибки

· Метод коррекции с обратной передачей сигнала ошибки

 

Вычислительная алгебра

Алгоритмы вычисления дискретного преобразования Фурье

· Быстрое преобразование Фурье

Быстрое преобразование Фурье (БПФ, FFT) — это быстрый алгоритм вычисления дискретного преобразования Фурье (ДПФ).

Решение систем линейных уравнений

· Метод Гаусса (Гауссово исключение) — стандартный метод решения систем линейных уравнений

· Структурированное гауссово исключение — применяется, когда матрица системы является разреженной

· Метод Жордана — Гаусса — модификация метода Гаусса для матричного представления

· Разложение Холецкого — метод, эффективный для ленточных и разреженных матриц

· Метод Пранис — Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам

Теоретико-числовые алгоритмы

Численные алгоритмы

Алгоритм де Кастельжо — вычисление кривых Безье

Методы интерполяции:

Линейное сглаживание по трём точкам

Линейное сглаживание по пяти точкам

Нелинейное сглаживание по семи точкам

Интерполяция сплайнами

Приближенное вычисление решений

Метод фальшпозиции (англ.) (False position method, regula falsi method) — аппроксимирует корни функции

Метод Ньютона (метод касательных) — нахождение нулей функций с помощью производной

Метод секущих (метод хорд) — аппроксимирует корни функции

Метод градиентов (градиентный спуск) — аппроксимирует решение системы уравнений

Метод сопряжённого градиента

Алгоритм Гаусса — Ньютона — алгоритм для решения нелинейных уравнений методом наименьших квадратов

Алгоритм Левенберга — Марквардта — алгоритм для решения нелинейных уравнений методом наименьших квадратов

Решение диффернциальных уравнениий

Метод Эйлера

Рассмотрим дифференциальное уравнение первого порядка

y^/=f(x, y) (1)

с начальным условием

x=x₀, y(x₀)=y₀ (2)

Требуется найти решение уравнения (1) на отрезке [а, b].

Разобьем отрезок [a, b] на n равных частей и получим последовательность х₀, х₁, х₂, …, х_n, где x_i=x₀+ih (i=0, 1, …, n), а h=(b-a)/n-шаг интегрирования.

В методе Эйлера приближенные значения у(х_i)»y_i вычисляются последовательно по формулам у_i+hf(x_i, y_i) (i=0, 1, 2…).

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

y_m+1=y_m+h/6(R₁+2R₂+2R₃+R₄) 1.14

где R₁=f(x_m, y_m), 1.15

R₂=f(x_m+h/2, y_m+hR₁/2), 1.16

R₃=f(x_m+h/2, y_m+hR₂/2), 1.17

R₄=f(x_m+h/2, y_m+hR₃/2). 1.18

15. Алгоритмы оптимизации

· Линейное программирование

· Симплекс-метод

· «Венгерский метод» — решение задач целочисленного линейного программирования

· Метод Мака решения задачи о назначениях

· Алгоритм имитации отжига

· Метод роя частиц

· Муравьиные алгоритмы

· Метод ветвей и границ

· Дифференциальная эволюция

· Эволюционная стратегия

· Метод Нелдера — Мида (downhill simplex method) — алгоритм нелинейной оптимизации

· Всхождение со случайным перезапуском (англ.)

· Стохастическое туннелирование (англ.)

· Алгоритм суммирования подмножеств (англ.)

· Метод перебора

· Метод Фибоначчи поиска экстремума — метод выбора точек для нахождения экстремума функции одной переменной

· Градиентный спуск

· Алгоритм Левенберга — Маркардта — комбинация метода Ньютона и наискорейшего спуска

Грамматический разбор

Квантовые алгоритмы

Теория вычислений и автоматов

Лекция

Компьютерная обработка информации

Обработка информации — преобразование одних информационных объектов в другие путем выполнения некоторых алгоритмов.

При решении задач обработки информации на компьютере строится модель того аспекта реального или воображаемого мира, к которому будет применяться алгоритм решения задачи. В такой модели информацию об объекте исследования представляют в формализованном виде: в виде структур данных («информационных объектов»), представляющих собой некоторую абстракцию данного объекта. Абстракция (от лат. abstraction -отвлечение) подразумевает выделение наиболее существенных с точки зрения задачи обработки свойств и связей.

Исполнитель алгоритма — абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

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

В зависимости от формы представления обрабатываемой информации вычислительные машины делятся на три больших класса:

· цифровые вычислительные машины (ЦВМ), обрабатывающие информацию, представленную в цифровой форме;

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

· гибридные вычислительные машины (ГВМ), содержащие как аналоговые, так и цифровые вычислительные устройства.

История развития ЭВМ

Простейшие:

· Счётные палочки

· Простейшие балансирные весы

· Абак или Счёты

· Чётки

Счетные механизмы:

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

· В 1623 году Вильгельм Шикард придумал «Считающие часы» — первый механический калькулятор, умевший выполнять четыре арифметических действия.

· Машины Блеза Паскаля («Паскалина», 1642 г.) и Готфрида Вильгельма Лейбница.

· Примерно в 1820 году Charles Xavier Thomas создал первый удачный, серийно выпускаемый механический калькулятор — Арифмометр Томаса, который мог складывать, вычитать, умножать и делить. В основном, он был основан на работе Лейбница. Механические калькуляторы, считающие десятичные числа, использовались до 1970-х.

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

Джон Непер заметил, что умножение и деление чисел может быть выполнено сложением и вычитанием, соответственно, логарифмов этих чисел. Действительные числа могут быть представлены интервалами длины на линейке, и это легло в основу вычислений с помощью логарифмической линейки, что позволило выполнять умножение и деление намного быстрее. Логарифмические линейки использовались несколькими поколениями инженеров и других профессионалов, вплоть до появления карманных калькуляторов. Инженеры программы «Аполлон» отправили человека на Луну, выполнив на логарифмических линейках все вычисления, многие из которых требовали точности в 3—4 знака.

Появление перфокарт

В 1804 году Жозеф Мари Жаккар разработал ткацкий станок, в котором вышиваемый узор определялся перфокартами.

В 1838 году Чарльз Бэббидж перешёл от разработки Разностной машины к проектированию более сложной аналитической машины, принципы программирования которой напрямую восходят к перфокартам Жаккара.

В 1890 году Бюро Переписи США использовало перфокарты и механизмы сортировки (табуляторы), разработанные Германом Холлеритом, чтобы обработать поток данных десятилетней переписи, переданный под мандат в соответствии с Конституцией. Компания Холлерита в конечном счёте стала ядром IBM.

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: