- •Общие сведения Сведения об эумк
- •Методические рекомендации по изучению дисциплины
- •Рабочая учебная программа Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники»
- •Пояснительная записка
- •Содержание дисциплины
- •1. Название тем лекционных занятий, их содержание, объем в часах Наименование тем, их содержание
- •2. Перечень тем ипр
- •Перечень тем контрольных работ
- •4. Литература
- •4.1 Основная
- •4.2 Дополнительная
- •5. Перечень компьютерных программ, наглядных и других пособий, методических указаний и материалов и технических средств обучения
- •6. Учебно-методическая карта дисциплины содержание дисциплины
- •Теоретический раздел Вступление
- •Дискретная и вычислительная математика
- •Часть 1. Вычислительная математика Математическое моделирование и вычислительный эксперимент
- •1 Решение систем линейных алгебраических уравнений
- •1.1 Точные методы
- •1.1.1 Метод Гаусса
- •1.1.2 Связь метода Гаусса с разложением матрицы на множители. Теорема об lu разложении
- •Теорема об lu разложении
- •1.1.3 Метод Гаусса с выбором главного элемента
- •1.1.4 Метод Холецкого (метод квадратных корней)
- •1.2 Итерационные методы решений систем алгебраических уравнений
- •1.2.1 Метод Якоби (простых итераций)
- •1.2.2 Метод Зейделя
- •1.2.3 Матричная запись методов Якоби и Зейделя
- •1.2.4 Метод Ричардсона
- •1.2.5 Метод верхней релаксации (обобщённый метод Зейделя)
- •1.2.6 Сходимость итерационных методов
- •2 Плохо обусловленные системы линейных алгебраических уравнений
- •2.1 Метод регуляризации для решения плохо обусловленных систем
- •2.2 Метод вращения (Гивенса)
- •3 Решение нелинейных уравнений
- •3.1 Метод простых итераций
- •3.1.1 Условия сходимости метода
- •3.1.2 Оценка погрешности
- •3.2 Метод Ньютона
- •3.2.1 Сходимость метода
- •4 Решение проблемы собственных значений
- •4.1 Прямые методы
- •4.1.1 Метод Леверрье
- •4.1.2 Усовершенствованный метод Фадеева
- •4.1.3 Метод Данилевского
- •4.1.4 Метод итераций определения первого собственного числа матрицы
- •5 Задача приближения функции
- •5.1 Интерполяционный многочлен Лагранжа
- •5.1.1 Оценка погрешности интерполяционного многочлена
- •5.2 Интерполяционные полиномы Ньютона
- •5.2.1 Интерполяционный многочлен Ньютона для равноотстоящих узлов
- •5.2.2 Вторая интерполяционная формула Ньютона
- •5.3 Интерполирование сплайнами
- •5.3.1 Построение кубического сплайна
- •5.3.2 Сходимость процесса интерполирования кубическими сплайнами
- •5.4 Аппроксимация функций методом наименьших квадратов
- •6 Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений и систем дифференциальных уравнений
- •6.1 Семейство одношаговых методов решения задачи Коши
- •6.1.1 Метод Эйлера (частный случай метода Рунге-Кутта)
- •6.1.2 Методы Рунге-Кутта
- •6.2 Многошаговые разностные методы решения задачи Коши для обыкновенных дифференциальных уравнений
- •6.2.1 Задача подбора числовых коэффициентов aк , bк
- •6.2.2 Устойчивость и сходимость многошаговых разностных методов
- •6.2.3 Примеры m-шаговых разностных методов Адамса для различных m
- •6.3 Численное интегрирование жестких систем обыкновенных дифференциальных уравнений
- •6.3.1 Понятие жесткой системы оду
- •6.3.2 Некоторые сведения о других методах решения жестких систем
- •6.3.2.1 Методы Гира
- •6.3.2.2 Метод Ракитского(матричной экспоненты) решения систем оду
- •6.4 Краевые задачи для обыкновенных дифференциальных уравнений
- •6.5 Решение линейной краевой задачи
- •6.6 Решение двухточечной краевой задачи для линейного уравнения второго порядка сведением к задаче Коши
- •6.7 Методы численного решения двухточечной краевой задачи для линейного уравнения второго порядка
- •6.7.1 Метод конечных разностей
- •6.7.2 Метод прогонки (одна из модификаций метода Гаусса)
- •7 Приближенное решение дифференциальных уравнений в частных производных
- •7.1 Метод сеток для решения смешанной задачи для уравнения параболического типа (уравнения теплопроводности)
- •7.2 Решение задачи Дирихле для уравнения Лапласа методом сеток
- •7.3 Решение смешанной задачи для уравнения гиперболического типа методом сеток
- •Часть 2. Дискретная математика
- •1. Основные Элементы теории множеств
- •1.1 Элементы и множества
- •1.2 Задание множеств. Парадокс Рассела
- •1.3 Операции над множествами
- •1.4 Булеан множества
- •1.5 Представление множеств в эвм
- •Разбиения и покрытия
- •2 Отношения и функции
- •2.1 Прямое произведение множеств
- •Элементы комбинаторики
- •Теория конфигураций и теория перечисления
- •Размещения
- •Сочетания
- •3.1 Перестановки и подстановки
- •4 Элементы математической логики
- •5 Конечные графы и сети Основные определения
- •5.1 Матрицы графов
- •Матрица смежности Списки инцидентности
- •5.2 Достижимость и связность
- •5.3 Эйлеровы и гамильтоновы графы
- •5.4 Деревья и циклы
- •5.5 Алгоритмы поиска пути
- •Двунаправленный поиск
- •Поиск по первому наилучшему совпадению
- •Алгоритм Дейкстры
- •АлгоритмА*
- •Остовное дерево
- •Матрица Кирхгофа
- •5.6 Конечные автоматы
- •5.6 Элементы топологии
- •5.7 Метрическое пространство
- •Указания по выбору варианта
- •Контрольная работа № 2 Общие сведения
- •Квадратурная формула Гаусса
- •Указания по выбору варианта
- •Индивидуальные практические работы Индивидуальная практическая работа № 1 Общие сведения
- •Интерполяционный полином Лагранжа
- •Аппроксимация функций с помощью кубического сплайна
- •Приближение формулами Ньютона
- •Аппроксимация функций методом наименьших квадратов
- •Индивидуальная практическая работа № 2
1.4 Булеан множества
Напомним, что число элементов конечного множества называется мощностью множества и обозначается символом A или Card A (от английского cardinality - мощность).
Определение. Множество всех подмножеств данного множества называют булеаном множества. Булеан обозначают символом B(A).
Пример. Пусть A = { 1,2,3 }. Перечислить элементы булеана множества A.
B(A)={ ,{ 1 },{ 2 },{ 3},{ 1,2 },{ 1,3 },{ 2,3},{ 1,2,3 } }.
Пример. Пусть A = { 1,2,3,4,...,n }, т.е. |A | = n. Найдем мощность множества B(A).
Для определения CardB(A) воспользуемся биномиальными коэффициентами Cnk (число сочетаний из n по k)4. Перечислим по порядку, начиная с пустого множества, все подмножества множества A:
пустому подмножеству множества A поставим в соответствие число 1 = Cn0;
булеан содержит одноэлементные подмножества:
-
{ 1 }, { 2 }, { 3 }, ..., {n}.
Число одноэлементных подмножеств равно n = Cn1;
булеан содержит следующие двухэлементные подмножества:
-
{ 1,2 },{ 1,3 },{ 1,4 }, ,{ 1,n },{ 2,3 },{ 2,4 }, ,{ 2,n },
{ 3,4 },{ 3,5 }, ,{ 3,n }, ,{ n 2,n 1 },{ n 2,n },{ n 1,n}.
Количество двухэлементных подмножеств равно
-
n(n 1)
2
= Cn2 ;
продолжая этот подсчет, получим, что булеан содержит Cn3 трехэлементных подмножеств, Cn4 четырехэлементных подмножеств и так далее;
наконец, мы отметим, что булеан содержит Cnn 1 (n 1)-элементных подмножеств и одно n-элементное подмножество - само множество A, которому мы сопоставим биномиальный коэффициент Cnn = 1.
В результате сумма всех биномиальных коэффициентов покажет нам количество элементов булеана B(A):
-
2n = (1 + 1)n = Cn0 + Cn1 + Cn2 + ... + Cnn 1 +Cnn .
Таким образом, для любого множества A, если Card A = n, то Card B(A)=2n.
1.5 Представление множеств в эвм
Для конечного универсума, мощность которого не превосходит разрядности машинного слова, подмножества универсума могут представляться битовой шкалой (аналог характеристической функции – 0 или 1 для каждого элемента). Битовая шкала имеет размерность универсума, и для каждого подмножества число единиц в соответствующей ему битовой шкале определяется мощностью этого подмножества. Если элемент входит в подмножество, то ему соответствует 1, иначе 0. Тогда операции над подмножествами осуществляются посредством поразрядных логических операций
Если универсум велик, а подмножества имеют сравнительно небольшую мощность, то использование характеристических функций невыгодно, т.к. в них будет много нулей. Для представления таких множеств обычно используют списки элементов. Элемент множества тогда может быть представлен записью с двумя полями: информационным и указателем на следующий элемент. Трудоемкость операций включения, пересечения и объединения определяется как O(m× n), где m и n – мощности множеств; операции Î – как O(n).
При использовании списков, упорядоченных по информационному полю, трудоемкость всех операций является линейной (О(n)). В таком случае эффективная организация всех операций над множествами основана на общем алгоритме, известном как алгоритм типа слияния.
Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение вперед (увеличение номера рассматриваемого элемента) происходит в том множестве, в котором текущий элемент меньше.
В качестве простейшей организации множеств можно использовать упорядоченный массив элементов.
Проверка включения AÌ B
Вход: Два упорядоченных множества A и B (массивы).
Выход: да или нет (1 или 0, true или false).
i:=1; j:=1; // указатели на начало множеств
пока i < |A|+1 и j < |B|+1 цикл
если A[i] < B[j] то вернуть 0 и выход
// элемент A отсутствует в B
иначе
если A[i] > B[j] то j:=j+1
// переход к след. элементу B
иначе
// элементы совпали – перейти к следующим
i:=i+1; j:=j+1;
конец если
конец цикла
если i=|A|+1 то вернуть 1, иначе вернуть 0.
Алгоритмы, вычисляющие объединение множеств, пересечение и дополнение устроены совершенно аналогичным образом. Общее действие – продвижение вперед (увеличение индекса) в том массиве, элемент которого меньше, и сразу в обоих, если элементы равны.
Для определения объединения в результирующее множество заносятся каждый из меньших элементов и один, если они равны. Если конец одного из множеств достигнут раньше, все оставшиеся элементы другого дописываются в конец итогового множества.
Для определения пересечения в результирующее множество заносится тот элемент, который совпал у обоих множеств. Если конец одного из множеств достигнут раньше, работа алгоритма заканчивается.