Факультет фундаментальной
физико-химической инженерии

Информатика, численные методы и программирование

2023-24 учебный год

Зачет в семестре и его оценка ставится как результат решения задач по указанным темам. Пожалуйста, присылайте мне решения (файлы с программами, присоединенные к письму) по электронной почте на адрес
vladibor2016 (собака) yandex.ru


Прошлый 2022-23 учебный год


Материалы 1-го курса

Материалы 2-го курса

1-й курс

1-й семестр (2022-23 уч. год)

Тексты лекций на "виртуальной доске", прочитанных в прошлом году (2021-22)

2-й семестр

Тексты прочитанных лекций на "виртуальной доске"
(группа 102, весенний семестр 2021-22 учебного года).


2-й курс

3-й семестр

Тема 1: классы в С++

1.1. Классы для поддержки двумерной и трехмерной графики и их использование для решения геометрических задач

Для вычислений на плоскости R2 используются классы R2Vector (вектор на плоскости с вещественными координатами) и R2Point (точка на плоскости). В пакете "R2Graph.zip" реализованы все основные операции на плоскости.

Простой пример программы, использующей классы R2Point и R2Vector и потоковый ввод-вывод в стиле C++: ввести вершины треугольника и вычислить центр и радиус вписанной окружности. При вычислении запрещено использовать координаты векторов и точек, следует пользоваться исключительно методами классов R2Point и R2Vector. Файл "inCircle.cpp". Программа использует модуль R2Graph, в котором определяются классы для поддержки геометрии на плоскости: файлы "R2Graph.h" и "R2Graph.cpp". Архив всех файлов: InCircle.zip

Задачи:
написать консольное приложение, в котором вводятся 3 точки треугольника и вычисляется

1) точка Нагеля треугольника

(пересечение отрезков, соединяющих вершины треугольника с точками касания внешне-вписанных окружностей);

2) точка Лемуана треугольника

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

Студенты с нечетными номерами по журналу делают первую задачу, с четными — вторую.

Трехмерная геометрия: координаты на поверхности Земли и на карте

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

Рассмотрим классическую задачу определения расстояния между двумя точками на поверхности Земли (приблизительно считаем поверхность Земли сферой). Самый простой способ ее решения — это найти угол между радиус-векторами, проведенными из центра Земли к этим точкам, и умножить его на радиус Земли. В классе R3Vector имеется метод angle, возвращающий угол между векторами, мы им воспользуемся. Все, что нам нужно — это реализовать функцию, определяющую радиус-вектор единичной длины, проведенный из центра Земли в направлении заданной точки.

Для представления векторов и точек на поверхности Земли мы используем декартову систему координат, у которой начало координат расположено в центре Земли. Ось x направлена из центра в точку перечесения экватора и гринвичского меридиана, ось z направлена на северный полюс, ось y перпендикулярна осям z и x и направлена на восток.

Радиус-вектор единичной длины, направленный из центра земли в точку с широтой и долготой (lat, lon), получается из базисного вектора ex двумя поворотами: первый поворот на угол lat выполняеся вокруг оси z, второй поворот на угол lon выполняется в меридиональной плоскости. После первого поворота мы получаем вектор

v0 = (cos(φ), sin(φ), 0)
где φ — долгота lon в радианах. После второго поворота на угол lat в меридиональной плоскости координаты x и y вектора v0 умножаются на cos(θ), где θ — широта lat в радианах, а координата z равна sin(θ):
v1 = (cos(φ)cos(θ), sin(φ)cos(θ), sin(θ))
Вот реализация функции radiusVector, вычисляющий радиус вектор единичный длины, проведенный из центра Земли в точку с координатами (lat, lon) — широтой и долготой в градусах:

R3Vector radiusVector(double lat, double lon) {
    double phi = lon*PI/180.;   // Convert to radians
    double theta = lat*PI/180.;
    
    // Rotate ex around ez by angle phi: v0 = (cos(phi), sin(phi), 0.)
    // Rotate v0 in meridional plane by angle theta:
    // v1 = (cos(phi)*cos(theta), sin(phi)*cos(theta), sin(theta))
    double cosTheta = cos(theta);
    return R3Vector(cos(phi)*cos(theta), sin(phi)*cos(theta), sin(theta));
}
(здесь используется константа PI = π, определенная ранее в тексте).

