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

Заливка области с затравкой

2022-12-03T18:15:24Z

StudentL: Новая страница: «== Основы == Алгоритм применим, когда область, подлежащая заливке, не является многоугольн...»

== Основы ==
Алгоритм применим, когда область, подлежащая заливке, не является многоугольником. Множество пикселей на растре не задает область однозначно, поэтому требуется задать координаты "затравочного" пикселя, принадлежащего области.
При данном способе заливки тем или иным способом выбирается произвольная точка, являющаяся заведомо внутренней для заданной области. Эта точка закрашивается. Закрашиваются также все ее не закрашенные соседи по заданному критерию связности и их адреса записываются в стек. Далее из стека извлекается адрес очередной точки и с ней поступают точно так же, как с предыдущей. Процедура повторяется до тех пор, пока в стеке будет находиться адрес хотя бы одной точки.

== Пример простого алгоритма ==
Простейший алгоритм заполнения с затравкой - это так называемый алгоритм короеда, получивший подобное название, поскольку заполняемая область последовательно "выедается" по одному пикселю.
При обходе соседних пикселей может рассматриваться и 4-связность , и 8-связность. В зависимости от этого результат будет различным.
[[Файл:Алгос заливки.jpg|без рамки|центр]]

== Модифицированный алгоритм ==
Простой алгоритм выше можно модифицировать, вместо того что бы на каждой итерации закрашивать один пиксель, закрашивать линию. Для этого используется пространственная когерентность:
* пиксели в строке меняются только на границах
* при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен, или меняется на 1 пиксель
Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пикселя, что приводит к существенному уменьшению размера стека.[[Файл:Модифицированное заполнение.jpg|мини]]
Последовательность работы алгоритма следующая:
# Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4
# Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксель. Пусть это ХLeft и ХRight, соответственно.
# Анализируется строка ниже закрашиваемой в пределах от ХLeft до ХRight и в ней находятся крайние правые пиксель всех не закрашенных фрагментов. Их координаты заносятся в стек
# То же самое проделывается для строки выше закрашиваемой

Файл:Снимок экрана (106).png

2022-12-03T18:03:09Z

StudentL:

то же

Файл:Алгос заливки.jpg

2022-12-03T17:59:44Z

StudentL:

блок-схема алгоритма и поэтапный обход

Файл:Модифицированное заполнение.jpg

2022-12-03T17:57:19Z

StudentL:

Поэтапно представлены способы заливки фигуры

Множества

2021-12-28T07:31:43Z

StudentL:

== Определения множеств ==
{{Определение
|definition=
Множество {{---}} любая совокупность элементов одной природы, мыслимая как единое целое.
}}
{{Определение
|definition=
Пустое множество {{---}} множество, не содержащее элементов. Обозначается <math>\varnothing</math>.
}}
{{Определение
|definition=
Множества считаются равными, если они состоят из одних и тех же элементов.
}}
{{Определение
|definition=
Два множества называются равномощными, если каждому элементу одного множества взаимно-однозначно сопоставляется один и только один элемент другого.
}}
{{Определение
|definition=
Множество, равномощное множеству всех натуральных чисел <math>\N</math>, называют ''счетным множеством''.
}}
{{Определение
|definition=
Мощность множества {{---}} количество элементов множества. Обозначают <math>\vert A \vert</math>. Используется для конечных множеств.
}}

