7 Feb 2022
Что добавилось в язык С++ по сравнению с языком С
помимо классов?
1. Добалены были встроенные в язык операторы new и delete
(захвата и освобождения динамической памяти) -- вместо
функций malloc и free.
2. Был добавлен тип "ссылка" (reference).
Ссылка -- это второе имя для уже существующего объекта
(псевдоним, алиас, nickname). Ссылка -- это не указатель!
Указатель -- это переменная, которая хранит адрес некоторого
объекта. Ссылка вообще не обязательно должна быть переменной,
под нее может выделаться память, а может и не выделяться.
Как устроена ссылка внутри, программисту знать запрещено.
int k;
int& l; // ОШИБКА!
int& l = k;
После этого любое обращение к l переадресуется к k.
double a[100];
double& last = a[99];
В отличие от указателя, ссылку нельзя перенаправить на другой объект.
Ссылки в основном используются для передачи параметров функциям.
В языке С функциям всегда передаются КОПИИ объектов. Если мы хотим,
чтобы функция изменила переданный, то в С надо передавать указатель
на объект. В С++ в таких случаях передается ссылка.
Пример: вычислить окружность, вписанную в треугольник.
Прототип функции:
void insribedCircle(
const R2Point* vertices,
R2Point& center, double& radius
);
R2Point a[3]; // Vertices of triangle
R2Point center;
double radius;
a[0] = R2Point(0., 0.);
a[1] = R2Point(5., 1.);
a[2] = R2Point(3., 5.);
insribedCircle(a, center, radius);
В языке C пришлось бы написать:
void insribedCircle(
const R2Point* vertices,
R2Point* center, double* radius
);
. . .
insribedCircle(a, ¢er, &radius);
3. Добавлен базовый тип bool.
int n = (2 == 2); // Так писать не надо!
bool n = (2 == 2);
bool m = true;
Что еще добавлено в С++
Главное -- классы (которые как бы вводят новые сложные типы
данных) и переопределение операторов языка С для классов.
class R2Vector {
public:
double x;
double y;
};
R2Vector u(1., 2.), v(3., 4.);
R2Vector w;
Хотим вычислить сумму двух векторов.
w.x = u.x + v.x;
w.y = u.y + v.y;
Так никто не пишет!!! Я попросту не буду засчитывать
подобные программы, где вместо операций с векторами или точками
производятся манипуляции с их координатами.
Надо писать:
w = u + v;
Это означает, что для класса R2Vector переопределен оператор
сложения. Например, оператор умножения * для двух векторов
определен как скалярное произведение (dot product).
double s = u*v; // s == 11. == u.x*v.x + u.y*v.y
R2Vector t = u*2.5; // Это уже умножение вектора на число.
Это всё каcается языка С++ образца 1985 г.
В 1998 г. вышла третья версия языка С++, в нее были добавлены
1) механизм шаблонов (template);
2) понятие пространства имен (namespace);
3) стандартная библиотека.
Степанов (американец) написал библиотеку STL (Standard Library),
которая настолько понравилась Страуструпу, что он включил ее в
качестве обязательного элемента любого компилятора С++.
Книга Страуструпа 1997 г. "The C++ Programming Language"
"Язык программирования С++" на 90% посвящена описанию стандартной
библиотеки.
Помимо стандартной библиотеки, имеется библиотека Boost, библиотеки
Qt и т.д.
Все классы и функции стандартной библиотеки включены в простанство
имен std.
Минимальная программа hello, world!
На С:
#include <stdio.h>
int main() {
printf("Hello, World!\n");
return 0;
}
На С++ с использованием стандартной библиотеки:
#include <iostream>
int main() {
std::cout << "Hello, World!" << std::endl;
return 0;
}
Страуструп этого не советует, но многие ленятся писать префикс std,
есть возможность импортировать ВСЕ имена из стандартной библиотеки
в неименованное пространство имен:
using namespace std;
Тогда программу Hello можно написать так:
#include <iostream>
using namespace std;
int main() {
cout << "Hello, World!" << endl;
return 0;
}
Давайте разберем программу нахождения окружности,
вписанной в треугольник. Для этого мы используем готовые классы
R2Vector и R2Point. (Эти классы были написаны мной в учебных целях,
но оказалось, что они очень удобны для любой работы с компьютерной
графикой или геометрией.)
Для этих классов переопределены операции:
сумма векторов
разность двух точек -- это вектор!
к точке можно прибавить (или отнять) вектор
умножение двух векторов -- это склярное произведение
вектор можно умножить на число
У класса вектор имеются методы:
R2Vector v;
. . .
R2Vector n = v.normal(); // Нормаль к вектору
v.normalize(); // Нормализовать вектор (длина стала 1)
R2Vector u = v.normalized();
double len = v.norm(); // Евклидова длина вектора
len = v.length();
Главная идея объектно-ориентированного программирования:
вместо манипуляций с числами используем методы класса вектор и точка,
которые соответствуют геометрическим операциям.
Пример 1
Найти расстояние от точки до прямой
Как задается прямая?
Разные способы: две точки, точка и нормаль к прямой,
точка и направляющий вектор.
Итак, дана точка t и прямая, заданная точкой p
и направляющим вектором v
R2Point p; R2Vector v; // Задают прямую
R2Point t;
. . .
R2Vector n = v.normal();
n.normalize();
double d = fabs(n*(t - p));
Второй пример:
найти точку пересечение двух прямых
R2Point p1; R2Vector v1; // Первая прямая
R2Point p2; R2Vector v2; // Вторая прямая
R2Vector n = v2.normal();
// q = p1 + v1*t
// n*(q - p2) = 0
// n*(p1 + v1*t - p2) = 0
// n*(p1 - p2) + (n*v1)*t = 0
// t = n*(p2 - p1)/(n*v1)
double t = n*(p2 - p1)/(n*v1);
R2Point q = p1 + v1*t;
В пакете R2Graph.h, R2Graph.cpp помимо классов R2Vector, R2Point
реализованы также функции, решающие различные геометрические
задачи на плоскости. В частности,
bool intersectStraightLine(
const R2Point& p1, const R2Vector& v1,
const R2Point& p2, const R2Vector& v2,
R2Point& q
);
R2Point t;
R2Point p; R2Vector v;
. . .
double d = t.distanceToLine(p, v);
Разберем программу вычисления окружности, вписанной в треугольник.
14 Feb 2022
Разбираем программу "Вычислить окружность, вписанную в треугольник"
Консольное приложение на C++
Для представления векторов и точек мы используем свои классы
R2Vector и R2Point. Мы различает точки и векторы:
векторы можно складывать, а точки нельзя!
Разность двух векторов есть вектор.
ВНИМАНИЕ! Разность двух точек -- это операция осмысленная,
в отличие от суммы точек. Разность точек a - b
представляет собой вектор, направленный от b к a.
R2Point a, b;
. . .
R2Vector v = a - b; // вектор, направленный от b к a.
К точке можно прибавить (или отнять) вектор, в результате получим
точку:
R2Point a; R2Vector v;
. . .
R2Point b = a + v;
Главная идея первой задачи -- научиться решать геометрические
задачи геометрическими методами. Это означает, что вместо
манипуляций с координатами объектов (векторы и точки) мы
используем методы этих классов: сложение и вычитание векторов,
вычитание точек, прибавление (или вычитание) вектора к точке,
скалаярное произведение векторов, длина вектора, расстояние между
точками, получение нормали к вектору, нормализация вектора,
получение угла между векторами, ориентированная площадь треугольника
или параллелограмма, пересечение прямых и т.д.
ПРЕДУПРЕЖДЕНИЕ
Задача, которая решается с помощью обращения к координатам,
не будет засчитана!
Замечательные точки треугольника:
1. Центр вписанной окружности.
2. Центр описанной окружности (точка пересения серединных
перпендикуляров).
3. Центр тяжести вершин треугольника (точка пересечения медиан).
4. Ортоцентр -- точка пересечения высот.
6. Точка Жергона -- точка пересечения чевиан, проведенных из вершин
треугольника к точкам касания вписанной окружности.
Теорема Чевы дает необходимые и достаточные условия для того,
чтобы 3 отрезка, проведенные из вершин треугольника до пересечения
с противоположной стороной, пересекались бы в одной точке.
=====================================================================
Самая важная тема второго семестра
Представление матриц в компьютере.
Метод Гаусса приведения матрицы к ступенчатому виду
и задачи, которые решаются с его помощью
На эту тему будет одна задача (достаточно сложная).
Первое:
давайте не использовать базовые массивы языка C,
а пользоваться классом std::vector<double> из стандартной
библиотеки, который реализует динамический массив.
Динамический массив -- это массив, размер которого может изменяться
(может расти).
Массив в стиле языка C:
double *a = new double[n];
. . .
x = a[i];
a[j] = 0.5;
. . .
delete[] a;
Массив a не меняет своего размера в течение своей жизни.
Массив в стиле языка C++ c использованием стандартной библиотеки:
std::vector<double> a(n);
. . .
x = a[i];
a[j] = 0.5;
. . .
Никакого delete[] не требуется!!! Динамический массив умирает
естественно, его не требуется убивать. Кроме того, динамический
массив может расти:
std::vector<double> a; // Массив нулевого размера
assert(a.size() == 0);
a.push_back(1.5);
a.push_back(33.78);
assert(a.size() == 2);
assert(a.capacity() >= 2);
Мнемоника стандартной библиотеки (для шаблонных классов,
реализующих разные структуры данных)
push -- добавить
push_back(x) -- добавить x в конец структуры
push_front(x) -- добавить x в начало структуры
back() -- конец
fron() -- начало
pop -- удалить (отстрелить, выкинуть,
поп-корн, pop-gun).
pop_back() -- удалить конец
pop_front() -- удалить начало
Перейдем к матрицам.
ВНИМАНИЕ!!! Основная идея:
мы храним элементы матрицы в линейном массиве.
Для матрицы размера m x n (m строк, n столбцов) мы
сначала храним элементы нулевой строки, затем первой строки, ...,
в конце -- элементы m-1-й строки.
[ a00 a01 a02 a03 ]
[ a10 a11 a12 a13 ]
[ a20 a21 a22 a23 ]
Храним элементы в линейном массиве по строкам:
a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23
--------------- =============== ---------------
строка 0 строка 1 строка 2
Идиотский способ реализации матрицы (если вы будете его
использовать, я такие решения задач принимать не буду!)
ПЕРЕРЫВ до 12:45
Продолжим.
Неправильный способ -- матрица реализуется как массив указателей
на начала строк. Каждая строка хранится в отдельном сегменте
памяти, захваченном в куче.
int m, n;
. . .
double **a = new double*[m]; // Массив указателей на начала строк
for (int i = 0; i < m; ++i) {
a[i] = new double[n];
}
. . .
x = a[i][j];
a[i][j] = 3.5;
. . .
// Убийство матрицы
for (int i = 0; i < m; ++i) {
delete[] a[i];
}
delete[] a;
Такой способ приниматься не будет!!!
Чем он плох:
1) для обращения к элементу матрицы a[i][j] нужно 2 обращения к памяти;
2) плохо используется кэш-память процессора. При использовании
кэш-памяти данные из оператичной памяти читаются не по одному
элементу, а блоками, и заносятся в кэш-память. Если элемент уже
в кэш-памяти, то обращаться к оперативной памяти уже не нужно.
Поэтому выгодно, когда элементы матрицы лежат в одном
блоке памяти.
В правильном решении элементы матрицы хранятся в одном
линейном массиве по строкам. Тогда элемент матрицы a_ij хранится
в ячейке массиве с индексом
i*n + j
Элемент a_ij -- это
a[i*n + j]
Попробуем написать программу, которая читает матрицу из
файла, приводит ее к ступенчатому виду и печатает ответ
на консоли.
Орлов Андрей -- добавить в список
---------------------------------------
21 Feb 2022
Работа с матрицами
Мы представляем матрицу линейным массивом, в котором
элементы матрицы лежат по строкам. Индексы в программировании
начинаются с нуля (не как в математике, с единицы), это
удобнее, потому что индекс = смещение относительно начала.
Например, матрица 3x4
10 20 30 40
51 61 71 81
92 102 112 122
хранится в линейном массиве как
10 20 30 40 51 61 71 81 92 102 112 122
В этом семестре мы будем использовать вместо массивов в стиле C
double *a = new double[m*n]; // Захватываем память в куче
. . .
x = a[i*n + j];
. . .
delete[] a;
мы будем использовать класс vector из стандартной библиотеки С++:
std::vector<double> a(m*n); // Память в куче захватывается в конструкторе
// Освобождать память не надо!
// Она освобождается в деструкторе класса vector
double determinant(int m, int n, const double *a) {
double *b = new double[m*n];
for (int i = 0; i < m; ++i) { // Копируем матрицу a в матрицу b
for (int j = 0; j < n; ++j) {
b[i*n + j] = a[i*n + j];
}
}
gauss(b, m, n);
double d = 1.;
for (int i = 0; i < m; ++i) {
d *= b[i*n + i];
}
delete[] b;
return d;
}
То же самое в стиле C++:
double determinant(int m, int n, const std::vector<double>& a) {
std::vector<double> b = a;
gauss(b, m, n);
double d = 1.;
for (int i = 0; i < m; ++i) {
d *= b[i*n + i];
}
return d;
}
Прошлый раз мы написали алгоритм Гаусса.
Задачи: 4 задачи
Все они сводятся к методу Гаусса
Обратная матрица
1 2 3
4 5 6
7 8 0
Приписываем справа к исходной матрице единичную
1 2 3 1 0 0
4 5 6 0 1 0
7 8 0 0 0 1
Приводим матрицу к ступенчатому виду методом Гаусса:
* * * * * *
0 * * * * *
0 0 * * * *
Домножаем строки матрицы на числа, обратные к диагональным элементам
так, чтобы на диагонали получились единицы:
1 * * * * *
0 1 * * * *
0 0 1 * * *
Выполняем обратный проход в методе Гаусса:
1 0 0 * * *
0 1 0 * * *
0 0 1 * * *
То, что стоит справа -- это обратная матрица. Она вычислена за
O(n^3) операций.
Обратный проход в методе Гаусса используется также при решении
СЛАУ (системы линейных алгебраических уравнений).
1 2 3 2
4 5 6 3
7 8 0 5
Метод Гаусса:
* * * *
0 * * *
0 0 * *
Нормируем строки (домножаем) так, чтобы на диагонали были единицы:
1 * * *
0 1 * *
0 0 1 *
Выполняем обратный проход:
1 0 0 *
0 1 0 *
0 0 1 *
Столбец свободных членов представляет решение системы.
========================================================
28 Feb 2022
Применение алгоритма Гаусса (приведение матрица к ступенчатому
виду) для решения различных задач.
Задача 3. Решить систему линейных уравнений (СЛАУ -- Система Линейных
Алгебраических Уравнений) с невырожденной квадратной
матрицей.
AX = B, A -- матрица размера nxn, X -- вектор-столбец неизвестных,
B -- вектор-столбех свободных членов.
Идея: рассмотрим расширенную матрицу системы: столбец B приписываем справа к
матрице. Пример:
[1 2 3] [2]
A = [4 5 6] B = [3]
[7 8 0] [5]
Приписываем столбец B справа к матрице A
[1 2 3 | 2]
A = [4 5 6 | 3]
[7 8 0 | 5]
Эту матрицу приводим к ступенчатому виду методом Гаусса:
[ 1 2 3 2]
A1 = [ 0 3 6 5]
[ 0 0 9 -1]
Делим каждую строку на диагональный элемент:
[ 1 2 3 2 ]
A2 = [ 0 1 2 5/3]
[ 0 0 1 -1/9]
Выполняем обратный проход -- как бы выполняем метод Гаусса, но снизу-вверх
и справа налево
Что мы делаем: из верхних строк выше i-й с номерами k=1, 2, ..., i-1
вычитаем i-ю строку, умноженную на число -A_ik так,
чтобы элемент A_ik сократился. Получим матрицу
[ 1 0 0 -13/9]
A3 = [ 0 1 0 17/9]
[ 0 0 1 -1/9]
Каждая строка матрицы (с индексом i) представляет собой уравнение
x_i = b_i
то есть решением нашей системы будет столбец свободных членов.
Обратный проход будем делать для любой ступенчатой матрицы,
не обязательно квадратной и невырожденной.
x * * * * * * * *
0 0 0 x * * * * * -->
0 0 0 0 x * * * *
0 0 0 0 0 0 0 x *
0 0 0 0 0 0 0 0 0
1 * * 0 0 * * 0 *
0 0 0 1 0 * * 0 * rank -- это для ступенчатой матрицы
0 0 0 0 1 * * 0 * число ненулевых строк
0 0 0 0 0 0 0 1 *
0 0 0 0 0 0 0 0 0
В частном случае, для расширенной матрицы системы уравнений
с невырожденной квадратной матрицей
(ступенчатый вид которой треугольный) получим
x * * * * *
0 x * * * *
0 0 x * * * -->
0 0 0 x * *
0 0 0 0 x *
1 0 0 0 0 *
0 1 0 0 0 *
0 0 1 0 0 *
0 0 0 1 0 *
0 0 0 0 1 *
ПЕРЕРЫВ 15 минут до 12:40
Задача 2
Для квадратной невырожденной матрицы вычислить обратную матрицу.
Идея та же самая: метод Гаусса + обратный проход.
Умоляю, не использовать правило Крамера или что-то подобное
для вычисления обратной матрицы!!!
A
| |
inverse(A) = | -1^(i+j) A_ji/det(A) |
| |
A_ij -- алгебраическое дополнение: определитель матрицы,
которая получается вычеркиванием из A i-й строки
и j-го столбца.
ТАК ДЕЛАТЬ НЕ НАДО!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Обратную матрицу следует вычислить с помощью метода Гаусса:
Рассмотрим на примере:
[1 2 3]
A = [4 5 6]
[7 8 0]
1.К исходной матрице приписываем справа единичную матрицу:
[1 2 3 | 1 0 0]
A1 = [4 5 6 | 0 1 0]
[7 8 0 | 0 0 1]
2. Приводим полученную матрицу к ступенчатому виду методом Гаусса:
[ 1 2 3 | 1 0 0]
A2 = [ 0 3 6 | 4 -1 0]
[ 0 0 9 | -1 2 -1]
3. Выполняем обратный проход и получаем слева единичную матрицу:
[ 1 0 0 | -16/9 8/9 -1/9]
A3 = [ 0 1 0 | 14/9 -7/9 2/9]
[ 0 0 1 | -1/9 2/9 -1/9]
Справа будет обратная матрица:
[-16/9 8/9 -1/9]
inverse(A) = [ 14/9 -7/9 2/9]
[ -1/9 2/9 -1/9]
Доказательство:
Элементарные преобразования строк матриц можно реализовать как умножение
слева на специальные матрицы:
Обмен строки i со сторокой k
1 0 0 0 0
0 0 0 0 1
0 1 0 0 0
swap(2,5) = 0 0 1 0 0
0 0 0 1 0
0 1 0 0 0
(берем единичную матрицу и выполняем с ней элементарное преобразование;
получаем матрицу, которая при домножении произвольной матрицы на нее
слева будет выполнять то же самое преобразование с произвольной
матрицей).
Если любую матрицу A размера 5x5 домножить слева на матрицу swap(2, 5),
то у нее переставятся 2-я и 5-я строки
Аналогично определяются элементарные матрицы, реализующие другие
элементарные преобразования строк произвольной матрицы.
Когда мы элементарными преобразованиями СТРОК приводим матрицу к единичной E,
то это соответствует домножениям слева на элементарные матрицы:
E = s_k...(s3*(s2*(s1*A))) = (s_k...s3*s2*s1)*A ==>
s_k...s3*s2*s1 -- это обратная матрица.
Когда мы применяем элементарные преобразования к расширенной матрице
( A | E )
то единичная матрица справа умножается на произведение этих элементарных
матриц => значит, справа получится обратная матрица.
Задача 1.
Дано m векторов линейного пространства размерности n.
Требуется найти среди них максимальную линейно независимую систему.
Векторы записаны в файле в виде строк матрицы размером m x n.
Идея: записываем координаты векторов по столбцам новой матрицы
(т.е. транспонируем исходную матрицу и записываем ее в новую матрицу).
Транспонированную матрицу приводим методом Гаусса к ступенчатому виду.
Определяем индексы столбцов, содержащих ПЕРВЫЕ ненулевые элементы строк.
Это и будут нужные нам индексы линейно независимых векторов исходной системы.
Пример:
[ 1 2 3 4]
[10 20 30 40]
[ 4 3 2 1]
A = [ 1 1 1 1]
[ 0 0 0 0]
[ 1 0 0 0]
[10 10 0 0]
[ 0 0 1 1]
Транспонированная матрица
[ 1 10 4 1 0 1 10 0]
B = [ 2 20 3 1 0 0 10 0]
[ 3 30 2 1 0 0 0 1]
[ 4 40 1 1 0 0 0 1]
Приводим транспонированную матрицу к ступенчатому виду методом Гаусса:
[ 1 10 4 1 0 0 0 1]
С = [ 0 0 5 1 0 0 0 1]
[ 0 0 0 0 0 1 0 0]
[ 0 0 0 0 0 0 10 -1]
Находим, в каких столбцах стоят первые ненулевые элементы строк:
[ 1 10 4 1 0 0 0 1]
С = [ 0 0 5 1 0 0 0 1]
[ 0 0 0 0 0 1 0 0]
[ 0 0 0 0 0 0 10 -1]
= = = =
0 2 5 6
Значит, векторы с индексами 0, 2, 5, 6 представляют максимальную
линейно независимую подсистему (решение нашей задачи):
[ 1 2 3 4]
D = [ 4 3 2 1]
[ 1 0 0 0]
[10 10 0 0]
Последнюю задачу 4 разберем следующий раз.
============================================
5 Mar 2022
Задача 4.
Дана однородная линейная система уравнений
(свободные члены уравнений равны нулю) с вырожденной квадратной матрицей A:
A X = 0
(здесь X ∙ столбец неизвестных x1, x2, ... xn).
Вычислить базис пространства решений, т.е. найти n - rank(A) векторов.
Исходную матрицу прочесть из файла "input.txt"
(формат такой же, как и в задаче 1), ответ записать в файл "output.txt".
Матрицу A размера n x n можно рассматривать как линейный оператор
линейного пространства R^n. Множество векторов, которые переходят в 0
под действием оператора A, называется ядром линейного оператора:
Ker(A)
Это линейное подпространство:
v <- Ker(A), w <- Ker(A) =>
Av = 0, Aw = 0 ==> A(v+w) = Av + Aw = 0 ==> v + w <- Ker(A)
Нужно найти базис в этом подпространстве.
Анадогично определяется образ оператора A:
Im(A) = { v: найдется u такой, что A(u) = v }
Столбцы матрицы оператора представляют собой образы базисных векторов.
Образ -- это линейная оболочка столбцов.
dim Im(a) = rank(A)
Идея алгоритма:
приводим матрицу методом Гаусса к ступенчатому виду
A:
1 2 3
4 5 6
7 8 9
Расширенная матрица системы:
1 2 3 | 0
4 5 6 | 0
7 8 9 | 0
Столбец свободных членов остается нулевым при любых элементарных
преобразованиях ==> его можно не хранить в памяти.
Идея:
Матрица
* * * * * * | 0
* * * * * * | 0
* * * * * * | 0
* * * * * * | 0
* * * * * * | 0
* * * * * * | 0
Приводим к ступенчатому виду:
0 a * * * * | 0 a_ij != 0
0 0 a * * * | 0
0 0 0 0 a * | 0
0 0 0 0 0 0 | 0
0 0 0 0 0 0 | 0
0 0 0 0 0 0 | 0
------------
f m m f m f
t t t mainVar[i] = true, если переменная главная
Главные переменные отмечены буквой m (от слова main)
Свободные переменные отмечены буквой f (от слова free)
В данном случае свободные переменные x0, x3, x5
Главные переменные x1, x2, x4
Свободным переменным можно придать любой набор значения,
при этом главные переменные определяются однозначно
с помощью обратного прохода:
Идем снизу вверх:
последнее уравнение выглядит как
a x4 + * x5 = 0 => x4 = -* x5 / a
Для того, чтобы получить базис в пространстве решений,
придаем свободным переменным последовательно значения
1, 0, 0, ..., 0
0, 1, 0, ..., 0
. . .
0, 0, 0, ..., 1
Для каждого набора значений свободных переменных определяем
значения главных переменных.
В результате получим n - r векторов-строк, представляющих
базис в пространстве решений однородной системы. Здесь n --
размерность пространства, r -- ранг матрицы
Это -- базис в ядре линейного оператора.
Этот базис мы выдаем в виде матрицы размера (n-r)*n,
координаты базисных векторов записаны по строкам матрицы.
========================================
14 Mar 2022
Задача сортировки:
дан массив a длины n. Надо упорядочить его элементы по
возрастанию:
a[0] <= a[1] <= a[2] <= ... <= a[n-1]
Теорема:
Для всякого алгоритма сортировки найдется входной массив,
на котором будет выполнено не меньше чем log_2(n!) сравнений:
t >= log_2(n!)
Функция log_2(n!) при n->inf ведет себя как
log_2(n!) ~ n*log_2(n)
Вопрос: а есть ли алгоритмы, которые работают за время
O(n*log_2(n)) ?
Ответ: да!
Первый такой алгоритм был предложен Шенноном в конце 40-х годов XX века:
сортировка слиянием Merge Sort.
Она требует вспомогательной памяти порядка O(n).
Зато она стабильная!
Очень красивый алгоритм: сортировка кучей (пирамидой) Heap Sort.
Не требует вспомогательной памяти, очень красивая в реализации.
Увы, она не стабильная...
Алгоритм сортировки называется стабильным, если он не меняет
взаимного порядка равных элементов.
"Быстрая сортировка" Quick Sort -- она не оптимальная, т.е. работает за время
O(n log(n)) только в среднем. (Из 1000 самолетов 999 будут приземляться успешно,
а один будет разбиваться.)
Также есть сортировка Radix Sort (поразрядная сортировка),
она применяется к строкам, состоящим из элементов дискетного конечного
множества -- например, банковские идентификаторы счетов, которые в России
состоят из 20 цифр, например,
13247546465354354357
Radix Sort работает за время O(n*k), где k -- длина строк (20 в случае
банковских идентификаторов).
Это тоже стабильная сортировка, так же как и MergeSort.
ПЕРЕРЫВ 10 минут до 12:30
Напишем тестовую программу для разных алгоритмов сортировки.
=======================================================
28 Mar 2022
Численное интегрирование
Численное вычисление производной функции.
f'(x) = lim_h->0 (f(x + h) - f(x))/h
Численное значение производной можно приближенно вычислить по формуле
f'(x) = (f(x + h) - f(x))/h
взяв небольшое значение h, например, h = 0.001
Как оценить точность вычисления по этой формуле?
Разложим f(x) в ряд Тейлора точке x:
f(x + h) = f(x) + f'(x)*h + f''(x)*h^2/2! + O(h^3)
f(x + h) - f(x) = f'(x)*h + O(h^2)
f'(x) = (f(x + h) - f(x))/h + O(h) -- очень низкая точность.
Оказывается, точность приближенного вычисления производной
можно на порядок увеличить, используя просто симметричную формулу:
f'(x) = (f(x + h) - f(x - h))/(2*h)
точность O(h^2)
Это так, потому что
f(x + h) = f(x) + f'(x)*h + f''(x)*h^2/2! + O(h^3)
f(x - h) = f(x) - f'(x)*h + f''(x)*h^2/2! + O(h^3)
f(x + h) - f(x - h) = f'(x)*(2*h) + O(h^3)
(f(x + h) - f(x - h))/(2*h) = f'(x) + O(h^2)
Мораль: для приближенного вычисления производной надо использовать
формулу
f'(x) = (f(x + h) - f(x - h))/(2*h),
где h -- небольшое число.
Перейдем к численному интегрированию.
Интеграл Римана определяется как предел интегральных сумм.
Формула прямоугольников соответствует тому, что на маленьком
отрезке разбиения мы берем значение ф-ции в левом конце отрезка.
Точность низкая, порядка h, где h -- величина отрезка разбиения.
точность O(h)
Точность ф-лы трапеций O(h^2)
Формула Симпсона (формула парабол).
Разбиваем отрезок интегрирования [a, b] на ЧЕТНОЕ число
маленьких отрезков равной длины. На каждой паре соседних отрезков
приближаем функцию параболой по трем точкам. И считаем
сумму площадей получившихся криволинейных трапеций.
Формула для площади криволинейной трапеции, ограниченной отрезком
параболы:
S = (y0 + 4*y1 + y2)/6 * (2*h)
где
y0 = f(x0)
y1 = f(x0 + h)
y2 = f(x0 + 2*h)
===================================================
4 Apr 2022
Квадратурные формулы (численное интегрирование)
Задача: дана числовая функция на отрезке f: [a, b] -> R
Надо вычислить приблизительно определенный интеграл от f(x)
по отрезку [a, b].
В прошлый раз мы рассмотрели формулу прямоугольников и
формулу трапеций.
Мы начали рассматривать формулу Симпсона (формула парабол).
Идея: мы разбиваем отрезок интегрирования [a, b] на ЧЕТНОЕ
число маленьких отрезков равной длины. На каждой паре соседних
отрезков мы приближаем функцию параболой (многочленом 2-й степени)
и вычисляем интергал от этого многочлена. Интеграл по всему отрезку
есть сумма интегралов по этим парам отрезков.
Главное, что нужно запомнить:
рассмотрим пару маленьких отрезков
x0, x1 = x0+h, x2 = x0+2*h
Пусть значения в этих точках равны
y0, y1, y2
Еще раз, есть узлы x0, x1, x2 и значения функции в этих узлах равны
y0, y1, y2:
y0 y1 y2
x0 x1 x2
Тогда интеграл от квадратного многочлена (площадь криволинейной трапеции)
S = ((y0 + 4*y1 + y2)/6) * (2*h)
Эта формула точна не только на многочленах 2-й степени, но и на многочленах
3-ей степени! (Доказательство: можно проверить ее на f(x) = x^3,
и так как ф-ла линейна относительно f, то она выполняется и на любой
линейной комбинации x^d, d <= 3.)
======================================================
Создание оконных и графических приложений в системе разработки Qt
Если у вас Linux -- установите Qt5 или Qt6
Если у ваc MS Windows -- надо перейти на сайт http://qt.io/
дальше --> Downloads --> Go Open Source --> download installator for 64-bit
Запускаете инсталлятор, выбираете Qt для MS Windows 64 bit
на базе MinGW-64 (ни в коем случае не MS Visual C++).
Qt + QtCreator
Qt Creator -- очень удобная оболочка для разработки приложений.
Она выглядит одинаково на всех операционных системах.
Код Qt-приложения не зависит от операционной системы.
Попробуем написать простую программу на Qt.
Программа рисует график функции в дочернем окне, мышкой отмечаем
точки в окне (рисуются крестики), есть две кнопки:
Draw -- рисует график функции,
Clear -- стирает всё, что нарисовано.