Полный текст программы: "earthdist.cpp". Проект использует также файлы "R3Graph.h" и "R3Graph.cpp", команда для компиляции проекта в Linux'е:

    g++ -o earthdist earthdist.cpp R3Graph.cpp
Архив всех файлов: "earthdist.zip".

Задачи на использование классов в R3-графике

Карта представляет собой касательную плоскость к земной сфере. Положение карты задается координатами ее центра: (широта центра, долгота центра). Для представления точек поверхности сферы на карте используется центральная проекция с центром в центре земного шара. На карте используется декартова система координат, в которой ось Y направлена на север (касательная к меридиану, проходящему через центр карты), ось X перпендикулярна оси Y и направлена на восток. Нужно решить одну из следующих двух задач (студенты с нечетными номерами решают 1-ю задачу, с четными — вторую).
  1. Заданы координаты центра карты (mlat, mlon) и координаты точки на земной поверхности (lat, lon) в градусах. Получить координаты проекции этой точки на карте (x, y) в метрах.
  2. Заданы координаты центра карты (mlat, mlon) и координаты точки (x, y) на карте в метрах. Получить координаты точки на поверхности Земли (lat, lon) в градусах, которая проецируется в данную точку на карте.

Задачи на замену

Нужно сделать одну задачу из трех, ее номер должен совпадать с номером студента по журналу по модулю 3.

  1. Дан тетраэдр (треугольная пирамида, задается 4-мя вершинами в R3). Найти центр и радиус описанной сферы. Нужно реализовать алгоритм в виде отдельной функции, а также написать тестирующую программу. Прототип функции:
       void curcumSphere(
           const R3Graph::R3Point tetrahedron[4],
           R3Graph::R3Point& center,
           double& radius
       );
    
  2. Дан тетраэдр (треугольная пирамида, задается 4-мя вершинами в R3). Найти центр и радиус вписанной сферы. Нужно реализовать алгоритм в виде отдельной функции, а также написать тестирующую программу. Прототип функции:
       void inscribedSphere(
           const R3Graph::R3Point tetrahedron[4],
           R3Graph::R3Point& center,
           double& radius
       );
    
  3. Дан тетраэдр (треугольная пирамида, задается 4-мя вершинами в R3) и плоскость, которая задается точкой и нормальным вектором. Вычислить выпуклый многоугольник в пересечении этой плоскости с тетраэдром (это может быть либо треугольник, либо четырехугольник), т.е. получить массив его вершин и число элементов массива (не больше 4-х), причем точки должны идти в порядке против часовой стрелки, если смотреть на плоскость из конца вектора нормали. Нужно реализовать алгоритм в виде отдельной функции, а также написать тестирующую программу. Прототип функции:
        bool intersectTetrahedron(
            const R3Graph::R3Point tetrahedron[4], // Тетраэдр
            const R3Graph::R3Point& p,       // Точка плоскости
            const R3Graph::R3Point& normal,  // Нормаль к плоскости
            int& numVertices,                // Число вершин многоугольника
            R3Graph::R3Point intersection[4] // Многоугольник в пересечении
        );
    
    Функция должна возвращать true, если пересечение непусто, и false в противном случае.

1.2. Реализация классов на C++

Пример 1: реализация класса Complex —
файлы "Complex.h", "Complex.cpp", тестирующая программа "complexTst.cpp", "Makefile" для сборки проекта, архив всех файлов "Complex.zip".

Пример 2: реализация класса Matrix (частичная) —
файлы "Matrix.h" (вариант "stdMatrix.h", использующий стандартный контейнер std::vector<double>), "Matrix.cpp", тестирующая программа "matrixTst.cpp", "Makefile" для сборки проекта, архив всех файлов "Matrix.zip".