== Подмножества ==
{{Определение
|definition=
Обозначают <math>A \subseteq B</math> и говорят, что множество <math>A</math> является подмножеством множества <math>B</math>, если каждый элемент множества <math>A</math> является элементом множества <math>B</math>.
}}
Если также известно, что <math>A \neq B</math>, говорят, что <math>A</math> является собственным (или
строгим) подмножеством множества <math></math> и пишут <math>A \subset B</math>.
{{Пример
|content=
1) <math>\{ 1,\ 3 \} \subset \{ 3,\ 5,\ 1,\ 4 \}</math> <br />
2) <math>\{ k,\ l,\ j \} \subseteq \{ l,\ j,\ k \} </math>
}}
{{Определение
|definition=
Множество всех подмножеств множества <math>A</math> будем обозначать <math>2^A</math>. Мощность
множества всех подмножеств множества с <math>n</math> элементами равна <math>2^n\colon \ \vert 2^A \vert = 2^{\vert A \vert}</math>.
}}
{{Пример
|content=
Пусть <math>A = \{ a,\ b,\ c \}</math>. Тогда <math>2^A = \{ \varnothing,\ \{a\},\ \{b\},\ \{c\},\ \{a,\ b\},\ \{a,\ c\},\ \{b,\ c\},\ \{A\} \}</math>.
Видно, что в этом множестве <math>2^{\vert A \vert} = 2^3 = 8</math> элементов.
}}
== Операции над множествами ==
=== Объединение множеств ===
<math>A \cup B = \{ x \mid x \in A\ </math> или <math>\ x \in B \}</math>
=== Пересечение множеств ===
<math>A \cap B = \{ x \mid x \in A\ </math> и <math>\ x \in B \}</math>
=== Дополнение множества ===
<math>\overline{A} = \{ x \mid x \in U\ </math> и <math>\ x \notin A \}</math>, где <math>U</math> {{---}} универсальное множество.
=== Разность множеств ===
<math>A\ \backslash\ B = \{ x \mid x \in A\ </math> и <math>\ x \notin B \}</math>
=== Симметрическая разность множеств ===
<math>A\ \dot - \ B = \left ( A\ \backslash\ B \right ) \cup \left ( B\ \backslash\ A \right )</math>
{{Утверждение
|id=mnoj
|about=Основные тождества алгебры множеств
|statement=
Пусть <math>A,\ B,\ C,\</math> произвольные подмножества множества <math>U</math>, тогда выполняются следующие тождества:

<math>1)\ </math> ''Коммутативность:'' <math>\ a)\ </math> <math>A \cup B = B \cup A ;\quad</math> <math>b)\ A \cap B = B \cap A</math>

<math>2)\ </math> ''Ассоциативность:'' <math>\ a)\ A \cup \left ( B \cup C \right ) = \left ( A \cup B \right ) \cup C ; \quad</math> <math>b)\ A \cap \left ( B \cap C \right ) = \left (A \cap B \right ) \cap C </math>;

<math>3)\ </math> <math>a)</math> ''Дистрибутивность'' <math>\cup</math> ''относительно'' <math>\cap: \ </math> <math>A \cup \left ( B \cap C \right ) = \left ( A \cup B \right ) \cap \left ( A \cup C \right )</math>

<math>\quad\ \ b)</math> ''Дистрибутивность'' <math>\cap</math> ''относительно'' <math>\cup: \ </math> <math>A \cap \left ( B \cup C \right ) = \left ( A \cap B \right ) \cup \left ( A \cap C \right )</math>

<math>4)\ </math> <math>A \cup \varnothing = A</math>; <math>\quad A \cap \varnothing = \varnothing</math>

<math>5)\ </math> <math>A \cup U = U</math>; <math>\ A \cap U = A</math>

<math>6)\ </math> <math>A \cup \overline{A} = U</math>; <math>\quad A \cap \overline{A} = \varnothing</math>

<math>7)\ </math> ''Законы де Моргана:'' <math>\overline{A \cup B} = \overline{A} \cap \overline{B}</math>; <math>\quad \overline{A \cap B} = \overline{A} \cup \overline{B}</math>

<math>8)\ </math> ''Идемпотентность:'' <math>A \cup A = A</math>; <math>\quad A \cap A = A</math>

<math>9)\ </math> ''Законы поглощения'' <math>A \cap \left ( A \cup B \right ) = A;</math> <math>\quad A \cup \left ( A \cap B \right ) = A</math>

<math>10)\ </math> ''Инволютивный закон'' <math>\overline{\overline{A}} = A</math>
Доказательства тождеств следуют из определений операций над множествами.
}}

Множества

2021-12-27T13:40:32Z

