Викиконспекты ПМ-ПУ - Вклад [ru]

Алгоритмы и структуры данных

2022-02-19T12:27:42Z

СВ: Новая страница: «== Простые структуры данных == * Динамический массив * Список == Типы данных == * Стек *...»

== Простые структуры данных ==
* [[Динамический массив]]
* [[Список]]

== Типы данных ==
* [[Стек]]
* [[Очередь]]
* [[Словарь]]

== Структуры данных для поиска ==
* [[Двоичное дерево поиска]]
* [[АВЛ-дерево]]
* [[Красно-черное дерево]]
* [[АА-дерево]]
* [[B-дерево]]
* [[B+-дерево]]

== Очереди с приоритетом ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]

== Система непересекающихся множеств ==
* [[Disjoint Sets]]
* [[Union-Find Disjoint Sets]]

Обсуждение участника:StudentL

2022-01-03T11:36:10Z

СВ: Полностью удалено содержимое страницы

Функции нескольких переменных. Предел функции

2021-12-04T19:26:31Z

СВ: Новая страница: «Пусть задана область <math>D\subset R^n</math>. Пусть каждой точке <math>{\bf x}=(x_1,\ldots,x_n)^T\in D</math> поставле...»

Пусть задана область <math>D\subset R^n</math>. Пусть каждой точке <math>{\bf x}=(x_1,\ldots,x_n)^T\in D</math> поставлено в соответствие однозначным образом вещественное число <math>f({\bf x})=f(x_1,\ldots,x_n)</math>.
Тогда говорят, что определена скалярная вещественная функция нескольких переменных. Область <math>D</math> назовем областью определения функции <math>f({\bf x})</math>.

Функция одной переменной <math>y=f(x)</math> задает кривую на плоскости. Функция двух переменных <math>y=f(x_1,x_2)</math> задает двумерную поверхность в трехмерном пространстве, и т.д.

{{Пример
|content=
Рассмотрим функцию <math>y=f(x_1,x_2)=\frac{\ln(x_1x_2)}{x_1^2+x_2^2}.</math>
Областью определения этой функции является множество <math>D=\{{\bf x}=(x_1,x_2)^T\in R^2:\ x_1x_2 \gt 0\}.</math>
Задавая различные значения двумерной переменной <math>{\bf x}\in D</math>, будем получать различные значения функции.
При этом точка <math>(x_1,x_2,y)^T</math> будет пробегать по некоторой поверхности.
Пусть, например, <math>x_1=1</math>, <math>x_2=2</math>.
В этой точке функция принимает значение <math>y=f(1,2)=(\ln2)/5</math>.
}}

{{Определение
|definition= Величина <math>\hbox{ diam} D=\sup_{{\bf x}^{(1)},{\bf x}^{(2)}\in D}\rho({\bf x}^{(1)},{\bf x}^{(2)}) </math>
называется диаметром области <math>D</math>. Если <math>\hbox{diam } D \lt +\infty</math>, то область <math>D</math> называется ограниченной.
}}

{{Определение
|definition= Область <math>D</math> называется связной, если любые две точки этой области можно соединить непрерывной кривой, целиком лежащей в этой области.
}}

{{Определение
|definition= Пусть <math>{\bf a}</math> — предельная точка области <math>D\subset R^n</math>. Число <math>g</math> называется пределом функции <math>f({\bf x})</math> в точке <math>{\bf a}</math> (предела функции по Гейне):
<math>
g=\lim\limits_{{\bf x}\to{\bf a}}f({\bf x}), \tag{1}
</math>
если для любой последовательности точек <math>\big\{{\bf x}^{(k)}\big\}</math> из области <math>D</math>, таких что <math>{\bf x}^{(k)}\to{\bf a}</math>
при <math>k\to+\infty</math>, выполняется условие <math>f({\bf x}^{(k)})\to g</math> при <math>k\to+\infty</math>.
}}

Таким образом, как и в одномерном случае, определение предела функции сводится к понятию предела последовательности. Смысл определения предела: вдоль любого пути в области
задания функции, ведущего к предельной точке, значение функции должно стремиться к одному и тому же числу. В одномерном случае мы могли приближаться к предельной точке на
вещественной прямой слева и справа (вводились лево и правосторонние пределы). В многомерном случае (на плоскости, в трехмерном пространстве, и т.д.) мы можем приближаться к предельной
точке как угодно (по прямой, по спирали, и т.д.).

Пусть <math>{\bf a}=(a_1,\ldots,a_n)^T</math>, <math>{\bf x}^{(k)}=(x_1^{(k)},\ldots,x_n^{(k)})^T</math>.

Зафиксируем переменные <math>x_2,\ldots,x_n</math>, а переменную <math>x_1</math> устремим к <math>a_1</math>. Рассмотрим одномерный предел
<math>f^{(1)}(x_2,\ldots,x_n)=\lim_{x_1\to a_1}f(x_1,x_2,\ldots,x_n).</math>
После этого, оставляя фиксированными переменные <math>x_3,\ldots,x_n</math>, устремим переменную <math>x_2</math> к <math>a_2</math>, и т.д. В результате придем к так называемому повторному пределу
<math>\lim_{x_n\to a_n}\ldots\lim_{x_1\to a_1}f(x_1,\ldots,x_n).</math>
Если фиксировать переменные в другом порядке, получим другой повторный предел. Всего, очевидно, можно построить <math>n!</math> повторных пределов. Так, если <math>n=2</math>, то будет два
повторных предела
<math>\lim_{x_1\to a_1} \lim_{x_2\to a_2}f(x_1,x_2),\quad \lim_{x_2\to a_2} \lim_{x_1\to a_1}f(x_1,x_2).</math>

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

{{Пример
|content= Имеем <math>\lim_{(x_1,x_2)^T\to(0,0)^T}(x_1^2+x_2^2)=\lim_{x_1\to0} \lim_{x_2\to0}(x_1^2+x_2^2)=\lim_{x_1\to0}x_1^2=0.</math>
}}

Однако, существование многомерного предела не гарантирует существование повторного предела, и наоборот.

{{Пример
|content= Пусть <math>{\bf a}=(0,0)^T</math>, <math>f(x_1,x_2)=\frac{x_1x_2}{x_1^2+x_2^2}.</math>

Оба повторных предела здесь существуют
<math>
\lim_{x_1\to 0} \lim_{x_2\to 0}f(x_1,x_2)=\lim_{x_2\to 0} \lim_{x_1\to 0}f(x_1,x_2)=0.
</math>

В то же время, многомерного предела
<math>
\lim_{(x_1,x_2)^T\to(0,0)^T}f(x_1,x_2)
</math>
здесь не будет. В самом деле, будем двигаться вдоль лучей, ведущих в начало координат:
<math>
x_1\to0,\quad x_2=kx_1 \to 0,
</math>
где коэффициент <math>k=\hbox{const}</math> задает наклон луча. На этих лучах имеем
<math>\lim_{x_1\to0}f(x_1,kx_1)=\frac{k}{k^2+1}.</math>
Этот предел существует, но зависит от выбора <math>k</math>, т.е. вдоль разных лучей, ведущих в предельную точку, значение функции стремится к разным значениям. Значит, многомерного предела нет.

Рассмотрим теперь функцию
<math>f(x_1,x_2)=\frac{x_1^2x_2}{x_1^4+x_2^2}.</math>
В качестве предельной точки снова возьмем <math>{\bf a}=(0,0)^T</math>. Аналогично получим, что соотношения для повторных пределов верны. Двигаясь вдоль лучей, находим, что предел
<math>\lim_{x_1\to0}f(x_1,kx_1)=\lim_{x_1\to0}\frac{kx_1}{x_1^2+k^2}=0</math> не зависит от выбора <math>k</math>. Однако, это еще не означает, что многомерный предел существует, поскольку в определении предела предполагается движение по любым путям, ведущим к предельной точке,
не обязательно по лучам. Будем, например, двигаться по параболам:
<math>x_1\to0,\quad x_2=kx_1^2\to0.</math>

Получим
<math>\lim_{x_1\to0}f(x_1,kx_1^2)=\frac{k}{k^2+1}.</math>
Снова имеем зависимость от выбора <math>k</math>, т.е. на каждой рассматриваемой параболе значение функции стремится к разным значениям. Значит, многомерного предела по-прежнему нет.
}}

{{Пример
|content= Рассмотрим теперь обратную ситуацию. Пусть <math>{\bf a}=(0,0)^T</math>,
<math>f(x_1,x_2)=x_1\sin\frac1{x_2}+x_2\sin\frac1{x_1}.</math>

Учитывая предельное соотношение
<math>0\leq|f(x_1,x_2)|\leq|x_1|+|x_2|\to0\quad\hbox{при}\quad (x_1,x_2)^T\to(0,0)^T,</math>
получаем, что многомерный предел существует:
<math>\lim_{(x_1,x_2)^T\to(0,0)^T}f(x_1,x_2)=0.</math>

С другой стороны, ни одного из повторных пределов
<math>\lim_{x_1\to 0} \lim_{x_2\to 0}f(x_1,x_2),\quad\lim_{x_2\to 0} \lim_{x_1\to 0}f(x_1,x_2)</math>
здесь не будет.

Если, например, рассмотреть функцию
<math>f(x_1,x_2)=x_1+x_2\sin\frac1{x_1},</math>
то получим, что повторный предел
<math>\lim_{x_1\to 0} \lim_{x_2\to 0}f(x_1,x_2)=0</math>
здесь существует, а повторный предел
<math>\lim_{x_2\to 0} \lim_{x_1\to 0}f(x_1,x_2)</math>
нет.
}}

Таким образом, сводить многомерный предел к повторному можно, только убедившись в том, что оба они существуют.

Определение предела функции по Гейне удобно использовать в случаях, когда надо доказать, что предела нет. Для этого достаточно найти два пути, ведущих в предельную точку,
вдоль которых значение функции стремится к разным величинам, или один путь, вдоль которого значение функции вообще ни к чему не стремится. В тех случаях, когда предел существует,
часто бывает удобнее использовать другое определение предела функции.</p>

{{Определение
|definition= Пусть <math>{\bf a}</math> — предельная точка области <math>D\subset R^n</math>. Число <math>g</math> называется пределом функции <math>f({\bf x})</math> в точке <math>{\bf a}</math> (предел функции по Коши):
<math>g=\lim\limits_{{\bf x}\to{\bf a}}f({\bf x})</math>,
если для любого <math>\varepsilon \gt 0</math> можно указать <math>\delta \gt 0</math>, такое что для всех <math>{\bf x}\in D</math>, удовлетворяющих условию <math>\rho({\bf x},{\bf a}) \lt \delta</math>,
будет иметь место неравенство <math>|f({\bf x})-g| \lt \varepsilon</math>.}
}}

Будут верны те же теоремы, что и в одномерном случае.

{{Теорема
|statement= Определения предела функции по Гейне и по Коши эквивалентны.
}}

{{Теорема
|about= критерий сходимости Коши
|statement= Для того, чтобы существовал конечный предел <math>\lim\limits_{{\bf x}\to{\bf a}}f({\bf x})</math> необходимо и достаточно, чтобы
для любого <math>\varepsilon \gt 0</math> можно было указать <math>\delta \gt 0</math> так, чтобы для всех <math>{\bf x}^{(1)},{\bf x}^{(2)}\in D</math>, удовлетворяющих условиям
<math>\rho({\bf x}^{(1)},{\bf a}) \lt \delta</math>, <math>\rho({\bf x}^{(2)},{\bf a}) \lt \delta</math>,
имело место неравенство <math>|f({\bf x}^{(1)})-f({\bf x}^{(2)})| \lt \varepsilon</math>.
}}

{{Теорема
|about=арифметические свойства предела
|statement= Пусть существуют пределы
<math>\lim_{{\bf x}\to{\bf a}}f({\bf x})=g,\quad \lim_{{\bf x}\to{\bf a}}h({\bf x})=r</math>.

Тогда:
<math>\lim_{{\bf x}\to{\bf a}}(f({\bf x})\pm h({\bf x}))=g\pm r,\quad \lim_{{\bf x}\to{\bf a}}(f({\bf x})h({\bf x}))=gr</math>,
а если <math>r\not=0</math>, то
<math>\lim_{{\bf x}\to{\bf a}}\frac{f({\bf x})}{h({\bf x})}=\frac{g}{r}</math>.
}}

{{Определение
|definition= Пусть функция <math>y=f(x_1,\ldots,x_n)</math> определена в области <math>D\subset R^n</math>, а функции
<math>x_1=h_1(t_1,\ldots,t_m),\ldots, x_n=h_n(t_1,\ldots,t_m)</math>
определены в области <math>G\subset R^m</math>. Тогда функция
<math>y=f\left({\bf h}({\bf t})\right)=f\left(h_1(t_1,\ldots,t_m),\ldots,h_n(t_1,\ldots,t_m)\right)</math>
называется суперпозицией скалярной функции <math>f({\bf x})</math> и векторной функции <math>{\bf h}({\bf t})</math>, или иначе, сложной функцией. Здесь
<math>{\bf x}=(x_1,\ldots,x_n)^T</math>, <math>{\bf t}=(t_1,\ldots,t_m)^T</math>, <math>{\bf h}({\bf t})=(h_1({\bf t}),\ldots,h_n({\bf t}))^T</math>.
}}