Приведенная реализация класса Matrix намерено не доведена до конца, чтобы оставить возможность решения задач.


Список задач по теме "Реализация классов"

  1. Реализовать класс Complex, представляющий комплексные числа. При этом требуется использовать внутреннее представление комплексных чисел в экспоненциальной форме:
    z = r·eiφ
    Воспользовавшись этим классом, написать программу, решающую кубическое уравнение с помощью формулы Кардано (или чего-то похожего). Описание см. в статье Решение кубического уравнения. Коэффициенты кубического уравнения можно считать комплексными или только вещественными, как вам больше нравится.
  2. Реализовать класс Polynomial, представляющий многочлен произвольной степени с коэффициентами в поле вещественных чисел. Должны быть реализованы операции сложения, умножения, деления с остатком, вычисление наибольшего общего делителя многочленов, производной многочлена, а также вычисление многочлена с теми же корнями, свободного от кратных корней, т.е. частного от деления многочлена f на gcd(f, f').
  3. Реализовать класс "Матрицы порядка m×n над полем вещественных чисел". Должны быть реализованы операции +, -, * над матрицами, приведение матрицы к ступенчатому виду, вычисление ранга, а также для квадратной матрицы вычисление определителя и обратной матрицы и решение линейной системы с невырожденной матрицей.
  4. Реализовать класс Polygon, представляющий замкнутую несамопересекающуюся ломаную на плоскости, т.е. невыпуклый многоугольник. Реализация должна использовать классы R2Point и R2Vector, описанные в пакете R2Graph.h, (архив всех файлов R2Graph.zip). Вершины многоугольника должны храниться в виде объектов типа R2Point. Должны быть реализованы операции получения вершины многоугольника по ее индексу, получения числа вершин, добавления вершины в конец, нахождения периметра, площади, центра тяжести вершин и центра тяжести плоской фигуры, проверки того, что точка находится внутри многоугольника.
  5. Реализовать класс "Real" (вещественное число), использующий представление вещественного числа в форме с фиксированной десятичной точкой. Число представляются с точностью до 10-3 в виде
    m·10-3
    где m — целое число. Реализация всех методов должна использовать исключительно целочисленную арифметику. В числе прочих должны быть реализованы методы
        class Real {
            . . .
            Real(int intPart = 0, int fractionPart = 0);
            Real(const char *string);
            Real sqrt() const;
            static Real fromString(const char *str);
            char* toString(char* string, int maxLen) const;
            . . .
        };
        
    В качестве тестовой программы написать программу решения квадратного уравнения, корни находятся с точностью 0.001.

Проект "Стековый калькулятор"

Архив файлов проекта: stdStackCalc.zip (файлы Stack.h, StackCalc.cpp).

Задача по проекту "Стековый калькулятор": добавить команды pi, e (математические константы), gcd (наибольший общий делитель), fastpow (быстрое возведение в целую неотрицательную степень), powmod (x^y (mod m) для целых чисел, y≥0, m>0).

Контейнерные классы в стандартной библиотеке C++

Механизм шаблонов (template) в C++. Контейнерные классы, реализующие популярные структуры данных в стандартной библиотеке С++: std::vector<Type>, std::deque<Type>, std::set<KeyType>, std::map<KeyType, ValueType>. Итераторы и их использование для реализации
    цикла для каждого элемента x структуры данных выполнить
        действие(x)
Программа "Телефонная книга", реализованная с помощью класса
    std::map<std::string, std::string>
— файл "notebook.cpp".

Класс std::deque, идея его реализации и примеры использования.

Алгоритмы в стандартной библиотеке C++

Помимо стандартных контейнеров, в стандартной библиотеке STL языка C++ содержится также набор функций, реализующих типичные алгоритмы. Эти функции также являются шаблонами, т.е. зависят от параметров, заданных с помощью ключевого слова template. Это означает, что, например, функция сортировки sort может применяться для любых типов данных (базовых типов языка C/C++ или классов), поддерживающих сравнение элементов с помощью знака меньше "<".

Все стандартные алгоритмы описаны в заголовочном файле algorithm, который подключается с помощью строки

#include <algorithm>

Отметим некоторые общие черты множества функций, содержащихся в стандартной библиотеке.

  1. Как правило, функции из стандартной библиотеки работают с некоторым отрезком последовательности элементов. Это может быть, например, целиком массив в стиле языка C, динамический массив (vector) в C++, список, дек и т.п., либо сегмент массива, списка и т.п., который задается двумя итераторами, указывающими на начальный элемент сегмента и элемент, следующий за конечным элементом сегмента. Таким образом, функция принимает в качестве первых двух аргументов два итератора, задающих сегмент структуры данных, к которому она применяется. Например, пусть динамический массив определяется в следующей строке:
        std::vector<int> a = { 10, 20, 77, 33, 45, 88, 99, 19 };
    
    Чтобы упорядочить весь массив, надо вызвать функцию sort, передав ей итераторы, указывающие на начало и за-конец массива:
        std::sort(a.begin(), a.end());
    
    Если же мы хотим упорядочить лишь отрезок массива, начинающийся с элемента 77 и заканчивающийся элементом 88 включительно, то нужно использовать следующую команду:
        std::sort(a.begin() + 2, a.begin() + 6);
    
    Здесь итератор a.begin()+2 указывает на элемент массива a с индексом 2, т.е. на 77; итератор a.begin()+6 указывает на элемент массива a с индексом 6, т.е. на 99 — это элемент, непосредственно следующий за элементом 88, который является последним элементом в сортируемом отрезке.
  2. Для того, чтобы произвести некоторое элементарное действие с элементами (например, сравнить два элемента), функции, выполняющей алгоритм, можно передать либо функцию, выполняющую это элементарное действие, либо объект некоторого класса, который также выполняет требуемое действие. В последнем случае для этого класса должен быть определен оператор "круглые скобки": operator()(...). Рассмотрим, например, сортировку массива целых чисел Во втором случае мы используем функцию, сравнивающую два элемента по их абсолютной величине, в третьем случае — объект, сравнивающий остатки от деления элементов на фиксированное целое число m, причем m хранится внутри этого объекта. Соответствующая программа записана в файле "cmp.cpp".

    В первом случае мы просто сортируем массив b (копию начального массива a) по величине чисел:

        std::vector<int> a = {
            1, -10, 22, 36, -57, 102, 17, 19, 28, 15,
            12, 18, -121, 343, -561
        };
    
        std::vector<int> b = a;
        std::sort(b.begin(), b.end());
    

    В втором случае мы сортируем массив b по абсолютной величине чисел, используя функцию сравнения cmp_abs:

        b = a;
        std::sort(b.begin(), b.end(), cmp_abs);
    
    Функция cmp_abs определена следующим образом:
    bool cmp_abs(int i0, int i1) {
        return (abs(i0) < abs(i1));
    }
    

    В третьем случае сравнение двух целых чисел по их остаткам при делении на фиксированное число m выполняет объект класса CmpMod, число m=10 задается в конструкторе этого класса:

        b = a;
        std::sort(b.begin(), b.end(), CmpMod(10));
    
    Класс CmpMod определен следующим образом:
    class CmpMod {
        int m;
    public:
        CmpMod(int mm = 5):
            m(mm)
        {}
    
        bool operator()(int i0, int i1) const {
            int r0 = i0 % m;
            if (r0 < 0)
                r0 += m;
            int r1 = i1 % m;
            if (r1 < 0)
                r1 += m;
            return (r0 < r1);
        }
    };
    

    Вот результат работы программы:

    Initial array:
    1 -10 22 36 -57
    102 17 19 28 15
    12 18 -121 343 -561
    ----
    Sorted by value:
    -561 -121 -57 -10 1
    12 15 17 18 19
    22 28 36 102 343
    ----
    Sorted by absolute value:
    1 -10 12 15 17
    18 19 22 28 36
    -57 102 -121 343 -561
    ----
    Sorted by residues modulo 10:
    -10 1 22 102 12
    -57 343 15 36 17
    28 18 19 -121 -561
    ----
    

Обработка текстов

Программа нахождения множества слов в тексте на английском языке использующем кодировку ASCII: "words.cpp". Для каждого слова определяется количество его вхождений в текст. В результате печатается список слов, упорядоченных по количеству вхождений слов в текст, а для слов с одинаковым числом вхождений — лексикографически.

Программа "words.cpp". использует классы std::map, std::string, std::vector и алгоритм std::stable_sort.

Но рассмотренную выше программу "words.cpp" нельзя использовать для текстов на русском языке или любом другом языке, отличном от английского, поскольку стандартная библиотека STL языка С++ не поддерживает ни работу с UNICODE-символами, ни современную кодировку текстов в файлах UTF-8. Для работы с UNICODE и с UTF-8 мы используем самостоятельно написанный пакет функций utf8: "utf8.h", "utf8.cpp".

С использованием этого пакета, а также стандартных контейнерных классов и алгоритмов из библиотеки STL, реализована программа нахождения множества русских слов в тексте: "rusWords.cpp". Для каждого слова определяется количество его вхождений в текст. В результате печатается список слов, упорядоченных по количеству вхождений слов в текст, а для слов с одинаковым числом вхождений — лексикографически.

Программа "rusWords.cpp" использует классы std::map, std::basic_string, std::vector и алгоритм std::sort из стандартной библиотеки, а также функции для работы с Unicode-символами в кодировке UTF-8 — файлы "utf8.h", "utf8.cpp". Архив всех файлов проекта: "rusWords.zip".

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

Программа нахождения частот русских букв в тексте на русском языке: "ruschars.cpp", она также использует пакет функций "utf8". Архив всех файлов: "ruschars.zip".

Список задач на тему "Обработка текстов"

  1. Найти и упорядочить множество пар соседних слов в тексте на русском языке, использующем кодировку UTF8. Два соседних слова образуют пару, если между ними нет знаков препинания и других символов, кроме пробелов, переводов строк и дефисов. Пары слов упорядочиваются по количеству вхождений в текст, а для пар с равным числом вхождений — лексикографически. Напечатать 500 самых часто встречающихся пар.
  2. Найти и упорядочить множество биграмм в тексте на русском языке, использующем кодировку UTF8, и напечатать их список, упорядоченный по частотам вхождения в текст. (Биграмма — это сочетание двух идущих подряд русских букв.) Нужно напечатать только первые 100 биграмм.)