StudentL: Новая страница: «{{Определение |definition= Множество {{---}} любая совокупность элементов одной природы, мыслима...»

{{Определение
|definition=
Множество {{---}} любая совокупность элементов одной природы, мыслимая как единое целое.
}}
{{Определение
|definition=
Пустое множество {{---}} множество, не содержащее элементов. Обозначается <math>\varnothing</math>.
}}
{{Определение
|definition=
Множества считаются равными, если они состоят из одних и тех же элементов.
}}
{{Определение
|definition=
Два множества называются равномощными, каждому элементу одного множества взаимно-однозначно сопоставляется один и только один элемент другого.
}}
{{Определение
|definition=
Множество, равномощное множеству всех натуральных чисел <math>\N</math>, называют ''счетным множеством''.
}}
{{Определение
|definition=
Мощность множества {{---}} количество элементов множества. Обозначают <math>\vert A \vert</math>. Используется для конечных множеств.
}}

== Подмножества ==
{{Определение
|definition=
Обозначают <math>A \subseteq B</math> и говорят, что множество <math>A</math> является подмножеством множества <math>B</math>, если каждый элемент множества <math>A</math> является элементом множества <math>B</math>.
}}
Если также известно, что <math>A \neq B</math>, говорят, что <math>A</math> является собственным (или
строгим) подмножеством множества <math></math> и пишут <math>A \subset B</math>.
{{Пример
|content=
1) <math>\{ 1,\ 3 \} \subset \{ 3,\ 5,\ 1,\ 4 \}</math> <br />
2) <math>\{ k,\ l,\ j \} \subseteq \{ l,\ j,\ k \} </math>
}}
{{Определение
|definition=
Множество всех подмножеств множества <math>A</math> будем обозначать <math>2^A</math>. Мощность
множества всех подмножеств множества с <math>n</math> элементами равна <math>2^n:\ \vert 2^A \vert = 2^{\vert A \vert}</math>.
}}
{{Пример
|content=
Пусть <math>A = \{ a,\ b,\ c \}</math>. Тогда <math>2^A = \{ \varnothing,\ \{a\},\ \{b\},\ \{c\},\ \{a,\ b\},\ \{a,\ c\},\ \{b,\ c\},\ \{A\} \}</math>.
Видно, что в этом множестве <math>2^{\vert A \vert} = 2^3 = 8</math> элементов.
}}
== Операции над множествами ==
=== Объединение множеств ===
<math>A \cup B = \{ x \mid x \in A\ </math> или <math>\ x \in B \}</math>
=== Пересечение множеств ===
<math>A \cap B = \{ x \mid x \in A\ </math> и <math>\ x \in B \}</math>
=== Дополнение множества ===
<math>\overline{A} = \{ x \mid x \in U\ </math> и <math>\ x \notin A \}</math>, где <math>U</math> {{---}} универсальное множество.
=== Разность множеств ===
<math>A\ \backslash\ B = \{ x \mid x \in A\ </math> и <math>\ x \notin B \}</math>
=== Симметрическая разность множеств ===
<math>A\ \dot - \ B = \left ( A\ \backslash\ B \right ) \cup \left ( B\ \backslash\ A \right )</math>
{{Утверждение
|id=mnoj
|about=Основные тождества алгебры логики
|statement=
Пусть <math>A,\ B,\ C,\</math> произвольные подмножества множества <math>U</math>, тогда выполняются следующие тождества:

<math>1)\ </math> ''Коммутативность:'' <math>\ a)\ </math> <math>A \cup B = B \cup A ;\quad</math> <math>b)\ A \cap B = B \cap A</math>

<math>2)\ </math> ''Ассоциативность:'' <math>\ a)\ A \cup \left ( B \cup C \right ) = \left ( A \cup B \right ) \cup C ; \quad</math> <math>b)\ A \cap \left ( B \cap C \right ) = \left (A \cap B \right ) \cap C </math>;

<math>3)\ </math> <math>a)</math> ''Дистрибутивность'' <math>\cup</math> ''относительно'' <math>\cap: \ </math> <math>A \cup \left ( B \cap C \right ) = \left ( A \cup B \right ) \cap \left ( A \cup C \right )</math>

<math>\quad\ \ b)</math> ''Дистрибутивность'' <math>\cap</math> ''относительно'' <math>\cup: \ </math> <math>A \cap \left ( B \cup C \right ) = \left ( A \cap B \right ) \cup \left ( A \cap C \right )</math>

<math>4)\ </math> <math>A \cup \varnothing = A</math>; <math>\quad A \cap \varnothing = \varnothing</math>

<math>5)\ </math> <math>A \cup U = U</math>; <math>\ A \cap U = A</math>

<math>6)\ </math> <math>A \cup \overline{A} = U</math>; <math>\quad A \cap \overline{A} = \varnothing</math>

<math>7)\ </math> ''Идемпотентность:'' <math>\overline{A \cup B} = \overline{A} \cap \overline{B}</math>; <math>\quad \overline{A \cap B} = \overline{A} \cup \overline{B}</math>

<math>8)\ </math> ''Законы де Моргана:'' <math>A \cup A = A</math>; <math>\quad A \cap A = A</math>

<math>9)\ </math> ''Законы поглощения'' <math>A \cap \left ( A \cup C \right ) = A;</math> <math>\quad A \cup \left ( B \cap C \right ) = A</math>

<math>10)\ </math> ''Инволютивный закон'' <math>\overline{\overline{A}} = A</math>
Доказательства тождеств следуют из определения операций над множествами.
}}

Разложение полинома на множители

