Нетрадиционный подход к решению классической задачи о суммах двух квадратов, приводящий к важным оптимальным алгоритмам
Проведение исследования отличий в вычислении наибольшего общего делителя. Характеристика эффективного алгоритма спуска-подъема для подсчитывания явной формы PR-решения, заданного в неявной форме. Особенность формирования индуктивного предположения.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 21.01.2018 |
| Размер файла | 95,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ФГОУ ВПО «Московский государственный университет природообустройства»,
НЕТРАДИЦИОННЫЙ ПОДХОД К РЕШЕНИЮ КЛАССИЧЕСКОЙ ЗАДАЧИ О СУММАХ ДВУХ КВАДРАТОВ, ПРИВОДЯЩИЙ К ВАЖНЫМ ОПТИМАЛЬНЫМ АЛГОРИТМАМ
В.Г. Мотанов
И.В. Мотанова
г. Москва
В теории чисел широко известна следующая классическая задача.
Задача 1. Найти все целочисленные решения (x,y) уравнения
x2 + y2 = p,
где p - натуральное число.
Уравнение (1) будем называть разрешимым, если оно имеет целочисленные решения, и неразрешимым в противном случае.
Если натуральное число p задано, то, прежде всего, возникает следующая задача.
Задача 2. Выяснить разрешимо или неразрешимо уравнение (1).
Классическое решение этой задачи было дано Ферма ещё в 1638 г. Он показал, что уравнение (1) разрешимо тогда и только тогда, когда все простые делители p вида 4т + 3 входят в p в чётной степени. Таким образом, для проверки разрешимости уравнения (1) необходимо знать разложение числа p напростые множители. Но разложение числа на множители является одной из центральных задач в теории вычислительной сложности и относится к трудно решаемым задачам [1]. Поэтому, указанные необходимые и достаточные условия Ферма в вычислительном аспекте совершенно не эффективны, так как базируются на разложении числа p на простые множители. Кроме того, даже установив разрешимость уравнения (1), для решения задачи 1 неизвестны алгоритмы, существенно отличающиеся от алгоритмов полного перебора вариантов.
Принципиальное отличие, излагаемого далее нетрадиционного подхода к решению задач типа задач 1 или 2 от традиционного, состоит в том, что при этом подходе никак не используется разложение числа p на простые множители. Это отличие сопоставимо с отличием в вычислении наибольшего общего делителя (НОД) двух чисел следующими двумя способами:
1) разлагаем два числа на простые множители. Тогда НОД равен произведению общих простых множителей этих чисел;
2) вычисляем НОД с помощью алгоритма Эвклида.
Преимущества второго способа очевидны, так как не требуют разложения чисел на простые множители. Традиционный подход к решению задачи 2 сопоставим с первым способом, а предлагаемый нами нетрадиционный подход - со вторым.
Через D(x,y) будем обозначать НОД чисел х,у.
Определение. Решение (х0,у0) уравнения (1) будем называть неприводимым (или, более коротко, Н-решением), если D(x0,y0) = 1 и приводимым, если D(x0,y0) > 1.
Легко видеть, что достаточно ограничиться только нахождением Н-решений уравнения (1), так как, если (х0,у0) приводимое решение уравнения (1), то есть х0 = dх1, у0 = dу1, где d > 0, то в этом случае очевидно, что p делится на d2 и решение (х0,у0) может быть получено из Н-решения (х1,у1) уравнения х2 + у2 = p1, где p1 = p/d2, следующим образом х0 = dх1, у0 = dу1.
Определение. Уравнения (1), имеющие Н-решения будем называть Н-уравнениями.
Таким образом, Н-решения Н-уравнений вида (1) можно рассматривать как решения-атомы, из которых простой операцией (умножением на любое целое число) может быть получено любое приводимое решение уравнения вида (1).
Следовательно любое приводимое решение уравнения вида (1) кратно некоторому Н-решению некоторого Н-уравне-ния вида (1). В этом смысле задача вычисления всех решений уравнения вида (1) сводится к задаче вычисления всех Н-решений всех Н-уравнений. Этой последней задачей мы в основном и будем заниматься.
Определение. Решение (х0,у0) уравнения (1) будем называть положительным, если х0 > 0, у0 ? 0.
Очевидно, что, если уравнение (1) имеет решения, то оно имеет и положительное решение. Ясно также, что достаточно ограничиться поиском только всех положительных Н-решений Н-уравнения (1), что мы и сделаем, то есть в дальнейшем под Н-решением Н-уравнения (1) будем понимать только положительные Н-решения.
Нашей целью является получение оптимального решения следующего варианта классической задачи.
Основная задача
Составить список всех H-уравнений вида (1), у которых p < Рmax и вычислить все H-решения этих уравнений.
Известно (см. [2]), что уравнение (1) имеет Н-решения тогда и только тогда, когда найдётся такое r с условиями
.
При этом число Н-решений (напоминаем, что под Н-решением подразумеваются только положительные Н-решения) Н-уравнения (1) с фиксированным p равно числу решений сравнения (2), в котором r неизвестное. Таким образом, имеет место взаимно однозначное соответствие между Н-решениями Н-уравнения (1) с фиксированным p и решениями сравнения (2).
Определение. Если для Н-уравнения (1) найдено некоторое решение сравнения (2) (то есть p и r, удовлетворяющие (2), зафиксированы), то единственное Н-решение Н-уравне-ния (1), определяемое числами p и r, назовём PR-реше-нием, а числа p и r - параметрами этого PR-решения.
Удобно всё множество PR-решений разбить на уровни, которые мы перенумеруем натуральными числами и обозначим: U1, U2, ... ,Un, ... .
Уровень Un будем называть соседним сверху для Un-1, а Un-1 - соседним снизу для Un.
PR-решения на n-м уровне будем обозначать с индексом n, то есть (pn,rn) или (x(pn,rn), y(pn,rn)).
Индукцией по номеру уровня n определим PR-решения, принадлежащие n-му уровню.
U0 состоит из параметра p0=1.
U1 состоит из одного PR-решения (x1,y1) = (x(1,0), y(1,0)) = (1,0) с параметрами p1 = 1, r1 = 0. Это PR-решение будем называть минимальным.
Допустим, что сформирован уровень Un. Тогда, каждое PR-решение на уровне Un (для определённости обозначим его (pn,rn)), определяет на соседнем сверху уровне Un+1 следующее множество PR-решений {(pn+1, rn+1)}, в каждом PR-решении (pn+1, rn+1) которого параметры pn+1, rn+1 имеют вид
где qn - параметр, принимающий любые натуральные значения;
рп-1 =
параметр РR-решения (рп-1, rп-1) с уровня Uп-1.
Следовательно, PR -решения (3) зависят от . В частности, для фиксированного РR-решения (рп-1, rп-1)Uп, все РR-решения (рп-1, rп-1)Uп-1 с параметрами вычисленными по формулам (3) образуют бесконечное множество {(pn+1, rn+1)}, элементы которого зависят только от qn .
Для фиксированного РR-решения (рп, rп)Uп, все PR-решения множества будем называть соседними с ним сверху, а само фиксированное PR-решение , будем называть соседним снизу для всех PR-решений множества . Значит, для фиксированного PR-решения (pn, rn) соседних с ним сверху, бесконечно много.
Проверим, что параметры pn+1, rn+1, вычисленные по формулам (3), действительно определяют PR-решение (pn+1, rn+1) , для которого соседним снизу является .
Нужно показать, что
то есть
0 < rn+1 < pn+1.
Действительно, имеем
и формула (4) доказана.
Далее,
рп+1 = qn(qnpn + 2rn) + pn-1 > qnpn + rn = rn+1
и формула (5) доказана. Следовательно, действительно, параметры рп+1, rn+1 определяют РR-решение (рп+1, rn+1).
Un+1 есть объединение всех множеств вида {(pn+1, rn+1)}, для каждого .
Далее, параметры q1, q2,..., qn в формулах
полностью и однозначно определяют следующую последовательность PR-решений
(1,0) = (p1, r1), (p2, r2),…,(pn-1, rn-1),( pn, rn),
где параметры pi, ri, (i = 2,3,…,n) является функциями от qi-1, pi-1, rn-1, а в итоге функциями от В частности, параметры pn+1, rn+1 являются функциями от q1, q2,...,qn.
Переход в последовательности () от (i = 1,2,...,n-1) по формулам (3') назовём i-м шагом вверх. Назовём последовательность () маршрутом вверх от (1,0) до ( pn, rn), а метод порождения маршрута () - подъёмом от (1,0) до ( pn, rn).
Теперь рассмотрим произвольное РR-решение (pn, rn)Un (n>1) (следовательно, Пусть получено из соседнего снизу PR-решения по формулам (3), то есть имеем
Покажем, что ни из какого другого PR-решения, PR-решение не может быть получено по формулам (6). Допустим, что получено из некоторого PR-решения (p, r) по формулам вида (6), то есть
Но из следует, что то есть р = рп-1.
Тогда rn = qp + r = qpn-1 + r, где 0 < r < pn-1. Но это возможно, только если q = qn-1, r = rn-1. Учитывая все это, получаем что
pn = q2p + 2qr + = q2n-1 + 2qn-1rn-1 + = q2n-1+2qn-1rn 1 + pn-2.
Откуда = pn-2.
Утверждение доказано. Отсюда следует, что для любого PR-решения (pn, rn)Un соседнее снизу PR-решение определяется однозначно и, более того, ни из какого другого PR-решения (pn, rn)Un, не может быть получено по формулам (6).
Так как для любого n > 1 любое PR-решения (pn, rn)Un (n>1) может быть получено по формулам (6) только из единственного PR-решения , то в формулах (6) параметры qn-1, pn-1, rn-1 должны однозначно определяться по параметрам pn, rn. Действительно, из формул (6) следует
где [a - целая часть числа а.
В свою очередь, PR-решения точно также однозначно определяет параметры и PR-решения Следовательно, PR-решения аналогичным образом может быть получено ещё одним шагом вниз. Спускаясь, таким образом, по уровням всё ниже и ниже мы, в конце концов, дойдём до минимального PR-решения и параметры q1. В итоге, исходя из PR-решения однозначно восстановим следующую последовательность PR-решения
(pn,rn), (pn-1,rn-1),…,(p2,r2), (p2,r2) = (1,0).
Следовательно, рядом стоящие элементы этой последовательности являются соседними сверху и снизу PR-реше-ниями. Назовём все такие последовательности маршрутами вниз, а метод порождения маршрута вниз () назовём спуском от до .
Важно отметить, что любой маршрут вниз () однозначно определяется PR-решением
Если два PR-решения входят в некоторый маршрут вниз вида (), то назовём такие два PR-решения родственными. В частности соседние PR-решения родственны и любое PR-решение родственно минимальному PR-реше-нию (1,0).
Переход в () от (i = n, n-1,...,3,2) по формулам (8) назовём i-м шагом вниз.
Ясно также, что маршрут () может быть однозначно восстановлен также в обратном направлении, исходя из минимального PR-решения , по формулам (6), с учётом того, что все q1,q2,...,qn-1 известны. В этом случае его лучше переписать в виде () и назвать обратным к маршруту (). Следовательно, маршрут () определяется однозначно, так как q1, q2,...,qn-1 однозначно определяются маршрутом () при спуске.
Ещё раз отметим, что последовательность (), реализованная спуском полностью и однозначно определяется её первым элементом и это существенно отличает её от последовательности (), реализованной подъёмом. Действительно, при подъёме требуется ещё фиксация произвольных параметров Это означает, что PR-реше-ния множества можно представить вершинами дерева Т с корнем и направленными рёбрами от любого PR-решения на уровне ко всем соседним с ним сверху PR-решениям на уровне (n = 2,3,... ).
Пока неясно, содержат ли уровни U1, U2,...,Un,... все PR-решения. Покажем, что любое PR-решение окажется на некотором уровне. Легко видеть, что в маршруте вниз ()
pn >rn >pn-1 > rn-1>…> p2 >r2 >p1 r1 = 0,
то есть rn > rn-1 >…>r2 > r1 = 0
Поэтому, осуществляя шаги вниз, начиная с произвольного PR-решения (p,r), и учитывая (*), мы, через некоторое конечное число n шагов вниз, придем к минимальному PR-решению (1,0). Следовательно, PR-решение (p,r) принадлежит n-му уровню Un, то есть (p,r) = (pn,rn).
Это означает, что множество содержит все PR-решения.
Оказывается, фиксированное PR-решения (рп,rn)Un (n >1) в неявной форме не только однозначно определяет маршрут вниз (), но и позволяет восстановить явную форму этого PR-решения, то есть вычислить (xn,yn) = (x(pn,rn), y(pn,rn)). Это следует из следующей важной теоремы.
Теорема Спуска-подъёма. Пусть (рп, rп) произвольное PR-уравнение на п-м уровне Un. Оно однозначно определяет на уровнях п, п-1,...,2,1 следующий маршрут из PR-реше-ний
(pn,rn), (pn-1,rn-1),…,(p2,r2), (p1,r1) = (1,0).
где параметры соседних PR-решений этого маршрута связаны формулами:
(i = n, n - 1,…,3,2),
которые эквивалентны следующим формулам:
(j = 1,2,…,n); (p0 = 1);
0 rj < pj; (j = 1,2,…,n).
Тогда явные формы (xj,yj)= (x(pj,rj), y(pj,rj)) и (xj-1,yj-1)= (x(pj-1,rj-1), y(pij-1,rij-1)) соседних PR-решений (рj, rj) и (рj-1, rj-1) маршрута () связаны следующими формулами:
(j = 2,3,…,n).
Формулы (11) позволяют последовательно по явной форме (xj-1,yj-1) PR-решения (рj-1, rj-1) восстановить явную форму (xj,yj) соседнего сверху PR-решения и в итоге восстановить явную форму всех PR- решений маршрута (), начиная с явной формы минимального PR-решения (x1,y1) =(1,0) и кончая явной формой (xn,yn) PR-решения (рn, rn).
Следствие. Из этой теоремы следует следующий эффективный алгоритм Спуска-пoдъёма для вычисления явной формы PR-решения, заданного в неявной форме (рп, rп).
По PR-решению (рп, rп) формируем маршрут вниз () по формулам (8'), состоящий из PR-решений в неявной форме. Далее, по формулам (11) в обратном порядке формируем следующий маршрут вверх:
(1,0) = (x1,y1),(x2,y2),…,(xn-1,yn-1),(xn,yn),
состоящий из PR-решений уже в явной форме. В результате получаем явную форму (xn,yn) исходного PR-решения (рп, rп), заданного вначале в неявной форме.
Очевидно, по эффективности этот алгоритм сравним с алгоритмом Эвклида для вычисления НОД двух чисел.
Доказательство теоремы.
Единственное PR-решение (x1,y1) = (1,0) с параметрами р1 = 1, r1 = 0, очевидно. Поэтому для доказательства теоремы 2 достаточно доказать для всех j = 1,2,...,п следующие два утверждения:
1.
2. Числители формул (11) делятся на знаменатели.
Индукцией по j проверим утверждение 1. Для j = 1 равенство 1. очевидно. Предположим, что для j-1 имеем Тогда
(учитывая формулу (9) и индуктивное предположение) = .Утверждение 1 доказано.
Утверждение 2, то есть делимость чисел будет доказано, если будет показано, что формулы (11) можно переписать в виде:
1) если j = 2m+1 (j - нечетное), то
x2m+1 = x2m-1 + y2mq2m
y2m+1 = x2m+1r2m+1 - y2mp2m+1
2) если j = 2m (j - четное), то
y2m =y2(m-1) + x2m-1q2m-1
x2m = x2m-1 p2m - y2mr2m.
Докажем эти формулы индукцией по j. Предположим, что для j-1 указанные формулы, в зависимости от чётности и нечётности j-1, имеют место.
Возможны два случая.
1. j = 2m+1. В этом случае индуктивное предположение имеет вид (14), (15), а соотношения (9),(10)
.
В рассматриваемом случае имеем
по индуктивному предположению (15)) = (используя (17)) =
Формула (12) доказана для j = 2m+1. Далее, в рассматриваемом случае
по индуктивному предположению (15)) = (используя (17)) =используя (16))
x2m-1r2m+1 - y2mp2m+1 + y2mq2mr2m+1 = (x2m-1 + y2mq2m)
(r2m+1 + 1) - y2mp2m+1 = (используя уже доказанное (12)) = x2m+1r2m+1 - y2mp2m+1 и (13) доказана для j = 2m+1.
2. j = 2m. В этом случае индуктивное предположение имеет вид:
x2m-1 = x2m-3 + y2(m-1)q2(m-1)
y2m-1 = x2m-1r2m-1 - y2(m-1)p2m-1,
а соотношения (9),(10) вычисление делитель индуктивный
.
В рассматриваемом случае имеем
по индуктивному предположению
(19)) = (используя (21)) =х2m-1q2m-1 + y2(m-1) и (14) доказана для j = 2m.
Далее в рассматриваемом случаев
(по индуктивному предположению (19)) = (используя (21))
(используя (20)) =
x2m-1p2m - (x2m-1q2m-1+ y2(m-1))r2m = (используя уже доказанное (14)) = x2m-1p2m - q2mr2m.
Формула (15) доказана для j = 2m.
Таким образом формулы (12)…(15) доказаны во всех случаях и значит доказано, что числители формул (11) делятся на pj-1 для всех j =1,2,...,n.
Осталось доказать положительность PR-решений, вычисляемых по формулам (11). Сделаем это индукцией по n. При n = 1 имеем (x1,y1) = (x(1,0),y(1,0)) = (1,0), то есть (x1,y1) положительно. Тогда при n = 2 имеем то есть х2 > 0, y2 > 0, то есть (x2,y2) положительно. Предположим, что все положительны, точнее Тогда и, очевидно, далее Предположим, что уп+1 0, то есть хпrn+1 - yn 0, или хпrn+1 yn .
Заменяя в этом неравенстве по формулам
получим
или ,
что невозможно, так как. Положительность всех PR-решений доказана.
Теорема полностью доказана.
Подведём итог в виде следующей теоремы.
Основная теорема
1. Любое PR-решение (p,r) (а следовательно, и любое H-решение) принадлежит единственному уровню множества , то есть имеет вид для некоторого n.
2. Любое PR-решение однозначно определяет бесконечное множество , соседних сверху, PR-решений , параметры которых имеют вид
где qn - произвольное натуральное число; pn-1 - параметр PR-решения (pn-1 < rn-1) с уровня Un-1.
3. При фиксированных q1, q2,...,qm-1 минимальное PR-решение (p1, r1) = (1,0)U1 однозначно определяет следующий маршрут вверх
в котором соседние PR-решения связаны формулами (3) при n =1,2,...,m-1. Следовательно, все (pn, rn), (n = 2,3,...,m) являются функциями от q1,q2,...,qn-1. В частности, (pm, rm) полностью определяется числами q1,q2,...,qm-1.
4. Любое PR-решение (pп, rп) =Uп (п 2) однозначно определяет единственное снизу PR-решение по формулам:
5. Любое однозначно определяет следующий маршрут вниз
в котором соседние PR-решения связаны формулами (8) при n = m,m-1,...,3,2. Следовательно, маршрут вниз () однозначно определяется PR-решением (pm, rm).
6. Все PR-решения можно представить вершинами дерева T с корнем (p1, r1) = (1,0) и направленными рёбрами от любого PR-решения на уровне Un-1 ко всем соседним с ним сверху PR-решениям на уровне Un, (n = 1,2,...).
7. Любое PR-решение связано с соседним с ним снизу PR-решением следующими фор-мулами:
Если в (1) p < Pmax, то дерево Т будет конечным. Обозначим его T(Pmax). Используя результаты основной теоремы в этом случае можно, реализуя алгоритм перебора с возвратом, последовательно осуществить построение и обход, ровно по одному разу, всех вершин (PR-решений) дерева T(Pmax), начиная с его корня (минимального PR-решения). Каждый шаг этого построения и обхода состоит из следующих действий:
Исходим из ранее полученного на некотором n-м уровне Un PR-решения и его явной формы
Фиксируем очередное, определяемое алгоритмом перебора с возвратом, значение qn. Исходя из qn, pn, rn по формулам (6), вычисляем параметры pn, rn соседнего сверху PR-решения (pn+1,rn+1)Un+1. При этом, если окажется pn+1>Pmax, то возвращаемся к ближайшей, ещё не до конца исследованной, вершине дерева T(Pmax) и делаем новый шаг. Завершаем шаг вычислением явной формы
,
полученного допустимого (то есть удовлетворяющего условию ) PR-решения по формулам (11). Алгоритм закончит работу, когда будут исследованы все вершины дерева T(Pmax)
Очевидно, этот алгоритм оптимален, так как для решения основной задачи обязательно нужно получить параметры и явную форму каждого PR-решения ровно один раз с минимальными затратами; это последовательно реализуется по очень простым формулам (3), (11). Далее, алгоритм автоматически отсекает все не H-уравнения и все не Н-решения Н-уравнений.
Этот алгоритм реализован в виде программы на компьютере.
В качестве побочного результата этот алгоритм находит оптимальным образом все решения всех сравнений вида (2) для всех .
Полученные результаты приводят также к следующему
алгоритму решения задач 1 и 2, в котором число шагов для вычисления всех решений уравнения
х2 + у2 = Рmax
равно числу PR-решений всех уравнений (1) с , что намного меньше числа шагов, которые нужно сделать при полном переборе.
Описание алгоритма
Начиная с минимального PR-решения , реализуем шаги алгоритма перебора с возвратом для вычисления неявных форм всех PR-решений , удовлетворяющих условию по формулам (6). На этом этапе не вычисляем явные формы PR-решений по формулам (11), так как явные формы решений нужны только для уравнения (1').
Каждый шаг алгоритма состоит из следующих действий с очередным сформированным PR-решением в неявной форме.
Проверяем неравенство . Если , то возвращаемся к ближайшему, ещё не до конца исследованному PR-решению . Выбираем очередное значение qm и делаем очередной шаг алгоритма, т.е. вычисляем очередное PR-решение в неявной форме.
Если , то проверяем делимость Рmax на рп. Если не делится на , то делаем очередной шаг алгоритма.
Если и делится на , то проверяем: является ли квадратом, то есть имеет ли место равенство . Если - нет, то переходим к следующему шагу алгоритма.
Если же , делится на и Рmax/pn = d2, то,
исходя из полученной неявной формы PR-решения , находим явную форму этого PR-решения, описанным выше алгоритмом спуска-подъёма. Тогда будет решением уравнения (1'), так как . Включаем это решение в список решений уравнения (1') и делаем очередной шаг алгоритма.
Алгоритм закончит работу, когда будут проверены все PR-решения , удовлетворяющие условию . В результате будет получен список всех решений уравнения (1'). Если он окажется пустым, то уравнение (1') не имеет решений, то есть неразрешимо.
Библиографический список
1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985.
2. Виноградов И.М. Основы теории чисел. - М.: Наука, 1981.
Размещено на Allbest.ru
Подобные документы
История арифметики остатков. Понятие остатка, наибольшего общего делителя, расширенного алгоритма Евклида и применение его для решения линейных диофантовых уравнений. Алгебраический подход к делимости в кольцах и разложение чисел в цепные дроби.
дипломная работа [466,7 K], добавлен 23.08.2009Теория высшей алгебры в решении задач элементарной математики. Программы для нахождения частного и остатка при делении многочленов, наибольшего общего делителя двух многочленов, производной многочлена; разложения многочленов на кратные множители.
дипломная работа [462,8 K], добавлен 09.01.2009Расширенный алгоритм Евклида, его использование для нахождения наибольшего общего делителя натуральных чисел посредством остатков от деления. Математическая проблема календаря. Евклидовы кольца - аналоги чисел Фибоначчи в кольце многочленов, их свойства.
реферат [571,1 K], добавлен 25.09.2009Общая схема методов спуска. Метод покоординатного спуска. Минимизация целевой функции по выбранным переменным. Алгоритм метода Гаусса-Зейделя. Понятие градиента функции. Суть метода наискорейшего спуска. Программа решения задачи дискретной оптимизации.
курсовая работа [90,8 K], добавлен 30.04.2011Свойства делимости целых чисел в алгебре. Особенности деления с остатком. Основные свойства простых и составных чисел. Признаки делимости на ряд чисел. Понятия и способы вычисления наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК).
лекция [268,6 K], добавлен 07.05.2013Определение понятия множества как совокупности некоторых объектов, объединенных по какому-либо признаку. Классификация операций над множествами. Принципы взаимно однозначного соответствия. Нахождение наибольшего общего делителя и наименьшего кратного.
презентация [249,6 K], добавлен 24.09.2011Постановка задачи аппроксимации методом наименьших квадратов, выбор аппроксимирующей функции. Общая методика решения данной задачи. Рекомендации по выбору формы записи систем линейных алгебраических уравнений. Решение систем методом обратной матрицы.
курсовая работа [77,1 K], добавлен 02.06.2011Определение основных свойств выпуклых фигур. Описание традиционного решения изопериметрической задачи. Приведение примеров задач на поиск точек экстремума. Формулирование и доказательство теоремы о пятиугольнике наибольшего периметра единичного диаметра.
дипломная работа [4,6 M], добавлен 30.03.2011Определение наименьшего и наибольшего значения функции в ограниченной области и ее градиента; общего интеграла и общего и частного решения дифференциального уравнения. Исследование ряда на абсолютную сходимость с применением признаков Коши и Даламбера.
контрольная работа [107,2 K], добавлен 25.11.2013Понятие волнового уравнения, описывающего различные виды колебаний. Рассмотрение явной разностной схемы "крест" для решения данной задачи. Нахождение решений на нулевом и первом слоях с помощью начальных условий. Виды и решения интегральных уравнений.
презентация [240,6 K], добавлен 18.04.2013