Программирование в среде Qt

Qt (Quazar Technology) — самая современная и самая лучшая среда для разработки C++ приложений. К достоинствам Qt относятся:

1) независимость текста программы от компьютера и операционной системы — исходные коды приложения одинаковы в Linux, MS Windows, Mac OS-X, и любых других современных операционных системах. В Qt можно создавать программы как для обычных компьютеров (Desktop), так и для операционных систем мобильных телефонов;

2) удобство программирования оконных и параллельных приложений благодаря удачному механизму сигналов и слотов;

3) поддержка огромного набора файловых форматов, сетевых протоколов и устройств;

4) программы на Qt, как правило, намного эффективнее, чем программы, подготовленные в других средах или на других языках, благодаря тому, что исполняющая система Qt автоматически учитывает особенности каждого конкретного компьютера и, к примеру, выбирает самый эффективный метод реализации графики (как правило, через трехмерный интерфейс, если в компьютере есть современная графическая карта);

5) Qt имеет очень удобную среду разработки qtcreator, которая позволяет редактировать оконные формы и добавлять обработчики сигналов, посылаемых управляющими элементами окон; qtcreator синхронно вносит изменения в h- и cpp-файлы.

Qt использует небольшое расширение базового языка C++ — добавлены ключевые слова signal, emit, slot, connect. Сигналы посылаются, например, управляющими элементами окон (для посылки сигнала используется ключевое слово emit). Слоты — это методы, предназначенныедля приема и обработки сигналов. С помощью вызова connect можно связать сигнал, посылаемый некоторым объектом, с обрабатывающим его слотом. При этом обработка выполняется не сразу путем вызова функции, а с помощью постановки сообщения о сигнале в очередь для последующей обработки объектом, принимающим этот сигнал. Такой способ гораздо более гибкий и безопасный, что важно при асинхронной обработке событий в многопоточных программах с параллельным исполнением нескольких нитей. Специальная утилита moc (Meta-Object Compiler) переводит программу с расширения языка С++ на чистый С++. Qt, в отличие от С++ варианта языка CLR-C++ (Сommon Language Runtime), являющегося частью платформы .Net фирмы Microsoft, не использует управляемую динамическую память и сборщик мусора. Благодаря этому Qt-программы быстрее, более надежны и тратят меньше памяти при выполнении, что позволяет использовать их в системах реального времени.