2021-12-27T10:32:43Z

StudentL: Новая страница: «{{Теорема |id=pol |statement= В алгебраически замкнутом поле любой полином <math>a_0x^n + a_1x^{n-1} + \dots + a_n <...»

{{Теорема
|id=pol
|statement=
В алгебраически замкнутом поле любой полином <math>a_0x^n + a_1x^{n-1} + \dots + a_n </math>, <math>a_0 \neq 0</math>, <math>n \geqslant 1</math>, имеет разложение на линейные множители вида <math>a_0(x - c_1)(x - c_2) \dots (x - c_n)</math>, и такое разложение единственное.
|proof=
Оба утверждения будут доказаны с помощью метода математической индукции по степени полинома.

''Доказательство возможности разложения''. Полином первой степени <math>a_0x + a_1</math> при <math>a_0 \neq 0</math> в любом поле имеет корень <math>c = - \frac{a_1}{a_0}</math>, и <math> a_0x + a_1 = a_0(x - c) </math>.
Пусть теперь <math>n > 1</math>. В силу алгебраической замкнутости полином <math>f(x)</math> имеет по крайней мере один корень <math>c_1</math> и, следовательно, <math>f(x) = (x - c_1) \cdot f_1(x)</math>, где <math>f_1(x) = a_0x^{n-1} + b_1x^{n - 2} + \dots + b_{n-1}</math> {{---}} полином степени <math>n - 1</math>. В силу индуктивного предположения <math>f_1(x) = a_0(x - c_2) \dots (x - c_n)</math>, откуда <math>f(x) = a_0(x - c_1)(x - c_2) \dots (x - c_n)</math>.

''Доказательство единственности разложения''. При <math>n = 1</math> если <math>a_0x + a_1 = a_0(x - c) = a_0(x - c^\prime)</math>, то <math>a_0(c - c^\prime) = 0</math>, откуда <math>c = c^\prime</math>, т.к. <math>a_0 \neq 0</math>.

Пусть теперь <math>n > 1</math> и есть два разложения <math>f(x) = a_0(x - c_1)(x - c_2) \dots (x - c_n) = a_0(x - c_1^\prime)(x - c_2^\prime) \dots (x - c_n^\prime)</math>. $\\$ Положим <math> x = c_1</math>, получим

<math>f(c_1) = 0 = a_0(c_1 - c_1^\prime)(c_1 - c_2^\prime) \dots (c_1 - c_n^\prime)</math>. Т.к. <math>a_0 \neq 0</math>, то без потери общности можно считать, что <math>c_1 = c_1^\prime</math>

и <math>a_0\boldsymbol{(x - c_1)}(x - c_2) \dots (x - c_n) = a_0\boldsymbol{(x - c_1)}(x - c_2^\prime) \dots (x - c_n^\prime)</math>.

Т.к. кольцо полиномов над полем {{---}} область целостности, то можно сократить обе части равенства на <math>x - c_1</math>, получив <math>a_0(x - c_2)(x - c_3) \dots (x - c_n) = a_0(x - c_2^\prime)(x - c_3^\prime) \dots (x - c_n^\prime)</math>. В силу индуктивного предположения эти разложения совпадают. Следовательно совпадают и исходные разложения <math>f(x)</math>.
}}

Теорема Безу

2021-12-27T08:56:29Z

StudentL: Новая страница: «{{Теорема |statement= Для того, чтобы полином <math>f(x)</math> делился на двучлен <math>x - c</math>, необходи...»

{{Теорема
|statement=
Для того, чтобы полином <math>f(x)</math> делился на двучлен <math>x - c</math>, необходимо и достаточно, чтобы <math>f(c) = 0</math>.
|proof=
''Необходимость''. Пусть <math>f(x)</math> делится на <math>x - c</math>, т.е. <math>f(x) = (x - c) \cdot h(x)</math>. Тогда <math>f(c) = 0</math>.

''Достаточность''. Пусть <math>f(c) = 0</math>, тогда в равенстве <math>f(x) = (x - c) \cdot h(x) + r</math> $\:$ будет $\:$ <math>r = f(c) = 0</math>, т.е. <math>f(x) = (x - c) \cdot h(x)</math>.
}}
{{Следствие
|statement=
Остаток от деления полинома <math>f(x)</math> на двучлен <math>x - c</math> равен <math>f(c)</math>.
}}

== Литература ==
''Фадеев Д. К.'' Лекции по алгебре: Учебное пособие. 4-е изд., стер. — СПб.: Лань, 2005. — 416 с. 58.