28. Типовые алгоритмы сортировки данных.

Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Алгоритмы устойчивой сортировки

• Сортировка выбором— поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка.

Алгоритмы неустойчивой сортировки

• Сортировка Шелла - попытка улучшить сортировку вставками.

• Сортировка расчёской

Непрактичные алгоритмы сортировки

• Bogosort - в среднем. Произвольно перемешать массив, проверить порядок.

• Сортировка перестановкой — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.

Алгоритмы, не основанные на сравнениях

• Блочная сортировка (Корзинная сортировка)

• Лексикографическая или поразрядная сортировка

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

• Топологическая сортировка

• Внешняя сортировка.

29. Поиск оптимального решения. Линейное программирование.

Линейное программирование —математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

Табличный симплекс-метод

Метод искусственного базиса

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Данный метод, имеющий несколько различных форм (модификаций), был разработан в 1947 году Г. Данцигом.

30. Погрешности вычислений. Источники и оценка.

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

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

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

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