В Qt в основном разрабатываются оконные графические программы. Примеры несложных проектов:

Qt-проект "График функции"
Изображается график функции, заданной непосредственно в тексте программы. Также в точках, отмечаемых кликами мыши, рисуются крестики, цвета которых задаются номером кнопки мыши (всего три цвета для трех кнопок):
PlotFunc.zip

Qt-проект "График интерполяционного многочлена"
Пользователь кликами мыши задает узлы интерполяции, которые отмечаются крестиками. По нажатию на клавишу "Draw" программа рисует график интерполяционного многочлена, построенного по этим узлам (вычисляется многочлен в форму Ньютона).
Узлы можно захватывать и перетаскивать мышью, при этом график многочлена изменяется в реальном времени:
NewtonPol.zip

Задачи на тему Qt

В задачах 2-5 надо нарисовать треугольник, задаваемый кликами мыши, и одну из замечательных точек треугольника, определяемых как пересечение чевиан. Нарисовать надо не только саму точку (в виде маленького закрашенного кружка), но и процесс ее построения. Нужно сделать одну задачу, номер которой совпадает по модулю 5 с номером студента по журналу.

В качестве образца дается Qt-проект "Triangle.zip", в котором по трем кликам мыши изображается треугольник, его три биссектрисы и вписанная окружность:

