Классические алгоритмы математики и их сложность

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

а) решение квадратного уравнения;

б) вычисление определителя 2х2, 3х3, 4х4, nxn;

в) решение системы линейных уравнений 2х2, 3х3, nxn по правилу Крамера;

г) приведение квадратной матрицы 2х2, 3х3, 4х4, nxn к треугольному виду;

д) решение системы линейных уравнений 2х2, 3х3, 4х4, nxn методом Гаусса;

28. Формальные исчисления

28.1. Задать формально дифференциальное исчисление функций одной переменной.

28.2. Задать формально интегральное исчисление функций одной переменной.

ДОПОЛНИТЕЛЬНЫЕ РАЗДЕЛЫ ДИСКРЕТНОЙ

МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ЛОГИКИ

29.Метод математической индукции

Суть метода в том, что некоторое утверждение, в котором участвует натуральное число n, проверяется для n=1 (база индукции), а затем совершается индукционный переход одним из двух способов: 1) если утверждение верно для n=k, то оно верно и для n=k+1. 2) если утверждение верно для n£ k, то оно верно и для n=k+1.

29.1. (Неполная индукция) Верно ли, что n²–n+41 является простым числом при всех nÎ N?

29.2. Доказать, что n³–n делится на n при всех nÎ N.

29.3. Доказать, что а) при всех nÎ N;

б) при всех nÎ N.

29.4. В шеренге n солдат. Доказать, что их можно переставить n! = 1×2×3×...×n способами.

30. Диофантовы уравнения

Пифагорова тройка – это тройка натуральных чисел x,y,z, удовлетворяющих «теореме Пифагора» x²+y²=z². Таких троек бесконечно много.

30.1. Найти все целые корни уравнения x⁴+x³–13x²–7x+42=0.

30.2. Среди пифагоровых троек найти все, у которых z =y+1.

30.3. Найти все несократимые пифагоровы тройки, у которых z=y+2.

30.4. То же, но z=y+3.

30.5. Решить в натуральных числах уравнения:

а) x² – y²=15; б) x³ = y³ + 61; в*) 2^x – y²=1;

31. Рекуррентные уравнения

Для нелинейных РУ нет универсального алгоритма, находящего формулу общего члена последовательности { a_n }, или хотя бы выясняющего, существует ли ее предел. На практике для этого часто приходится проводить численный эксперимент. Другой важный практический прием: предположив, что предел существует и равен x, получают из РУ обычное уравнение для x. Для линейных РУ имеется удобный алгоритм, использующий характеристические корни.

31.1. Дано РУ 1-го порядка с начальным условием a_n =2.

Доказать, что a_n имеет предел и найти его.

31.2. Найти формулу n -го члена последовательности, заданной линейным РУ

2-го порядка с начальными условиями:

а) a_n+2=4 a_n+1 –3 a_n; a₁=1; a₂=2;

б) a_n+2=6 a_n+1 –9 a_n; a₁=1; a₂=2.

32. Цепные дроби

32.1. Выяснить, к какому числу сходится данная цепная дробь.

а) ; б) .

ЛИТЕРАТУРА

1. Пугач, Л.И. – Задачи по дискретной математике: Методические указания для студентов 1 курса БГТУ/ Л.И. Пугач. – Брянск, БГТУ, 2000.– с. 1-12.

2. Горбатов, В.А.– Основы дискретной математики./В.А.Горбатов – М., 1993.

3. Элементы дискретной математики: учебное пособие для вузов.–

/К.Г. Гараев [и др].– Казань: КазГУ, 2000.

4. Яблонский, С.В..– Введение в дискретную математику./ С.В.Яблонский –

М.: Высш. Шк., 2001.

5. Гаврилов, Г.П. Задачи и упражнения по курсу дискретной математики.

/ Г.П. Гаврилов, А.А.Сапоженко А.А. М., Наука, 1992.

6. Дискретная математика для программиста. – С-Пб., 2000.

7. Кузнецов, О.П. Дискретная математика для инженера. /О.П.Кузнецов, Г.М.Адельсон-Вельский.– М., 1995.

8. Берж, К. Основы теории графов /К.Берж – М.:Мир, 1980.

9. Ершов, А.П. Дискретная математика и ее применение в программировании.

/ А.П. Ершов и др. – Новосибирск, 1992.

10. Гиндикин, С.Г. Алгебра логики в задачах./ С.Г.Гиндикин.– М., 1991.

11. Непейвода, Н.Н. Прикладная логика./Н.Н.Непейвода.– Ижевск, 1997.

12. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов

/ Н.К.Верещагин, А.А.Шень.– М., изд. МЦ НМО, 2000.

13. Воротников, С.М. Введение в математическую логику/С.М.Воротников.– Комсомольск-на-Амуре, 1996.

Дата добавления: 2015-07-11