<p><strong>Пример. </strong> Из функций <math>y=x_1x_3+x_2^2</math>, <math>x_1=\sqrt{t_1+t_2}</math>, <math>x_2=t_1t_2</math>, <math>x_3=\sin{t_1}</math> можно построить суперпозицию
<math>y=\sqrt{t_1+t_2}\sin{t_1}+t_1^2t_2^2</math>.
</p>

{{Теорема
|about=о суперпозиции пределов
|statement= Пусть <math>{\bf b}=(b_1,\ldots,b_m)^T</math> — предельная точка области <math>G\in R^m</math>,
<math>{\bf a}=(a_1,\ldots,a_n)^T</math> — предельная точка области <math>D\in R^n</math>. Тогда если существуют пределы
<math>\lim_{{\bf t}\to{\bf b}}{\bf h}({\bf t})={\bf a},\quad \lim_{{\bf x}\to{\bf a}}f({\bf x})=g</math>,
то <math>\lim_{{\bf t}\to{\bf b}}f\left({\bf h}({\bf t})\right)=g</math>.
}}

Обратная матрица

2021-11-23T19:28:47Z

СВ:

== Полезные ссылки ==
* [https://www.youtube.com/watch?v=QrVhx6tWZyE&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=15 KhanAcademyRussian: Определитель и союзная матрица]
* [https://www.youtube.com/watch?v=vFnFQ8qSEao&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=7 KhanAcademyRussian: Единичная и обратная матpицы(Часть 1)]
* [https://www.youtube.com/watch?v=iUyoeXNCGYE&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=16 KhanAcademyRussian: Обратные матрицы (Часть 2)]
* [https://www.youtube.com/watch?v=USYSUIkeB4M&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=17 KhanAcademyRussian: Обратные матрицы (Часть 3)]

Алгебраические дополнения и миноры

2021-11-23T19:27:40Z

СВ:

== Полезные ссылки ==
* [https://www.youtube.com/watch?v=t0MSqnTMpAk&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=14 KhanAcademyRussian: Матрица миноров и матрица алгебраических дополнений]

Матрицы и операции с ними

2021-11-23T18:26:22Z

СВ:

{{Определение
|definition=Матрицей называется таблица элементов, состоящая из <math>m</math> строк и <math>n</math> столбцов.
}}

== Ссылки на полезные источники ==
* [https://www.youtube.com/watch?v=b7NbUd5rGgQ&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=2 KhanAcademyRussian: Введение в матрицы]
* [https://www.youtube.com/watch?v=XeLppMkWwKI&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=3 KhanAcademyRussian: Сложение и вычитание матриц]
* [https://youtu.be/bg_gxWOufsA KhanAcademyRussian: Транспонирование матриц]
* [https://www.youtube.com/watch?v=uhtlPbYlMPs&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=5 KhanAcademyRussian: Умножение матриц. Часть 1]
* [https://www.youtube.com/watch?v=ax-nTuBRj4g&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=6 KhanAcademyRussian: Умножение матриц. Часть 2]

Определители второго и третьего порядка

2021-11-23T18:25:01Z

СВ:

== Полезные ссылки ==
* [https://www.youtube.com/watch?v=WBDOB2q7bbU&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=8 KhunAcademyRussian: Нахождение детерминанта(определителя) матрицы второго порядка]
* [https://www.youtube.com/watch?v=Fkbe8XyMgOg&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=12 KhanAcademyRussian: Вычисление определителя матрицы 3х3 (первый способ)]
* [https://www.youtube.com/watch?v=J9ElsNvxVIs&list=PLxGo9dxQkqWC0zB7_agKHKbQYkqLrsL3s&index=13 KhanAcademyRussian: Вычисление определителя матрицы 3х3 (второй способ)]

Последовательности в пространстве Rn

2021-11-23T17:58:21Z

СВ: Новая страница: «Пусть каждому натуральному <math>k</math> поставлен в соответствие вектор <math>{\bf x}^{(k)}=(x_1^{(k)},\ldo...»

Пусть каждому натуральному <math>k</math> поставлен в соответствие вектор
<math>{\bf x}^{(k)}=(x_1^{(k)},\ldots,x_n^{(k)})^T</math>.
Тогда говорят, что задана последовательность элементов в пространстве <math>R^n</math>: <math>\big\{ {\bf x}^{(k)}\big\}_{k=1}^{+\infty}</math>.

{{Определение
|definition=Точка <math>{\bf a}\in R^n</math> называется пределом последовательности <math>\big\{ {\bf x}^{(k)}\big\}</math> при <math>k\to+\infty</math> (пишут <math>{\bf a}=\lim\limits_{k\to+\infty}{\bf x}^{(k)}</math>), если
для любого <math>\varepsilon \gt 0</math> можно указать номер <math>K \gt 0</math>, такой что при всех <math>k\geq K</math> выполнено условие <math>\rho({\bf x}^{(k)},{\bf a}) \lt \varepsilon</math>.
}}

{{Теорема
|statement=Пусть <math>{\bf a}=(a_1,\ldots,a_n)^T</math>, <math>{\bf x}^{(k)}=(x_1^{(k)},\ldots,x_n^{(k)})^T</math>. Тогда
<math>{\bf a}=\lim\limits_{k\to+\infty}{\bf x}^{(k)}</math>
тогда и только тогда, когда
<math>a_i=\lim\limits_{k\to+\infty}x_i^{(k)},\quad i=1,\ldots,n.</math>
|proof=Доказательство теоремы вытекает из леммы (об эквивалентности в плане близости сферической и параллелепипедальной метрик). В самом деле, согласно этой лемме, имеем что требование
<math>\sqrt{\sum_{i=1}^n(x_i^{(k)}-a_i)^2}\to0\quad\hbox{при}\quad k\to+\infty</math>
эквивалентно требованию <math>\max_{i=1,\ldots,n}|x_i^{(k)}-a_i|\to0\quad\hbox{при}\quad k\to+\infty</math>.
}}

Таким образом, исследование сходимости последовательности в <math>R^n</math> сводится к исследованию сходимости одномерных числовых последовательностей.
Значит, вся теория, построенная ранее для одномерных числовых последовательностей, может быть распространена и на многомерный случай.
Единственно, стоит заметить, что пространство <math>R^n</math> не упорядочено, т.е.
между его элементами не установлены операции отношения "<math>\lt</math>", "<math>\gt</math>", "<math>\leq</math>", "<math>\geq</math>". Поэтому теоремы из одномерного анализа,
где используются эти операции, напрямую на многомерный случай не переносятся.

{{Определение
|definition=Последовательность <math>\big\{ {\bf x}^{(k)}\big\}</math> называется ограниченной, если существует <math>M \geq 0</math>, такое что
<math>\rho({\bf x}^{(k)},{\bf0})\leq M</math> при всех <math>k=1,2,\ldots</math>. Здесь <math>{\bf 0}=(0,\ldots,0)^T</math> {{---}} нулевой элемент пространства <math>R^n</math>.
}}

Для пространства <math>R^n</math> верны следующие утверждения:
* Если предел последовательности существует, то он единственен.
* Если последовательность сходится, то она ограничена.
* Сходимость последовательности эквивалентна выполнению критерия Коши: для любого <math>\varepsilon \gt 0</math> можно найти такое <math>K \gt 0</math>, что для любых натуральных <math>k\geq K</math> и <math>p \geq 0</math> имеет место условие <math>\rho({\bf x}^{(k+p)},{\bf x}^{(k)}) \lt \varepsilon</math>.
* Справедливы арифметические свойства предела.
* Если последовательность сходится, то любая ее подпоследовательность сходится к тому же пределу.
* Справедлива теорема Больцано-Вейерштрасса: из любой ограниченной последовательности можно выбрать сходящуюся подпоследовательность.
* И т.д.

Положительно определенные квадратичные формы

2021-11-23T10:06:02Z

СВ:

Канонический вид любой квадратичной формы определен неоднозначно. Например, если квадратичная форма имеет канонический вид
<math>
f(\xi_1, \xi_2, ...,\xi_n ) = \lambda_1 \xi_1^2 + \cdots + \lambda_k \xi_k^2 - \lambda_{k + 1} \xi_{k + 1}^2 - \cdots - \lambda_n \xi_n^2,
</math>
где <math>\lambda_i \ge 0</math> для любого <math>i = \overline {1,n}</math>, то всегда можно
сделать еще одно невырожденное преобразование по формулам <math>\eta_1 = \sqrt {\lambda_1 } \xi_1</math>, ..., <math>\eta_k = \sqrt {\lambda_k } \xi_k</math>, ..., <math>\eta_n = \sqrt {\lambda_n } \xi_n</math>, в результате которого получаем
<math>
g(\eta_1, \eta_2, ...,\eta_n ) = \eta_1^2 + \cdots + \eta_k^2 - \eta _{k + 1}^2 - \cdots - \eta_n^2 .
</math>

Общим у этих квадратичных форм является количество <math>N^{+}</math> положительных коэффициентов и количество <math>N^{-}</math> отрицательных коэффициентов.
Таким образом, общее число ненулевых коэффициентов составляет <math>N^{+} + N^{-}</math>, а оно равно рангу квадратичной формы.

{{Теорема
|id=Th1
|about=закон инерции
|statement=Число положительных и число отрицательных коэффициентов при квадратах переменных в каноническом виде данной квадратичной формы, к которому она приводится в результате невырожденного линейного преобразования, не зависит от выбора указанного преобразования.
|proof=Пусть квадратичная форма <math>f({\bf x})=f(\xi_1, \xi_2, ..., \xi_n )</math> с помощью невырожденного
преобразования <math>{\bf x} = {\bf By}</math> приводится к каноническому виду
<math>
g({\bf y}) = g(\eta_1, \eta_2, ..., \eta_n ) = \alpha_1 \eta_1^2 + \cdots + \alpha_k \eta_k^2 - \alpha_{k + 1} \eta_{k + 1}^2 - \cdots - \alpha_n \eta_n^2
</math>,
где <math>\alpha_i \ge 0</math>, <math>i = \overline {1,n}</math>, а в результате преобразования <math>{\bf x} = {\bf Cz}</math> к виду
<math>
\varphi ({\bf z}) = \varphi (\zeta_1, \zeta_2, ..., \zeta_n ) = \beta_1 \zeta_1^2 + \cdots + \beta_r \eta_r^2 - \beta_{r + 1} \eta_{r + 1}^2 - \cdots - \beta_n \zeta_n^2
</math>.

Предположим противное, что <math>k < r</math>. Заметим, что указанные линейные преобразования являются обратимыми, поэтому имеем

<math>
{\bf y} = {\bf B}^{-1}{\bf x} \Leftrightarrow \eta_i = \sum\limits_{j = 1}^n {\mu_{ij} \xi_j }, i = \overline {1,n},
</math>

<math>
{\bf z} = {\bf C}^{ - 1}{\bf x} \Leftrightarrow \zeta_i = \sum\limits_{j = 1}^n {\theta_{ij} \xi_j }, i = \overline {1,n} .
</math>

Положим <math>\eta_1 = \eta_2 = \cdots = \eta_k = 0</math>, <math>\zeta_{r + 1} = \zeta _{r + 2} = \cdots = \zeta_n = 0</math>. Указанные равенства определяют систему линейных алгебраических уравнений

<math>
\label{eq5}
\left\{
\begin{array}{l}
\sum\limits_{j = 1}^n {\mu_{ij} \xi_j = 0, i = \overline {1,k}, } \\
\sum\limits_{j = 1}^n {\theta_{ij} \xi_j = 0, i = \overline {r + 1,n} .} \\
\end{array}
\right.
</math>

Число уравнений в системе равно <math>k + n - r</math>, а число неизвестных <math>n</math>.
По предположению <math>k < r</math>, поэтому <math>k + n - r < n</math>.
Следовательно, система имеет нетривиальное решение <math>\xi_1^\ast, \xi_2^\ast, ..., \xi_n^\ast </math>.

Тогда <math>\eta_i^\ast = \sum\limits_{j = 1}^n {\mu_{ij} \xi_j^\ast }</math>, причем <math>\eta_{1 }^\ast = \eta_{2 }^\ast = \cdots = \eta_{k }^\ast = 0</math>, а <math>\zeta_i^\ast = \sum\limits_{j = 1}^n {\theta_{ij} \xi_j^\ast }</math>,
где <math>\zeta_{r + 1}^\ast = \zeta_{r + 2}^\ast = \cdots = \zeta_{n}^\ast = 0</math>, <math>i = \overline {1,n}</math>.
Поэтому, с одной стороны, имеем
<math>
f(\xi_1^\ast, \xi_2^\ast, ...,\xi_n^\ast ) = g(\eta_1^\ast, \eta_2^\ast, ...,\eta_n^\ast ) = - \alpha_{k + 1} \eta_{k + 1}^{\ast 2} - \cdots - \alpha_n \eta_n^{\ast 2} < 0,
</math>
а с другой стороны, получаем
<math>
f(\xi_1^\ast, \xi_2^\ast, ..., \xi_n^\ast ) = \varphi (\zeta_1^\ast, \zeta_2^\ast, ..., \zeta_n^\ast ) = \beta_1 \zeta_1^{\ast 2} + \cdots + \beta_r \zeta_r^{\ast 2} > 0.
</math>

Полученное противоречие доказывает, что <math>k = r = N^{+}</math>.
}}

{{Замечание
|content=Так как число ненулевых коэффициентов в каноническом виде данной квадратичной формы не зависит от выбора преобразования и равно ее рангу, то,
очевидно, что и <math>N^{-}</math> также не зависит от способа приведения <math>f({\bf x})</math> к каноническому виду.
}}

Положительно определенные квадратичные формы

2021-11-23T07:49:56Z

СВ: Новая страница: «Канонический вид любой квадратичной формы определен неоднозначно. Например, если квадр...»

Канонический вид любой квадратичной формы определен неоднозначно. Например, если квадратичная форма имеет канонический вид
<math>
f(\xi_1, \xi_2, ...,\xi_n ) = \lambda_1 \xi_1^2 + \cdots + \lambda_k \xi_k^2 - \lambda_{k + 1} \xi_{k + 1}^2 - \cdots - \lambda_n \xi_n^2,
</math>
где <math>\lambda_i \ge 0</math> для любого <math>i = \overline {1,n}</math>, то всегда можно
сделать еще одно невырожденное преобразование по формулам <math>\eta_1 = \sqrt {\lambda_1 } \xi_1</math>, ..., <math>\eta_k = \sqrt {\lambda_k } \xi_k</math>, ..., <math>\eta_n = \sqrt {\lambda_n } \xi_n</math>, в результате которого получаем
<math>
g(\eta_1, \eta_2, ...,\eta_n ) = \eta_1^2 + \cdots + \eta_k^2 - \eta _{k + 1}^2 - \cdots - \eta_n^2 .
</math>

Общим у этих квадратичных форм является количество <math>N^{+}</math> положительных коэффициентов и количество <math>N^{-}</math> отрицательных коэффициентов.
Таким образом, общее число ненулевых коэффициентов составляет <math>N^{+} + N^{-}</math>, а оно равно рангу квадратичной формы.

{{Теорема
|id=Th1
|about=закон инерции
|statement=Число положительных и число отрицательных коэффициентов при квадратах переменных в каноническом виде данной квадратичной формы, к которому она приводится в результате невырожденного линейного преобразования, не зависит от выбора указанного преобразования.
|proof=Пусть квадратичная форма <math>f({\bf x})=f(\xi_1, \xi_2, ..., \xi_n )</math> с помощью невырожденного
преобразования <math>{\bf x} = {\bf By}</math> приводится к каноническому виду
<math>
g({\bf y}) = g(\eta_1, \eta_2, ..., \eta_n ) = \alpha_1 \eta_1^2 + \cdots + \alpha_k \eta_k^2 - \alpha_{k + 1} \eta_{k + 1}^2 - \cdots - \alpha_n \eta_n^2
</math>,
где <math>\alpha_i \ge 0</math>, <math>i = \overline {1,n}</math>, а в результате преобразования <math>{\bf x} = {\bf Cz}</math> к виду
<math>
\varphi ({\bf z}) = \varphi (\zeta_1, \zeta_2, ..., \zeta_n ) = \beta_1 \zeta_1^2 + \cdots + \beta_r \eta_r^2 - \beta_{r + 1} \eta_{r + 1}^2 - \cdots - \beta_n \zeta_n^2
</math>.

Предположим противное, что <math>k < r</math>. Заметим, что указанные линейные преобразования являются обратимыми, поэтому имеем

<math>
{\bf y} = {\bf B}^{-1}{\bf x} \Leftrightarrow \eta_i = \sum\limits_{j = 1}^n {\mu_{ij} \xi_j }, i = \overline {1,n},
</math>

<math>
{\bf z} = {\bf C}^{ - 1}{\bf x} \Leftrightarrow \zeta_i = \sum\limits_{j = 1}^n {\theta_{ij} \xi_j }, i = \overline {1,n} .
</math>

Положим <math>\eta_1 = \eta_2 = \cdots = \eta_k = 0</math>, <math>\zeta_{r + 1} = \zeta _{r + 2} = \cdots = \zeta_n = 0</math>. Указанные равенства определяют систему линейных алгебраических уравнений

<math>
\label{eq5}
\left\{
\begin{array}{l}
\sum\limits_{j = 1}^n {\mu_{ij} \xi_j = 0, i = \overline {1,k}, } \\
\sum\limits_{j = 1}^n {\theta_{ij} \xi_j = 0, i = \overline {r + 1,n} .} \\
\end{array}
\right.
</math>

Число уравнений в системе равно <math>k + n - r</math>, а число неизвестных <math>n</math>.
По предположению <math>k < r</math>, поэтому <math>k + n - r < n</math>.
Следовательно, система имеет нетривиальное решение <math>\xi_1^\ast, \xi_2^\ast, ..., \xi_n^\ast </math>.

Тогда <math>\eta_i^\ast = \sum\limits_{j = 1}^n {\mu_{ij} \xi_j^\ast }</math>, причем <math>\eta_{1 }^\ast = \eta_{2 }^\ast = \cdots = \eta_{k }^\ast = 0</math>, а <math>\zeta_i^\ast = \sum\limits_{j = 1}^n {\theta_{ij} \xi_j^\ast }</math>,
где <math>\zeta_{r + 1}^\ast = \zeta_{r + 2}^\ast = \cdots = \zeta_{n}^\ast = 0</math>, <math>i = \overline {1,n}</math>.
Поэтому, с одной стороны, имеем
<math>
f(\xi_1^\ast, \xi_2^\ast, ...,\xi_n^\ast ) = g(\eta_1^\ast, \eta_2^\ast, ...,\eta_n^\ast ) = - \alpha_{k + 1} \eta_{k + 1}^{\ast 2} - \cdots - \alpha_n \eta_n^{\ast 2} < 0,
</math>
а с другой стороны, получаем
<math>
f(\xi_1^\ast, \xi_2^\ast, ..., \xi_n^\ast ) = \varphi (\zeta_1^\ast, \zeta_2^\ast, ..., \zeta_n^\ast ) = \beta_1 \zeta_1^{\ast 2} + \cdots + \alpha_r \zeta_r^{\ast 2} > 0.
</math>

Полученное противоречие доказывает, что <math>k = r = N^{+}</math>.
}}

{{Замечание
|content=Так как число ненулевых коэффициентов в каноническом виде данной квадратичной формы не зависит от выбора преобразования и равно ее рангу, то,
очевидно, что и <math>N^{-}</math> также не зависит от способа приведения <math>f({\bf x})</math> к каноническому виду.
}}

Компьютерная графика

2021-11-12T20:21:14Z

СВ: Новая страница: «* Векторная и растровая графика * Цвет * Цветовые модели * Обработка изображений ** ...»

* [[Векторная и растровая графика]]
* [[Цвет]]
* [[Цветовые модели]]
* Обработка изображений
** [[Геометрические преобразования изображений|геометрические преобразования]]
** [[Фильтрация изображений|фильтрация изображений]]
** [[Математическая морфология|математическая морфология]]
** [[Устранение шума на изображениях|устранение шума на изображениях]]
* [[Представление линии в квадратном растре]]
* [[Алгоритмы построения окружности]]
* [[Закраска областей]]
* [[Заливка области с затравкой]]
* [[Методы устранения ступенчатости]]
* [[Отсечение отрезков]]
** [[Алгоритм Коэна-Сазерленда|двумерный алгоритм Коэна-Сазерленда]]
** [[FC-алгоритм|FC-алгоритм (Fast Clipping)]]
** [[Алгоритм Линга-Барски|двумерный алгоритм Линга-Барски]]
** [[Алгоритм Кируса-Бека|двумерный алгоритм Кируса-Бека]]
* [[Отсечение плоских фигур]]
** [[Алгоритм Сазерленда-Ходгмана|алгоритм Сазерленда-Ходгмана]]
** [[Алгоритм Вейлера-Азертона|алгоритм Вейлера-Азертона]]
* [[Аффинные преобразования на плоскости и в пространстве]]
* [[Кватернионы. Ориентация. Вращение.]]
* [[Преобразования камеры]]
* [[Виды проекций]]
* [[Способы задания кривых]]
* [[Задание кривых в форме Эрмита|в форме Эрмита]]
* [[Задание кривых в форме Безье|в форме Безье]]
* [[В-сплайны]]
* Модели описания поверхностей
** [[векторно-полигональная модель]]
** [[воксельная модель]]
** [[равномерная сетка]]
** [[неравномерная сетка]]
* [[Фракталы]]
* [[Удаление скрытых линий и поверхностей]]
** [[Алгоритм Робертса|алгоритм Робертса]]
** [[Алгоритм плавающего горизонта|алгоритм плавающего горизонта]]
** [[Метод z-буфера|метод z-буфера]]
** [[Алгоритм Варнака|алгоритм Варнака]]
* [[Метод трассировки лучей]]
* [[Моделирование освещения]]
** [[Закраска методом Гуро]]
** [[Закраска методом Фонга]]
* Алгоритмы сжатия информации без потерь
** [[RLE]]
** [[LZW]]
** [[Алгоритм Хаффмана|алгоритм Хаффмана]]
* Алгоритм сжатия изображений с потерями
** [[JPEG]]
** [[Вейвлет сжатие|вейвлет сжатие]]
** [[Фрактальное сжатие|фрактальное сжатие]]

Справка:Шаблоны

2021-11-06T18:12:12Z

СВ: Защитил страницу Справка:Шаблоны ([Редактирование=Разрешено только администраторам] (бессрочно) [Переименование=Разрешено только администраторам] (бессрочно))

== Определение ==
Использование шаблона [[Шаблон:Определение|Определение]]:
<pre>
{{Определение
|id=идентификатор (необязательно), пример: def1.
|definition=текст
}}
</pre>
*Если указан id, то на определение можно ссылаться (по [[#def1|определению такому-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.
{{Определение
|definition = Пример определения...
}}

== Утверждение ==
Использование шаблона [[Шаблон:Утверждение|Утверждение]]:
<pre>
{{Утверждение
|id=идентификатор (необязательно), пример: Prop1.
|author=Автор утверждения (необязательно)
|about=О чем утверждение(необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на утверждение можно ссылаться из статьи (по [[#Prop1|утверждению такому-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.
{{Утверждение
|statement=Пример утверждения. Формулировка...
|proof=Текст доказательства утверждения...
}}

== Лемма ==
Использование шаблона [[Шаблон:Лемма|Лемма]]:
<pre>
{{Лемма
|id=идентификатор (необязательно), пример: Lem1.
|about=О чем лемма (необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на лемму можно ссылаться из статьи (по [[#Lem1|лемме такой-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.
{{Лемма
|statement=Пример формулировки леммы...
|proof=Текст доказательства леммы...
}}

== Теорема ==
Использование шаблона [[Шаблон:Теорема|Теорема]]:
<pre>
{{Теорема
|id=идентификатор (необязательно), пример: Th1.
|author=Автор теоремы (необязательно)
|about=О чем теорема (необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на теорему можно ссылаться из статьи (по [[#Th1|теореме такой-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.
{{Теорема
|about=Неравенство Коши-Буняковского
|statement=
Пусть дано линейное пространство <math>L</math> со скалярным произведением <math>(x,y)</math>. Пусть <math>\|x\|</math> {{---}} норма, порождённая скалярным произведением, то есть <math>\|x\|\equiv\sqrt{( x, x)},\;\forall x\in L</math>. Тогда для любых <math>x, y\in L</math> имеем:
<math>|( x, y)| \leqslant \|x\|\cdot\|y\|,</math>
причём равенство достигается тогда и только тогда, когда векторы <math>x</math> и <math>y</math> линейно зависимы.
|proof=Текст доказательства теоремы...
}}

== Следствие ==
Использование шаблона [[Шаблон:Следствие|Следствие]]:
<pre>
{{Следствие
|id=идентификатор (необязательно), пример: col1.
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на теорему можно ссылаться из статьи (по [[#col1|следствию к теореме такой-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.
{{Следствие
|statement=Пример формулировки...
|proof=Текст доказательства...
}}

== Замечание ==
Использование шаблона [[Шаблон:Замечание|Замечание]]:
<pre>
{{Замечание
|num=номер (не обязательно)
|content=текст
}}
</pre>
{{Замечание
|content=Текст замечание...
}}

== Пример ==
Использование шаблона [[Шаблон:Пример|Пример]]:
<pre>
{{Пример
|num=номер (не обязательно)
|content=текст
}}
</pre>
{{Пример
|num=1
|content=Текст примера...
}}

[[Категория:Справка]]

Справка:Инструкции

2021-11-06T18:11:47Z

СВ: Защитил страницу Справка:Инструкции ([Редактирование=Разрешено только администраторам] (бессрочно) [Переименование=Разрешено только администраторам] (бессрочно))

Инструкции и требования к написанию вики-конспектов

# Для внесения конспектов нужно зарегистрироваться на сайте и написать в информации о себе имя, фамилию и группу.
# На данный момент регистрация осуществляется через преподавателей:[mailto:s.pogozhev@spbu.ru Погожев Сергей Владимирович].
# Внимательно читайте свои конспекты перед тем, как совершать попытку их сдачи. Рекомендуется читать конспекты друг друга перед отправкой на проверку, так как это позволит значительно уменьшить количество итераций сдачи конспекта.
# Не забывайте сообщать преподавателям/редакторам/кураторам о том, что конспект нужно проверить. При общении с редактором давайте ссылку на конспект, который вы пишете. При использовании электронной почты в теме письма указывайте, пожалуйста, “Вики-конспекты: ''Название вики-конспекта''”.
# Редактировать можно не только свои конспекты.

== Викификация ==
# В конспекте не должно быть орфографических, пунктуационных, речевых, фактических, логических и других ошибок.
# Используйте вики-шаблоны [[Шаблон: Определение]], [[Шаблон: Теорема]], [[Шаблон: Лемма]], [[Шаблон: Утверждение]], [[Шаблон: Следствие]], [[Шаблон: Замечание]], [[Шаблон: Пример]] ([[Справка:Шаблоны|Справка по шаблонам]]).
# Вместо черточки “-” используйте тире “{{---}}”. Для этого можно использовать [[Шаблон:---]]. Про правила использования читать [http://www.artlebedev.ru/kovodstvo/sections/97/ здесь]
# Приводите английские названия терминов, теорем, имен алгоритмов и т.д. Их лучше писать в скобках курсивом после их русских названий.
# Не используйте без нужды тег <nowiki> <br> </nowiki>. Для перевода строки в вики надо вставлять пустую строку.
# Ставьте категорию, например, <nowiki>[[Категория: Дискретная математика]]</nowiki>.
# Оформляйте ссылки на источники [http://ru.wikipedia.org/wiki/Википедия:Ссылки_на_источники правильно].

== Картинки ==
# Предпочтительный формат картинок {{---}} векторный. Для этого можно пользоваться Microsoft Visio, Inkscape, Graphviz, Metapost и т.п.

== Источники информации==
# Используйте ссылки на другие конспекты.
# В конспекте должны быть указаны источники или литература. Причем указывать ссылки не просто на википедию, а на конкретную статью (как [http://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C Википедия {{---}} Экспоненциальная запись], на английскую {{---}} как [http://en.wikipedia.org/wiki/Scientific_notation Wikipedia {{---}} Scientific notation]). Для книг достаточно указать автора, название, издание и номер страницы.
# Нарушения авторского права недопустимы.

== TeX ==
# Формулы обязательно помещаются в тег <nowiki><math></nowiki>.
# [https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B Википедия:Формулы]
# [https://meta.wikimedia.org/wiki/Help:Displaying_a_formula/ru Help:Отображение формул]
# [https://ru.overleaf.com/learn/latex/Questions/Are_there_any_tools_to_help_transcribe_mathematical_formulae_into_LaTeX%3F Are there any tools to help transcribe mathematical formulae into LaTeX?]
# В качестве знака умножения нужно использовать <code>\times</code> или <code>\cdot</code>, а не звездочку. Не следует писать <math>2 * 2 = 4 </math>, нужно <math>2 \times 2 = 4</math> или <math>2 \cdot 2 = 4</math>.
# Не опускайте знаки умножения, конъюнкции, скобки и т.п., если это может привести к неоднозначности.

== Псевдокод ==
# Используйте максимально компактный и читаемый псевдокод.
# Не ставьте фигурные скобки. Используйте отступы для группировки.
# Не ставьте круглые скобки вокруг внешнего условия if'а, while'а и т.п.
# Обозначайте присвоение с помощью знака «=», а сравнение как «==».
# TeX в псевдокоде можно использовать только в случае какого-то нестандартного оператора(а перед этим хорошо подумать и посмотреть предыдущий пункт).
# Оформляйте псевдокод как функцию, принимающую входные данные и возвращающую результат.
# Ставьте пробелы между операндами и бинарными операторами(«1 + 2», а не «1+2»). После унарных операторов перед операндом пробел ставить не нужно.
# Ставьте пробел после запятой, разделяющей аргументы функции.
# Используем какой-то определённый стиль именования переменных(например, lowerCamelCase для переменных и функций, а UpperCamelCase для классов).

[[Категория:Справка]]

Дискретная математика

2021-11-06T18:11:33Z

СВ: Защитил страницу Дискретная математика ([Редактирование=Разрешено только администраторам] (бессрочно) [Переименование=Разрешено только администраторам] (бессрочно))

== Основы теории множеств ==
* [[Множества]]
* [[Диаграммы Эйлера-Венна]]
* [[Прямое произведение множеств]]
* [[Парадокс Рассела]]
* [[Аксиомы ZFC]]
* [[Бинарные отношения]]
* [[Отношение эквивалентности]]
* [[Отношение порядка]]
* [[Лексикографический порядок]]

== Комбинаторика ==
* [[Размещения]]
* [[Сочетания]]
* [[Треугольник Паскаля]]
* [[Перебор сочетаний]]
* [[Бином Ньютона]]
* [[Мультимножества]]
* [[Мультиномиальная формула Ньютона]]
* [[Разбиения множеств]]
* [[Композиция натурального числа]]
* [[Разбиения натурального числа]]
* [[Перестановки]]
* [[Группа перестановок]]
* [[Циклы перестановки]]
* [[Тип перестановки]]
* [[Принцип включения-исключения]]
* [[Задача о беспорядках]]
* [[Мощность объединения множеств]]
* [[Число целочисленных решений системы неравенств]]

== Булевы функции ==
* [[Булевы функции]]
* [[Формулы]]
* [[Основные тождества]]
* [[Дизъюнктивная нормальная форма]]
* [[Конъюнктивная нормальная форма]]
* [[Разложение функции по переменным]]
* [[Полином Жегалкина]]
* [[Полнота системы функций]]
* [[Функции сохраняющие ноль|Функции, сохраняющие ноль]]
* [[Функции сохраняющие единицу|Функции, сохраняющие единицу]]
* [[Двойственные функции]]
* [[Самодвойственные функции]]
* [[Монотонные функции]]
* [[Линейные функции]]
* [[Критерий полноты системы функций]]

== Исчисление высказываний ==

== Исчисление предикатов ==

== Алгоритмы ==
* [[Понятие алгоритма]]
* [[Машина Тьюринга]]
* [[Стандартные конфигурации машины Тьюринга]]
* [[Вычислимые функции]]
* [[Алгоритмически неразрешимые задачи]]
* [[Сложность алгоритмов]]
* [[Полиномиальная сводимость]]
* [[Классы задач в форме распознавания свойств]]
* [[NP-полные задачи]]
* [[Задача коммивояжера]]

== Графы ==

Математический анализ

2021-11-06T18:11:25Z

СВ: Защитил страницу Математический анализ ([Редактирование=Разрешено только администраторам] (бессрочно) [Переименование=Разрешено только администраторам] (бессрочно))

== Очерк теории чисел ==
* [[Элементы теории множеств]]
* [[Символика математической логики]]
* [[Натуральные и рациональные числа]]
* [[Аксиомы Пеано]]
* [[Операции с натуральными и рациональными числами]]
* [[Аксиомы поля рациональных чисел]]
* [[Сечение множества рациональных чисел]]
* [[Вещественные числа]]
* [[Операции с вещественными числами]]
* [[Ограниченные числовые множества]]
* [[Точные верхняя и нижняя грани множества]]
* [[Принцип Коши-Кантора (о вложенных промежутках)]]
* [[Лемма Бореля–Лебега о покрытиях множества]]
* [[Счетные множества и множества мощности континуума]]
* [[Комплексные числа, операции с комплексными числами]]

== Числовые последовательности ==
* [[Понятие последовательности чисел]]
* [[Монотонные последовательности]]
* [[Ограниченные последовательности]]
* [[Предел последовательности]]
* [[Теорема о единственности предела]]
* [[Теорема об ограниченности сходящейся последовательности]]
* [[Арифметические свойства пределов последовательностей]]
* [[Связь предела последовательности чисел и предела последовательности модулей этих чисел]]
* [[Предел последовательности неотрицательных чисел]]
* [[Связь предела последовательности с пределами мажорантной и минорантной последовательностями]]
* [[Теорема о сходимости монотонной ограниченной последовательности]]
* [[Число е]]
* [[Подпоследовательности]]
* [[Теорема Больцано–Вейерштрасса]]
* [[Теорема об ограниченной расходящейся последовательности]]
* [[Принцип сходимости Коши–Больцано]]
* [[Частичные пределы]]
* [[Верхний и нижний пределы последовательности]]
* [[Сходимость к бесконечности]]
* [[Теорема о монотонной неограниченной последовательности]]
* [[Свойства последовательностей с бесконечным пределом]]
* [[Типы неопределенностей при вычислении пределов последовательностей]]
* [[Теорема Штольца]]
* [[Предел последовательностей комплексных чисел]]
* [[Связь с вещественными последовательностями]]

== Функции вещественного аргумента ==
* [[Понятие функции]]
* [[Предельная точка числового множества]]
* [[Предел функции по Гейне]]
* [[Односторонние пределы]]
* [[Верхний и нижний пределы]]
* [[Арифметические свойства предела]]
* [[Теорема о пределе сложной функции]]
* [[Теорема о пределе монотонной функции]]
* [[Теорема о функции, не имеющей предела]]
* [[Предел функции по Коши]]
* [[Теорема об эквивалентности двух определений предела функции]]
* [[Критерий сходимости Коши]]
* [[Классификация бесконечно малых и бесконечно больших величин]]
* [[Эквивалентные функции]]
* [[Замечательные пределы]]
* [[Непрерывность функций]]
* [[Равномерная непрерывность]]
* [[Теорема Кантора]]
* [[Теорема Вейерштрасса о непрерывных функциях]]
* [[Теоремы Больцано–Коши о нуле функции и о промежуточных значениях]]
* [[Теорема о непрерывности обратной функции]]
* [[Теорема о строгой монотонности взаимнооднозначной непрерывной функции]]
* [[Классификация разрывов функции]]

== Дифференциальное исчисление функций одного вещественного аргумента ==
* [[Производная функции]]
* [[Теорема о непрерывности дифференцируемой функции]]
* [[Геометрический и физический смысл производной]]
* [[Уравнение касательной и нормали]]
* [[Таблица элементарных производных]]
* [[Арифметические свойства дифференцируемых функций]]
* [[Производная сложной функции]]
* [[Производная обратной функции]]
* [[Локальные и глобальные экстремумы функций]]
* [[Теорема Ферма]]
* [[Теорема Ролля]]
* [[Теорема Лагранжа]]
* [[Теорема Коши]]
* [[Исследование поведения функции]]
* [[Теорема о монотонной функции]]
* [[Необходимые и достаточные условия экстремумов]]
* [[Производные старшего порядка]]
* [[Формула Лейбница]]
* [[Формула Тейлора]]
* [[Правило Лопиталя раскрытия неопределенностей]]
* [[Выпуклость и вогнутость функций]]
* [[Теоремы о касательных]]
* [[Точки перегиба функций]]
* [[Исследование функций и построение графиков]]
* [[Дифференциалы функции]]
* [[Инвариантность формы первого дифференциала]]
* [[Производная функции, заданной неявно или параметрически]]
* [[Методы приближенного поиска корней алгебраических уравнений]]
* [[Интерполяция и регрессия]]

== Функциональные ряды ==
*[[Степенные ряды]]
*[[Комплексные ряды]]
*[[Аппроксимация непрерывных функций степенными полиномами]]
*[[Ряды Фурье]]
*[[Сходимость классического ряда Фурье]]
*[[Сходимость в среднем рядов Фурье]]
*[[Почленное интегрирование и дифференцирование рядов Фурье]]
*[[Аппроксимация непрерывных периодических функций тригонометрическими полиномами]]
*[[Обобщенное суммирование рядов]]
*[[Бесконечные произведения]]

== Функции ограниченной вариации и интеграл Стилтьеса ==
*[[Функции ограниченной вариации]]
*[[Интеграл Стилтьеса]]

== Функции нескольких переменных ==
*[[Метрические пространства]]
*[[Пространство Rn]]
*[[Последовательности в пространстве Rn]]
*[[Функции нескольких переменных. Предел функции]]
*[[Непрерывные функции]]
*[[Дифференцируемость функций]]
*[[Производные сложной функций]]
*[[Производные по направлению]]
*[[Производные и дифференциалы старшего порядка]]
*[[Экстремумы функции нескольких переменных]]
*[[Численные методы поиска экстремума]]
*[[Теорема о неявной функции]]
*[[Системы функций]]
*[[Теорема о системе неявных функций]]
*[[Условный экстремум]]
*[[Касательные и нормали в трехмерном пространстве]]

== Интегральное исчисление функций нескольких переменных ==
*[[Двойной интеграл]]
*[[Правила вычисления двойного интеграла]]
*[[Криволинейные интегралы 1-ого рода]]
*[[Криволинейные интегралы второго рода]]
*[[Криволинейные интегралы второго рода по замкнутому контуру]]
*[[Замена переменных в двойном интеграле]]
*[[Площадь криволинейной поверхности]]
*[[Поверхностные интегралы первого рода]]
*[[Поверхностные интегралы второго рода]]
*[[Формула Стокса]]
*[[Тройной интеграл]]
*[[Формула Остроградского-Гаусса]]
*[[Элементы теории поля]]

== Интегралы, зависящие от параметра ==
*[[Равномерная сходимость функций]]
*[[Собственные интегралы, зависящие от параметра]]
*[[Несобственные интегралы, зависящие от параметра]]
*[[Интегралы Лапласа]]
*[[Эйлеровы интегралы]]
*[[Интеграл Фурье]]

== Практика ==
*[[Задачи по математическому анализу]]

Алгебра и геометрия

2021-11-06T18:11:15Z

СВ: Защитил страницу Алгебра и геометрия ([Редактирование=Разрешено только администраторам] (бессрочно))

== Полиномы и их корни ==
* [[Комплексные числа]]
* [[Теорема Безу]]
* [[Схема Горнера]]
* [[Разложение полинома на множители]]
* [[Наибольший общий делитель полиномов]]
* [[Полиномы с вещественными коэффициентами]]
* [[Рациональные дроби]]

== Матрицы и определители ==
* [[Матрицы и операции с ними]]
* [[Определители второго и третьего порядка]]
* [[Перестановки]]
* [[Определители порядка n]]
* [[Алгебраические дополнения и миноры]]
* [[Определитель ступенчатой матрицы]]
* [[Блочные матрицы]]
* [[Определитель произведения двух матриц]]
* [[Обратная матрица]]
* [[Ортогональные матрицы]]
* [[Характеристический полином матрицы]]

== Линейные пространства ==
*[[Линейные операции над векторами]]
* [[Линеал]]
* [[Линейная зависимость и независимость векторов]]
* [[Геометрический смысл линейной зависимости и независимости векторов на плоскости и в трехмерном пространстве]]
* [[Базис и размерность линеала]]
* [[Ранг матрицы]]
* [[Изоморфизм линеалов]]
* [[Аффинные пространства]]
* [[Аффинные системы координатa]]
* [[Геометрический смысл аффинных координат]]
* [[Декартовые прямоугольные системы координат]]
* [[Полярная система координат]]
* [[Цилиндрические координаты в трехмерном пространстве]]
* [[Сферические координаты в трехмерном пространстве]]
* [[Деление вектора в заданном отношении]]
* [[Скалярное произведение векторов]]
* [[Евклидовы, нормированные и метрические пространства]]
* [[Векторное произведение векторов]]
* [[Смешанное произведение трех векторов]]
* [[Двойное векторное произведение]]
== Системы линейных уравнений ==
* [[Совместные, определенные, равносильные системы линейных уравнений]]
* [[Системы линейных уравнений с квадратной матрицей]]
* [[Структура общего решения однородной системы линейных уравнений]]
* [[Структура общего решения неоднородной системы линейных уравнений]]
* [[Метод Гаусса]]
* [[Геометрический смысл систем линейных уравнений]]
* [[Уравнение с угловым коэффициентом прямой на плоскости]]
* [[Геометрический смысл систем линейных неравенств]]
* [[Нормированное уравнение плоскости (прямой)]]
* [[Пучки плоскостей (прямых на плоскости)]]
* [[Взаимное расположение прямых и плоскостей]]

== Квадратичные формы ==
* [[Приведение квадратичной формы к каноническому виду]]
* [[Приведение квадратичной формы к каноническому виду с помощью унитреугольного преобразования]]
* [[Положительно определенные квадратичные формы]]
* [[Закон инерции]]
* [[Собственные значения и собственные векторы матрицы]]
* [[Подобные матрицы]]
* [[Одновременное приведение двух квадратичных форм к каноническому виду]]
* [[Унитарные матрицы]]
* [[Эрмитовы формы]]

== Преобразование координат ==
* [[Преобразование декартовых прямоугольных координат]]
* [[Преобразование координат в n-мерном линейном пространстве]]
* [[Преобразование аффинных координат]]
* [[Линии и поверхности второго порядка]]
* [[Алгебраические линии и поверхности]]
* [[Эллипс]]
* [[Гипербола]]
* [[Парабола]]
* [[Уравнения эллипса, гиперболы, параболы в полярных координатах]]
* [[Приведение общего уравнения линии второго порядка к каноническому виду]]
* [[Классификация линий второго порядка]]
* [[Инварианты общего уравнения линии второго порядка относительно преобразования декартовых координат]]
* [[Исследование общего уравнения линии второго порядка с помощью инвариантов]]
* [[Поверхности вращения]]
* [[Эллипсоид]]
* [[Гиперболоиды]]
* [[Параболоиды]]
* [[Цилиндрические поверхности]]
* [[Конические поверхности]]

== Элементы общей теории кривых и поверхностей ==
* [[Векторная функция скалярного аргумента]]
* [[Производная векторной функции скалярного аргумента. Формула Тейлора. Интеграл от векторной функции]]
* [[Понятие кривой]]
* [[Касательная к кривой]]
* [[Нормальная плоскость кривой]]
* [[Соприкасающаяся плоскость кривой]]
* [[Спрямляющая плоскость кривой]]
* [[Нормаль]]
* [[Главная нормаль]]
* [[Бинормаль]]
* [[Длина дуги кривой]]
* [[Естественная параметризация]]
* [[Кривизна кривой]]
* [[Кручение кривой]]
* [[Формулы Френе]]
* [[Взаимное расположение кривой и граней естественного трехгранника]]
* [[Натуральные уравнения кривой]]
* [[Понятие поверхности]]
* [[Касательная прямая к поверхности, касательная плоскость и нормаль к поверхности]]
* [[Первая квадратичная форма]]
* [[Длина дуги кривой на поверхности]]
* [[Угол между кривыми на поверхности]]
* [[Площадь поверхности]]
* [[Вторая квадратичная форма поверхности]]
* [[Кривизна кривой, лежащей на поверхности]]

== Геометрическая структура систем линейных уравнений ==
* [[Линейные подпространства]]
* [[Сумма и пересечение линейных подпространств]]
* [[Многомерные плоскости]]
* [[Взаимное расположение многомерных плоскостей]]

== Геометрическая структура систем линейных неравенств ==
* [[Выпуклые множества]]
* [[Выпуклые конусы]]
* [[Отделимость выпуклых множеств]]
* [[Конечные конусы]]
* [[Выпуклое многогранное множество]]
* [[Грани многогранного множества]]
* [[Параметрическое уравнение многогранного множества]]
* [[Геометрия задачи линейного программирования]]

== Практика ==
* [[Задачи по высшей алгебре]]
* [[Задачи по аналитической геометрии]]

Заглавная страница

2021-11-06T18:10:54Z

СВ: Защитил страницу Заглавная страница ([Редактирование=Разрешено только администраторам] (бессрочно) [Переименование=Разрешено только администраторам] (бессрочно))

Добро пожаловать на сайт вики-констпектов дисциплин, которые читаются на факультете ПМ-ПУ СПбГУ.

[[Справка:Инструкции| Инструкция для студентов]].
== Математические дисциплины ==
* [[Алгебра и геометрия]]
** [[Алгебра и геометрия#Полиномы и их корни| Полиномы и их корни]]
** [[Алгебра и геометрия#Матрицы и определители| Матрицы и определители]]
** [[Алгебра и геометрия#Линейные пространства| Линейные пространства]]
** [[Алгебра и геометрия#Системы линейных уравнений| Системы линейных уравнений]]
** [[Алгебра и геометрия#Квадратичные формы| Квадратичные формы]]
** [[Алгебра и геометрия#Преобразование координат| Преобразование координат]]
** [[Алгебра и геометрия#Линии и поверхности второго порядка| Линии и поверхности второго порядка]]
** [[Алгебра и геометрия#Элементы общей теории кривых и поверхностей| Элементы общей теории кривых и поверхностей]]
** [[Алгебра и геометрия#Геометрическая структура систем линейных уравнений| Геометрическая структура систем линейных уравнений]]
** [[Алгебра и геометрия#Геометрическая структура систем линейных неравенств| Геометрическая структура систем линейных неравенств]]
** [[Алгебра и геометрия#Практика| Практика]]

* [[Математический анализ]]
** [[Математический анализ#Очерк теории чисел| Очерк теории чисел]]
** [[Математический анализ#Числовые последовательности| Числовые последовательности]]
** [[Математический анализ#Функции вещественного аргумента| Функции вещественного аргумента]]
** [[Математический анализ#Дифференциальное исчисление функций одного вещественного аргумента| Дифференциальное исчисление функций одного вещественного аргумента]]
** [[Математический анализ#Функциональные ряды| Функциональные ряды]]
** [[Математический анализ#Функции ограниченной вариации| Функции ограниченной вариации]]
** [[Математический анализ#Функции нескольких переменных| Функции нескольких переменных]]
** [[Математический анализ#Интегральное исчисление функций нескольких переменных| Интегральное исчисление функций нескольких переменных]]
** [[Математический анализ#Интегралы, зависящие от параметра| Интегралы, зависящие от параметра]]
** [[Математический анализ#Практика| Практика]]

* [[Кратные интегралы и ряды]]
* [[Основы функционального анализа]]
* [[Дифференциальные и разностные уравнения]]
* [[Теория вероятности и математическая статистика]]
* [[Теория функций комплексной переменной]]
* [[Физика]]
* [[Методы оптимизации и исследование операций]]

== Теоретическая информатика ==
* [[Дискретная математика]]
** [[Дискретная математика#Основы теории множеств| Основы теории множеств]]
** [[Дискретная математика#Комбинаторика| Комбинаторика]]
** [[Дискретная математика#Булевы функции| Булевы функции]]
** [[Дискретная математика#Исчисление высказываний| Исчисление высказываний]]
** [[Дискретная математика#Исчисление предикатов| Исчисление предикатов]]
** [[Дискретная математика#Алгоритмы| Алгоритмы]]
** [[Дискретная математика#Графы| Графы]]
* [[Теория автоматов и формальных языков]]
* [[Математическая логика и теория алгоритмов]]
* [[Теория конечных графов и ее приложения]]
* [[Алгоритмы и структуры данных]]
* [[Алгоритмы и анализ сложности]]

== Прикладная информатика и информационные технологии ==
* [[Архитектура вычислительных систем]]
* [[Операционные системы]]
* [[Компьютерные сети]]
* [[Компьютерная графика]]
* [[Введение в системы баз данных]]

== Программирование ==
* [[Основы программирования]]
* [[Языки программирования]]

Справка:Инструкции

2021-11-06T18:05:41Z

СВ: /* TeX */

Категория:Задачи по математическому анализу

2021-11-06T18:04:16Z

СВ:

[[Категория: Математический анализ]]

Категория:Задачи по математическому анализу

2021-11-06T18:03:46Z

СВ: Создана пустая страница

Демидович: Задача 56

2021-11-06T18:03:37Z

СВ: Новая страница: «Предполагая, что <math>n</math> пробегает натуральный ряд чисел, определить значение выражени...»

Предполагая, что <math>n</math> пробегает натуральный ряд чисел, определить значение выражения
<math>\lim_{n \to \infty}{\left( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \ldots + \frac{1}{n \cdot (n+1)} \right)}</math>.

== Решение ==
Заметим, что <math>\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \ldots + \frac{1}{n \cdot (n+1)}</math>
<math>= \left(1-\frac{1}{2}\right) + \left(\frac{1}{2}-\frac{1}{3}\right) + \ldots + + \left(\frac{1}{n}-\frac{1}{n+1}\right)</math>
<math>= 1 - \frac{1}{n+1}</math>.

Тогда <math>\lim_{n \to \infty}{\left( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \ldots + \frac{1}{n \cdot (n+1)} \right)}</math>
<math>=\lim_{n \to \infty}{\left(1 - \frac{1}{n+1} \right)} = 1</math>.

[[Категория: Задачи по математическому анализу]]

Задачи по математическому анализу

2021-11-06T17:55:18Z

СВ: /* Отдел I. Введение в анализ */

Демидович Б.П. Сборник задач и упражнений по математическому анализу.

== Отдел I. Введение в анализ ==
# Вещественные числа
#* [[Демидович: Задача 1|Задача 1]]
#* [[Демидович: Задача 2|Задача 2]]
#* [[Демидович: Задача 3|Задача 3]]
# Теория последовательностей
#* [[Демидович: Задача 46|Задача 46]]
#* [[Демидович: Задача 48|Задача 48]]
#* [[Демидович: Задача 56|Задача 56]]
# Понятие функции
# Графическое изображение функции
# Предел функции
# O-символика
# Непрерывность функции
# Обратная функция. Функции, заданные параметрически
# Равномерная непрерывность функции
# Функциональные уравнения

== Отдел II. Дифференциальное исчисление функций одной переменной ==
# Производная явной функции
# Производная обратной функции. Производная функции, заданной параметрически. Производная функции, заданной в неявном виде
...

[[Категория: Математический анализ]]

Заглавная страница

2021-11-06T17:52:24Z

СВ:

Категория:Математический анализ

2021-11-06T17:51:25Z

СВ: Создана пустая страница

Задачи по математическому анализу

2021-11-06T17:51:13Z

СВ: Новая страница: «Демидович Б.П. Сборник задач и упражнений по математическому анализу. == Отдел I. Введение...»

Демидович Б.П. Сборник задач и упражнений по математическому анализу.

== Отдел I. Введение в анализ ==
# Вещественные числа
#* [[Демидович: Задача 1|Задача 1]]
#* [[Демидович: Задача 2|Задача 2]]
#* [[Демидович: Задача 3|Задача 3]]
# Теория последовательностей
#* [[Демидович: Задача 46|Задача 46]]
#* [[Демидович: Задача 48|Задача 48]]
# Понятие функции
# Графическое изображение функции
# Предел функции
# O-символика
# Непрерывность функции
# Обратная функция. Функции, заданные параметрически
# Равномерная непрерывность функции
# Функциональные уравнения

== Отдел II. Дифференциальное исчисление функций одной переменной ==
# Производная явной функции
# Производная обратной функции. Производная функции, заданной параметрически. Производная функции, заданной в неявном виде
...

[[Категория: Математический анализ]]

Математический анализ

2021-11-06T17:40:28Z

СВ: /* Интегралы, зависящие от параметра */

Категория:Задачи по высшей алгебре

2021-11-06T17:34:38Z

СВ:

[[Категория: Алгебра и геометрия]]

Категория:Задачи по высшей алгебре

2021-11-06T17:34:04Z

СВ: Создана пустая страница

Фаддеев Соминский: Задача 121

2021-11-06T17:33:48Z

СВ: /* Решение */

Представить в тригонометрической форме число <math>1 + \cos \phi + i \sin \phi</math>, считая <math>-\pi \lt \phi \leq \pi</math>.

== Решение ==
Воспользуемся формулами двойного угла <math>\cos 2\varphi = \cos^2 \varphi - \sin^2 \varphi = 2 \cos^2 \varphi - 1 </math>, <math>\sin 2\varphi = 2 \sin \varphi \cos \varphi</math> и получим запись в тригонометрической форме:

<math>1 + \cos \varphi + i \sin \varphi</math>
<math>= 2 \cos^2 \frac{\varphi}{2} + i \cdot 2 \sin \frac{\varphi}{2} \cos \frac{\varphi}{2}</math>
<math>= 2 \cos \frac{\varphi}{2} \left( \cos \frac{\varphi}{2} + i \sin \frac{\varphi}{2} \right)</math>.

Так как <math>-\pi \lt \phi \leq \pi</math>, то модуль комплексного числа <math>2 \cos \frac{\varphi}{2} \gt 0</math>.

[[Категория: Задачи по высшей алгебре]]

Фаддеев Соминский: Задача 121

2021-11-06T17:29:02Z

СВ: Новая страница: «Представить в тригонометрической форме число <math>1 + \cos \phi + i \sin \phi</math>, считая <math>-\pi \lt \phi \l...»

Задачи по высшей алгебре

2021-11-06T17:18:32Z

СВ: /* Комплексные числа */

Фаддеев Д.К., Соминский И.С. Задачи по высшей алгебре. Серия "Учебники для вузов. Специальная литература". {{---}} СПб.: Издательство "Лань", 1999. {{---}} 288 с.

== Комплексные числа ==
* [[Фаддеев Соминский: Задача 121|Задача 121]]
* [[Фаддеев Соминский: Задача 182|Задача 182]]

== Действия над матрицами и определители ==
* [[Фаддеев Соминский Задача 281|Задача 281]]
* [[Фаддеев Соминский Задача 285|Задача 285]]
* [[Фаддеев Соминский Задача 307|Задача 307]]

== Системы линейных уравнений, матрицы, квадратичные формы ==

== Алгебра полиномов ==
* [[Фаддеев Соминский Задача 617|Задача 617]]

[[Категория:Алгебра и геометрия]]

Задачи по высшей алгебре

2021-11-06T17:17:57Z

СВ:

Фаддеев Д.К., Соминский И.С. Задачи по высшей алгебре. Серия "Учебники для вузов. Специальная литература". {{---}} СПб.: Издательство "Лань", 1999. {{---}} 288 с.

== Комплексные числа ==
* [[Фаддеев Соминский Задача 121|Задача 121]]
* [[Фаддеев Соминский Задача 182|Задача 182]]

== Действия над матрицами и определители ==
* [[Фаддеев Соминский Задача 281|Задача 281]]
* [[Фаддеев Соминский Задача 285|Задача 285]]
* [[Фаддеев Соминский Задача 307|Задача 307]]

== Системы линейных уравнений, матрицы, квадратичные формы ==

== Алгебра полиномов ==
* [[Фаддеев Соминский Задача 617|Задача 617]]

[[Категория:Алгебра и геометрия]]

Задачи по высшей алгебре

2021-11-06T17:17:05Z

СВ: Новая страница: «Фаддеев Д.К., Соминский И.С. Задачи по высшей алгебре. Серия "Учебники для вузов. Специальн...»

Фаддеев Д.К., Соминский И.С. Задачи по высшей алгебре. Серия "Учебники для вузов. Специальная литература". {{---}} СПб.: Издательство "Лань", 1999. {{---}} 288 с.

== Комплексные числа ==
* [[Фаддеев Соминский Задача 120|Задача 120]]
* [[Фаддеев Соминский Задача 182|Задача 182]]

== Действия над матрицами и определители ==
* [[Фаддеев Соминский Задача 281|Задача 281]]
* [[Фаддеев Соминский Задача 285|Задача 285]]
* [[Фаддеев Соминский Задача 307|Задача 307]]

== Системы линейных уравнений, матрицы, квадратичные формы ==

== Алгебра полиномов ==
* [[Фаддеев Соминский Задача 617|Задача 617]]

[[Категория:Алгебра и геометрия]]

Алгебра и геометрия

2021-11-06T17:04:01Z

СВ:

Заглавная страница

2021-11-06T16:59:20Z

СВ:

Заглавная страница

2021-11-06T16:56:25Z

СВ:

Справка:Инструкции

2021-11-06T16:49:47Z

СВ: Новая страница: «Инструкции и требования к написанию вики-конспектов # Для внесения конспектов нужно зар...»

Инструкции и требования к написанию вики-конспектов

# Для внесения конспектов нужно зарегистрироваться на сайте и написать в информации о себе имя, фамилию и группу.
# На данный момент регистрация осуществляется через преподавателей:[mailto:s.pogozhev@spbu.ru Погожев Сергей Владимирович].
# Внимательно читайте свои конспекты перед тем, как совершать попытку их сдачи. Рекомендуется читать конспекты друг друга перед отправкой на проверку, так как это позволит значительно уменьшить количество итераций сдачи конспекта.
# Не забывайте сообщать преподавателям/редакторам/кураторам о том, что конспект нужно проверить. При общении с редактором давайте ссылку на конспект, который вы пишете. При использовании электронной почты в теме письма указывайте, пожалуйста, “Вики-конспекты: ''Название вики-конспекта''”.
# Редактировать можно не только свои конспекты.

== Викификация ==
# В конспекте не должно быть орфографических, пунктуационных, речевых, фактических, логических и других ошибок.
# Используйте вики-шаблоны [[Шаблон: Определение]], [[Шаблон: Теорема]], [[Шаблон: Лемма]], [[Шаблон: Утверждение]], [[Шаблон: Следствие]], [[Шаблон: Замечание]], [[Шаблон: Пример]] ([[Справка:Шаблоны|Справка по шаблонам]]).
# Вместо черточки “-” используйте тире “{{---}}”. Для этого можно использовать [[Шаблон:---]]. Про правила использования читать [http://www.artlebedev.ru/kovodstvo/sections/97/ здесь]
# Приводите английские названия терминов, теорем, имен алгоритмов и т.д. Их лучше писать в скобках курсивом после их русских названий.
# Не используйте без нужды тег <nowiki> <br> </nowiki>. Для перевода строки в вики надо вставлять пустую строку.
# Ставьте категорию, например, <nowiki>[[Категория: Дискретная математика]]</nowiki>.
# Оформляйте ссылки на источники [http://ru.wikipedia.org/wiki/Википедия:Ссылки_на_источники правильно].

== Картинки ==
# Предпочтительный формат картинок {{---}} векторный. Для этого можно пользоваться Microsoft Visio, Inkscape, Graphviz, Metapost и т.п.

== Источники информации==
# Используйте ссылки на другие конспекты.
# В конспекте должны быть указаны источники или литература. Причем указывать ссылки не просто на википедию, а на конкретную статью (как [http://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C Википедия {{---}} Экспоненциальная запись], на английскую {{---}} как [http://en.wikipedia.org/wiki/Scientific_notation Wikipedia {{---}} Scientific notation]). Для книг достаточно указать автора, название, издание и номер страницы.
# Нарушения авторского права недопустимы.

== TeX ==
# Формулы обязательно помещаются в тег <nowiki><math></nowiki>.
# [https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B Википедия:Формулы]
# [https://ru.overleaf.com/learn/latex/Questions/Are_there_any_tools_to_help_transcribe_mathematical_formulae_into_LaTeX%3F Are there any tools to help transcribe mathematical formulae into LaTeX?]
# В качестве знака умножения нужно использовать <code>\times</code> или <code>\cdot</code>, а не звездочку. Не следует писать <math>2 * 2 = 4 </math>, нужно <math>2 \times 2 = 4</math> или <math>2 \cdot 2 = 4</math>.
# Не опускайте знаки умножения, конъюнкции, скобки и т.п., если это может привести к неоднозначности.

== Псевдокод ==
# Используйте максимально компактный и читаемый псевдокод.
# Не ставьте фигурные скобки. Используйте отступы для группировки.
# Не ставьте круглые скобки вокруг внешнего условия if'а, while'а и т.п.
# Обозначайте присвоение с помощью знака «=», а сравнение как «==».
# TeX в псевдокоде можно использовать только в случае какого-то нестандартного оператора(а перед этим хорошо подумать и посмотреть предыдущий пункт).
# Оформляйте псевдокод как функцию, принимающую входные данные и возвращающую результат.
# Ставьте пробелы между операндами и бинарными операторами(«1 + 2», а не «1+2»). После унарных операторов перед операндом пробел ставить не нужно.
# Ставьте пробел после запятой, разделяющей аргументы функции.
# Используем какой-то определённый стиль именования переменных(например, lowerCamelCase для переменных и функций, а UpperCamelCase для классов).

[[Категория:Справка]]

Заглавная страница

2021-11-05T10:16:39Z

СВ:

Заглавная страница

2021-11-05T10:13:44Z

СВ:

Заглавная страница

2021-11-05T09:57:30Z

СВ:

Математический анализ

2021-11-04T21:29:46Z

СВ: Новая страница: «== Очерк теории чисел == * Элементы теории множеств * Символика математической логики *...»

Категория:Справка

2021-11-04T15:47:44Z

СВ: Создана пустая страница

Справка:Шаблоны

2021-11-04T15:47:28Z

СВ: Новая страница: «== Определение == Использование шаблона Определение: <pre> {{Определен...»

Шаблон:Следствие

2021-11-04T15:37:11Z

СВ:

<noinclude>
Использование шаблона [[Шаблон:Следствие|Следствие]]:
<pre>
{{Следствие
|id=идентификатор (необязательно), пример: col1.
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на следствие можно ссылаться из статьи (по [[#col1|следствию к теореме такой-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.

[[Категория:Шаблоны]]
</noinclude>
<includeonly>{{#if:{{{id|}}}|<span id="{{{id}}}"></span>|}}
<div width="100%" style="width:100%;background-color:#EEEEEE; border-left:3px solid #6699cc; padding:3px;">'''Следствие''':</div>
<div style="width:100%; background-color:#fdfdfd; border-left:3px solid #6699cc; padding:3px;"><div style="margin:6px auto;width:100%;">{{{statement}}}</div></div>
{{#if:{{{proof|}}}|<div style="width:100%;border:1px dashed #6699cc;padding:4px;margin:0 auto;"><div>'''Доказательство:'''</div>
{{{proof}}}
</div>
<div style="text-align:right;" width="100%"><math>\blacksquare</math></div>|}}
</includeonly>

Шаблон:Утверждение

2021-11-04T15:08:45Z

СВ:

<noinclude>
Использование шаблона [[Шаблон:Утверждение|Утверждение]]:
<pre>
{{Утверждение
|id=идентификатор (необязательно), пример: Prop1.
|author=Автор утверждения (необязательно)
|about=О чем утверждение(необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на утверждение можно ссылаться из статьи (по [[#Prop1|утверждению такому-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.

[[Категория:Шаблоны]]
</noinclude>
<includeonly>{{#if:{{{id|}}}|<span id="{{{id}}}"></span>|}}
<div width="100%" style="background-color: #EEEEEE;border-left:3px solid #33bbcc;padding:3px;">'''Утверждение{{#if:{{{author|}}}|{{#if:{{{about|}}}| ({{{author}}}, {{{about}}})| ({{{author}}})}}|{{#if:{{{about|}}}| ({{{about}}})|}}}}''':</div>
<div style="width:100%; background-color: #fdfdfd;border-left:3px solid #33bbcc;padding:3px;">
<div style="margin:10px auto;width:100%;">{{{statement}}}</div></div>
{{#if:{{{proof|}}}|<div style="border:1px dashed #3333cc;padding:4px;"><div>'''Доказательство:'''</div>
{{{proof}}}
</div>
<div style="text-align:right;" width="100%"><math>\blacksquare</math></div>|}}
</includeonly>

Размещения

2021-11-04T13:26:31Z

СВ:

{{Определение
|id=def1
|definition=
''Размещением'' из <math>n</math> элементов по <math>k</math> называется упорядоченная выборка без повторений
объема <math>k</math> из <math>n</math>-элементного множества.
}}

Не умаляя общности, можно называть размещением из <math>n</math> элементов по <math>k</math> упорядоченный набор из <math>k</math> различных чисел,
принадлежащих множеству <math>\{1, ..., n\}</math>.

Количество различных размещений из <math>n</math> по <math>k</math> обозначают <math>A_n^k</math> .

{{Пример
|num=1
|content= Пусть на экзамене у преподавателя <math>n</math> различных билетов и сдавать пришло <math>k</math> студентов.
Тогда существует ровно <math>A_n^k</math> способов выдать всем студентам по одному билету для подготовки.
}}

{{Пример
|num=2
|content= Пусть <math>S = \{1,2,3\}</math>. Тогда <math>(1,2)</math>, <math>(1,3)</math>, <math>(2,1)</math>, <math>(2,3)</math>, <math>(3,1)</math>, <math>(3,2)</math> {{---}} все возможные размещения из трех элементов по два.
}}

{{Утверждение
|statement=Пусть <math>k,n\in\mathbb{N}</math> и <math>1 \leq k \leq n</math>.
Тогда <math>A_n^k = n\cdot (n-1)\cdot ... \cdot(n-k+1) =\frac{n!}{(n-k)!}</math>.
|proof=
Действительно, существует <math>n</math> различных способов выбрать первый элемент набора из элементов множества <math>\{1, ..., n\}</math>.
Аналогично, существует <math>n-1</math> способ выбора второго элемента и так далее.
}}

[[Категория:Комбинаторика]]

Сочетания

2021-11-04T13:26:06Z

СВ:

{{Определение
|id=def1
|definition=
''Сочетанием'' из <math>n</math> элементов по <math>k</math> называется неупорядоченная выборка без повторений объема <math>k</math> из <math>n</math>-элементного множества.
}}
Не умаляя общности, можно называть сочетанием из <math>n</math> элементов по <math>k</math> неупорядоченный набор из <math>k</math> различных чисел,
принадлежащих множеству <math>\{1, ..., n\}</math>.

Количество различных сочетаний из <math>n</math> по <math>k</math> обозначают <math>C_n^k</math> или <math>\binom{n}{k}</math>.
{{Пример
|num=1
|content=Предположим, из <math>n</math> участников спортивного клуба на соревнования должны поехать какие-то <math>k</math>.
Тогда имеется <math>C_n^k</math> различных возможности собрать команду.
}}
{{Пример
|num=2
|content= Пусть <math>S = \{1,2,3\}</math>. Тогда <math>\{1,2\}</math>, <math>\{1,3\}</math>, <math>\{2,3\}</math> {{---}} все возможные cочетания из трех элементов по два.
}}
{{Утверждение
|statement=Пусть <math>k,n\in\mathbb{N}</math> и <math>1 \leq k \leq n</math>.
Тогда <math>\binom{n}{k} = \frac{n!}{k!(n-k)!}</math>.
|proof=
Действительно, каждому сочетанию из <math>n</math> по <math>k</math> соответствует <math>k!</math> различных размещений из <math>n</math> по <math>k</math> с различным порядком следования элементов.
Тогда <math>\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}</math>.
}}

== Свойства числа сочетаний ==

<math>
\binom{n}{k}\cdot\binom{k}{l} = \binom{n}{l}\cdot \binom{n-l}{k-l}.
</math>

Действительно,
<math>
\binom{n}{k}\cdot\binom{k}{l}= \frac{n!}{k!(n-k)!}\cdot\frac{k!}{l!(k-l)!} \cdot \frac{(n-l)!}{(n-l)!}=
\frac{n!}{l!(n-l)!}\cdot\frac{(n-l)!}{(k-l)!(n-k)!} = \binom{n}{l}\cdot \binom{n-l}{k-l}.
</math>

Интуитивно формулу можно описать как разбиение множества
из <math>n</math> элементов на три подмножества мощностей <math>l</math>, <math>k-l</math>, <math>n-k</math> соответственно.
Левая часть равенства описывает выбор сначала <math>k</math> элементов из <math>n</math>, а затем <math>l</math> элементов из выбранных <math>k</math>.
Получим все варианты разбиения исходного множества на три подмножества указанных мощностей.

Правая часть равенства соответствует выбору сначала <math>l</math> элементов из <math>n</math>,
а затем <math>k-l</math> элементов из оставшихся <math>n-l</math>. Получим те же варианты подмножеств.

== Алгоритм перебора сочетаний ==

Пусть <math>x_1, x_2, ..., x_k</math> {{---}} числа из множества <math>\{1,2,...,n\}</math>, вошедшие в сочетание, причем <math>x_1 \lt x_2 \lt ... \lt x_k</math>.

Пусть в начальный момент времени сочетание состоит из первых <math>k</math> чисел: <math>x_i = i, i=\overline{1,k}</math>.

На каждом шаге будем просматривать вектор <math>(x_1, x_2, ..., x_k)</math>, начиная с <math>x_k</math>, и искать первую такую компоненту <math>x_i</math>,
которую можно увеличить (нельзя увеличить <math>x_k</math>, если он равен <math>n</math>; <math>x_{k-1}</math>, если он равен <math>n-1</math> и так далее).

Если такой компоненты не найдется, алгоритм завершает свою работу.
В противном случае, пусть <math>i</math> {{---}} такое наибольшее число, что <math>x_i \lt n-k+i</math>.
Увеличим <math>x_i</math> на единицу, а для всех <math>x_t, t=\overline{i+1,k}</math>, присваиваем значения <math>x_t = x_i+(t-i)</math>.
Повторяем процесс нужное число раз.

=== Пример ===
{{Пример
|num=1
|content=Рассмотрим, как работает алгоритм для <math>n=5</math> и <math>k=3</math>.
# Сначала <math>x = (x_1, x_2, x_3) = (1,2,3)</math>.
# Увеличиваем <math>x_3</math>: <math>x = (1,2,4)</math>.
# Увеличиваем <math>x_3</math>: <math>x = (1,2,5)</math>.
# <math>x_3</math> больше увеличить нельзя. Увеличиваем <math>x_2</math> и переназначаем значение <math>x_3</math>: <math>x = (1,3,4)</math>.
# <math>x = (1,3,5)</math>
# <math>x = (1,4,5)</math>
# <math>x = (2,3,4)</math>
# <math>x = (2,3,5)</math>
# <math>x = (2,4,5)</math>
# <math>x = (3,4,5)</math>

Таким образом, мы перебрали все сочетания из 5 по 3.
}}

[[Категория:Комбинаторика]]

Самодвойственные функции

2021-11-04T13:25:29Z

СВ: Новая страница: «{{Определение |definition= Функция <math>f(x_1, ..., x_n)\in P_2</math> {{---}} самодвойственная, если <math>f^*(x_1, ..., x...»

{{Определение
|definition=
Функция <math>f(x_1, ..., x_n)\in P_2</math> {{---}} самодвойственная, если <math>f^*(x_1, ..., x_n) = f(x_1, ..., x_n)</math>.
}}
Множество всех самодвойственных функций обозначим за <math>S</math>:
<math>S = \{ f | f(x_1, ..., x_n) \in P_2, f^*(x_1, ..., x_n) = f(x_1, ..., x_n) \}</math>.
{{Пример
|num=1
|content=
Пусть <math>f = x\vee y</math>, <math>f^* = \overline{\overline x \vee \overline y} = xy</math>.

<math>f\neq f^*</math> и, следовательно, <math>f^*</math> не является самодвойственной.
}}
{{Пример
|num=2
|content=
Пусть <math>f</math> {{---}} функция голосования: <math>f(x,y,z) = xy\vee xz\vee yz</math>.

<math>f^*(x,y,z) = \overline{\overline x\cdot \overline y \vee \overline x\cdot \overline z \vee \overline y\cdot \overline z} </math>
<math>= \overline{\overline x\cdot \overline y} \cdot \overline{\overline x\cdot \overline z} \cdot \overline{\overline y\cdot \overline z} </math>
<math>= (x\vee y)(x\vee z)(y\vee z) </math>
<math>= (x\vee xz\vee xy\vee yz)(y\vee z)</math>
<math>= xy\vee xz \vee xyz \vee xz \vee xy\vee xyz \vee yz \vee yz </math>
<math>= xy \vee xz \vee yz \vee xyz </math>
<math>= xy \vee xz \vee yz = f(x,y,z).</math>

Функция голосования {{---}} самодвойственная.
}}
Табличный вид функции голосования:
{|class="wikitable"
! x !! y !! z !! f(x,y,z)
|-
| 0 || 0 || 0 || 0
|-
| 0 || 0 || 1 || 0
|-
| 0 || 1 || 0 || 0
|-
| 0 || 1 || 1 || 1
|-
| 1 || 0 || 0 || 0
|-
| 1 || 0 || 1 || 1
|-
| 1 || 1 || 0 || 1
|-
| 1 || 1 || 1 || 1
|}

Нижняя половина столбца значений повторяет перевернутую и инвертированную верхнюю. Это верно для любой самодвойственной функции.

== Принцип двойственности ==
{{Утверждение
|about=Принцип двойственности
|statement=
Пусть формула <math>\mathcal U = f(\mathcal U_1,...,\mathcal U_n)</math> реализует функцию <math>F (x_1,...,x_m)</math>,
где <math>\mathcal U_i</math> {{---}} формулы, реализующие <math>f_{i}(x_{j_1},...,x_{j_{k_i}})</math>, <math>i=\overline{1,n}</math>.

Пусть <math>\mathcal U_i^*</math> {{---}} формулы реализующие <math>f_{i}^*</math>, <math>i=\overline{1,n}</math>.

Тогда формула <math>\mathcal U^* = f^*(\mathcal U^*_1,...,\mathcal U^*_n)</math> реализует функцию <math>F^*(x_1,...,x_m)</math>.
|proof=
<math>F(x_1,...,x_m) = f(f_{1}(x_{i_1}, ..., x_{i_{k_1}}), ..., f_{n}(x_{j_1}, ..., x_{j_{k_n}})).</math>

Тогда, по определению двойственной функции <br />
<math>
F^*(x_1,...,x_m) = \overline f(f_{1}(\overline x_{i_1},...,\overline x_{i_{k_1}}), ..., f_{n}(\overline x_{j_1}, ..., \overline x_{j_{k_n}}))
</math>
<math>
= \overline f(\overline {\overline f}_{1}(\overline x_{i_1},...,\overline x_{i_{k_1}}), ..., \overline {\overline f}_{n}(\overline x_{j_1},...,\overline x_{j_{k_n}}))
</math>
<math>
= \overline f(\overline {f^*}_{1}(x_{i_1},..., x_{i_{k_1}}),...,\overline {f^*}_{n}(x_{j_1},...,x_{j_{k_n}}))
</math>
<math>
= f^*({f^*}_{1}(x_{i_1},..., x_{i_{k_1}}), ..., {f^*}_{n}(x_{j_1},...,x_{j_{k_n}})).
</math>

С другой стороны, формула $f^*(\mathcal U_1^*,...,\mathcal U_n^*)$ реализует функцию
<math>
f^*(f_{\mathcal U_1^*}(x_{i_1},..., x_{i_{k_1}}), ..., f_{\mathcal U_n^*} (x_{j_1},...,x_{j_{k_n}}))
</math>
<math>
= f^*({f^*}_{1}(x_{i_1},..., x_{i_{k_1}}), ..., {f^*}_{n}(x_{j_1},...,x_{j_{k_n}})).
</math>

Таким образом, один из способов задать функцию <math>F^*(x_1, ...,x_m)</math> формулой имеет вид <math>\mathcal U^* = f^*(\mathcal U_1^*, ..., \mathcal U_n^*)</math>.
}}
{{Пример
|num=3
|content=
Пусть <math>F(x,y,z) = (x\equiv y)\supset(y~|~z)= f(f_1(x,y),f_2(y,z))</math>, <br />
<math>f^*(x,y) = (x\supset y)^* = \overline{\overline x\supset\overline y}= \overline{x\vee \overline y} = \overline x y</math>, <br />
<math>f_1^*(x,y) = (x\equiv y)^* = \overline{\overline x\equiv \overline y} = \overline{x\equiv y} = x\oplus y</math>, <br />
<math>f_2^*(x,y) = (x~|~ y)^* = \overline{\overline x~|~\overline y} = \overline{x\vee y} = \overline x\wedge \overline y = x\downarrow y</math>.

Тогда по принципу двойственности <math>F^*(x,y,z)</math> будет иметь вид
<math>F^*(x,y,z) = f^*(f_1^*(x,y),f_2^*(y,z)) = \overline{(x\oplus y)}\wedge (y\downarrow z)</math>.

Действительно,
<math>F^*(x,y,z) = \neg {((\overline x\equiv \overline y)\supset(\overline y~|~\overline z))} </math>
<math>= \neg (\overline{(x\equiv y)}\vee(y\vee z)) </math>
<math>= \overline{\overline{(x\equiv y)}}\wedge\overline{(y\vee z)} </math>
<math>= \overline{(x\oplus y)}\wedge (y\downarrow z)</math>.
}}
{{Следствие
|statement=
Пусть <math>f(x_1,...,x_n)</math> задана формулой <math>\mathcal U</math> над множеством функций <math>\{0,1, \neg, \vee,\wedge\}</math>.
Тогда <math>f^*(x_1,...,x_n)</math> задается формулой, полученной из <math>\mathcal U</math> заменой: нулей на единицы, единиц на нули, конъюнкций на дизъюнкции, дизъюнкций на конъюнкции.
|proof=
Пусть <math>f=\neg f_1</math>.
Это значит, что <math>f = f_0(f_1)</math>, где <math>f_0(x) = \overline x</math>.

Тогда <math>f_0^* = \overline{\overline{\overline x}} = \overline x = f_0</math>.

Следовательно, <math>f^* = f_0^*(f_1^*) = f_0(f_1^*) = \neg f_1^*</math>.

Пусть <math>f = f_1\vee f_2</math>. Другими словами, <math>f = f_0(f_1,f_2)</math>, <math>f_0(x,y) = x\vee y</math>.

Тогда <math>f_0^* = \overline{\overline x \vee \overline y} = x\wedge y</math> и
<math>f^* = f_0^*(f_1^*, f_2^*) = f_1^*\wedge f_2^*</math>.

Пусть <math>f = f_1\wedge f_2</math>. Другими словами, <math>f = f_0(f_1,f_2)</math>, <math>f_0(x,y) = x\wedge y</math>.

Тогда <math>f_0^* = \overline{\overline x \wedge \overline y} = x\vee y</math> и <math>f^* = f_0^*(f_1^*, f_2^*) = f_1^*\vee f_2^*</math>.

Пусть <math>f = 0</math>. Тогда <math>f^* = 1</math>.

Пусть <math>f=1</math>. Тогда <math>f^* = 0</math>.

Пусть <math>f = x</math>. Тогда <math>f^* = \overline{\overline x}=x = f</math>.
}}
{{Пример
|num=4
|content=
Пусть, <math>f(x,y,z) = 0\wedge x\wedge \overline y\vee 1\wedge y\wedge \overline z</math>.

Тогда,
<math>
f^*(x,y,z) = \overline f(\overline x, \overline y, \overline z)
</math>
<math>=\neg(0\wedge \overline x\wedge\overline{\overline y} \vee 1 \wedge \overline y\wedge \overline{ \overline z})
</math>
<math>= \overline{(0\wedge \overline x\wedge y)} \wedge\overline{(1 \wedge \overline y\wedge z)} </math>
<math>= (1 \vee x \vee \overline y)\wedge (0\vee y \vee \overline z)</math>.
}}
{{Пример
|num=5
|content=
Пусть <math>f(x,y,z) = (\overline{0\vee x})(y\vee \overline x z)</math>.

Тогда
<math>f^*(x,y,z) = \neg((\overline{0\vee \overline x})(\overline y\vee \overline{\overline x}\wedge \overline z))</math>
<math>=\neg(1\wedge x)(\overline y\vee x\wedge \overline z))</math>
<math>=(\overline{1\wedge x})\vee(\overline{\overline y\vee x\wedge \overline z}))</math>
<math>=(\overline{1\wedge x})\vee(y\wedge ( \overline x\vee z)))</math>.
}}

== Замкнутость класса ==

{{Утверждение
|statement=
Класс функций <math>S</math> замкнут.
|proof=
Рассмотрим суперпозицию ранга 1 от функций из <math>S</math>.

a) Пусть <math>f(x_1,...,x_n)\in S</math> и <math>g(x_1,...,x_{j-1},x_{j+1},...,x_n, y) = f(x_1,...,x_{j-1},y,x_{j+1},...,x_{n})</math>.

Тогда
<math>\overline g(\overline x_1,...,\overline x_{j-1},\overline x_{j+1},...,\overline x_n, \overline y) </math>
<math>= \overline f(\overline x_1,...,\overline x_{j-1},\overline y,\overline x_{j+1},...,\overline x_{n})</math>
<math>= f^*(x_1,...,x_{j-1},y,x_{j+1},...,x_{n})</math>
<math>= f(x_1,...,x_{j-1},y,x_{j+1},...,x_{n})</math>
<math>= g(x_1,...,x_{j-1},x_{j+1},...,x_n, y)</math>.

Следовательно <math>g(x_1,...,x_{j-1},x_{j+1},...,x_n, y)\in S</math>.

b) Пусть <math>f(x_1,...,x_n)\in S</math> и <math>h(y_1, ...,y_m)\in S</math> и
<math>g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)</math>
<math>=f(x_1,...,x_{j-1},h(y_1,...,y_{m}),x_{j+1},...,x_{n})</math>.

Тогда
<math>\overline g(\overline x_1,...,\overline x_{j-1}, \overline x_{j+1},...,\overline x_n, \overline y_1,...,\overline y_m)</math>
<math>= \overline f(\overline x_1,...,\overline x_{j-1}, h(\overline y_1,...,\overline y_{m}),\overline x_{j+1},...,\overline x_{n})</math>
<math>= \overline f(\overline x_1,...,\overline x_{j-1}, \overline{\overline h}(\overline y_1,...,\overline y_{m}),\overline x_{j+1},...,\overline x_{n})</math>
<math>= \overline f(\overline x_1,...,\overline x_{j-1}, \overline{ h^*}( y_1,...,y_{m}),\overline x_{j+1},...,\overline x_{n})</math>
<math>= f^*(x_1,..., x_{j-1}, { h^*}( y_1,...,y_{m}), x_{j+1},..., x_{n})</math>
<math>= f(x_1,..., x_{j-1}, { h}( y_1,...,y_{m}), x_{j+1},..., x_{n})</math>
<math>= g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)</math>.

Получаем, что <math>g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)\in S</math>.

Таким образом, <math>[S] = S</math>.
}}
{{Замечание
|content=
Тождественная функция $f(x)=x$ лежит в классе $S$.

Конъюнкция $f(x) = x \wedge y$ не лежит в $S$.

Таким образом, $S\neq \varnothing$ и $S\neq P_2$.
}}
{{Лемма
|about=о несамодвойственной функции
|statement=
Пусть <math>f(x_1, ..., x_n) \notin S</math>. Тогда, подставляя в <math>f</math> вместо аргументов переменные <math>x</math> и их отрицание <math>\overline x</math>, можно получить константу.
|proof=
Пусть <math>(\alpha_1,...,\alpha_n)</math>, <math>\alpha_i\in\{0,1\}</math>, такой набор, что <math>f(\alpha_1,...,\alpha_n) = f(\overline \alpha_1,...,\overline\alpha_n)</math>.
Такой набор обязан существовать в силу несамодвойственности функции <math>f</math>.

Рассмотрим функцию <math>\varphi(x) = f(x^{\alpha_1}, ..., x^{\alpha_n})</math>.

Тогда
<math>\varphi(0) = f(0^{\alpha_1}, ..., 0^{\alpha_n}) = f({\alpha_1}^0,...,{\alpha_n}^0) = f(\overline\alpha_1,...,\overline \alpha_n) </math>
<math> = f(\alpha_1,...,\alpha_n) = f(1^{\alpha_1},...,1^{\alpha_n}) = \varphi(1)</math>.

Следовательно $\varphi(x)$ {{---}} константа.
}}
{{Пример
|content=
Получение константы из несамодвойственной функции

Пусть <math>f(x,y,z) = x\supset (y\oplus z)</math>.

Это несамодвойственная функция, поскольку <math>f(0,1,0) = 0\supset (1\oplus 0) =1= 1\supset (0\oplus 1) =f(1,0,1)</math>.

Тогда <math>\varphi(x) = f(\overline x, x, \overline x)</math> {{---}} константа.

Действительно, <math>\varphi(x) = \overline x\supset(x\oplus \overline x) = \overline x\supset 1 = 1</math>.
}}

Шаблон:Утверждение

2021-11-04T13:22:20Z

СВ:

<noinclude>
Использование шаблона [[Шаблон:Утверждение|Утверждение]]:
<pre>
{{Утверждение
|id=идентификатор (необязательно), пример: Prop1.
|author=Автор утверждения необязательно)
|about=О чем утверждение(необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на утверждение можно ссылаться из статьи (по [[#Prop1|утверждению такому-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.

[[Категория:Шаблоны]]
</noinclude>
<includeonly>{{#if:{{{id|}}}|<span id="{{{id}}}"></span>|}}
<div width="100%" style="background-color: #EEEEEE;border-left:3px solid #33bbcc;padding:3px;">'''Утверждение{{#if:{{{author|}}}|{{#if:{{{about|}}}| ({{{author}}}, {{{about}}})| ({{{author}}})}}|{{#if:{{{about|}}}| ({{{about}}})|}}}}''':</div>
<div style="width:100%; background-color: #fdfdfd;border-left:3px solid #33bbcc;padding:3px;">
<div style="margin:10px auto;width:100%;">{{{statement}}}</div></div>
{{#if:{{{proof|}}}|<div style="border:1px dashed #3333cc;padding:4px;"><div>'''Доказательство:'''</div>
{{{proof}}}
</div>
<div style="text-align:right;" width="100%"><math>\blacksquare</math></div>|}}
</includeonly>

Шаблон:Теорема

2021-11-04T13:21:21Z

СВ:

<noinclude>
Использование шаблона [[Шаблон:Теорема|Теорема]]:
<pre>
{{Теорема
|id=идентификатор (необязательно), пример: Th1.
|author=Автор теоремы (необязательно)
|about=О чем теорема (необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}
</pre>
* После этого на теорему можно ссылаться из статьи (по [[#Th1|теореме такой-то]])
* Все '''id''' должны быть уникальными внутри статьи и не совпадать с названиями секций.

[[Категория:Шаблоны]]
</noinclude>
<includeonly>{{#if:{{{id|}}}|<span id="{{{id}}}"></span>|}}
<div width="100%" style="background-color: #EEEEEE;border-left:3px solid #3333cc;padding:3px;">'''Теорема{{#if:{{{author|}}}|{{#if:{{{about|}}}| ({{{author}}}, {{{about}}})| ({{{author}}})}}|{{#if:{{{about|}}}| ({{{about}}})|}}}}''':</div>
<div style="width:100%; background-color: #fdfdfd;border-left:3px solid #3333cc;padding:3px;">
<div style="margin:10px auto;width:100%;">{{{statement}}}</div></div>
{{#if:{{{proof|}}}|<div style="border:1px dashed #3333cc;padding:4px;"><div>'''Доказательство:'''</div>
{{{proof}}}
</div>
<div style="text-align:right;" width="100%"><math>\blacksquare</math></div>|}}
</includeonly>