Список задач

  1. Пользователь отмечает кликами мыши 4 точки A, B, C, D, координаты x которых строго возрастают. Построить график кубического многочлена, обладающего следующими свойствами:

    Указание: такой кубический многочлен удобно вычислять в форме Ньютона. Обозначим A.x=x0, D.x=x1. Нужно найти коэффициенты ai в представлении многочлена
         p(x) = a0 + a1(x-x0) + a2(x-x0) (x-x1) + a3(x-x0)2 (x-x1).

  2. Нарисовать треугольник и точку Жергона — пересечение отрезков, соединяющих вершины треугольника с точками касания вписанной окружности.
  3. Нарисовать треугольник и точку Нагеля — пересечение отрезков, соединяющих вершины треугольника с точками касания трех внешне вписанных окружностей.
  4. Нарисовать треугольник и точку Лемуана — точку, изогонально сопряженную центру тяжести треугольника. Она определяется как пересечение симмедиан. Симмедиана — это отрезок прямой, симметричной медиане треугольника относительно бисектриссы, проведенной из той же вершины.

    На рисунке синяя точка — это пересечение медиан треугольника. Медианы изображены синим цветом, биссектрисы — зеленым, симмедианы — красным. Точка Лемуана изображена красным кружком.
  5. Нарисовать треугольник и точку Ферма-Торричелли. Точка Ферма-Торричелли минимизирует сумму расстояний до вершин треугольника. Если треугольник остроугольный или даже тупоугольный, но с тупым углом, меньшим 120 градусов, то это точка, из которой каждая из сторон треугольника видна под углом 120 градусов. Для тупоугольного треугольника с углом 120 градусов и больше это вершина тупого угла.

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

4-й семестр (весна 2022)

Тексты прочитанных лекций на "виртуальной доске"
(группа 202, весенний семестр 2021-22 учебного года).

Журнал группы химиков, 2 курс, 4 семестр 2022-23.