Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Discrete
pads
| Term | Definition |
|---|---|
| 1)Размещения с повторениями | Комбинаторный объект(КО), все возможные упор выборки из n элементов(могут повторяться несколько раз) A(n,k) – n-колво элементов,k-размер выборки |
| 2) Размещения бп | КО, все возможные упор выборки из n элементов(встречаются 1 раз) A(n,k) – n-колво элементов,k-размер выборки |
| 3) Перестановки | КО, возможные способы перстановки n элементов в упорядоченную последовательность. P(n) n-колво эл-в |
| 4) Сочетания бп | КО, возможные неупорядоченные выборки из n эл-в, встречаются 1 раз C(n,k) – n-колво эл-в,k-размер выборки |
| C(n,k) = C(n,n-k) | сочетания бп (бп) симметричны по k |
| C(n,k) = C(n-1,k) + C(n-1,k-1) | для сочетаний бп |
| Сумма всех сочетаний из n элементов равна | 2^n |
| Сумма квадратов сочетаний из n элементов равна | C(2n,n) |
| C(n,0)+C(n,1)+...+C(n,n) = 2^n | формула бинома |
| 6) Формула включений и исключений | К метод подсчёт а размера объединения или пересечения нескольких множеств(размеры и их пересечения) |A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Ai| - Σ|Ai ∩ Aj| + Σ|Ai ∩ Aj ∩ Ak| - ... + (-1)^(n-1)|A₁ ∩ A₂ ∩ ... ∩ Aₙ|, где |A| обозначает размер множества A. |
| |A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Ai| - Σ|Ai ∩ Aj| + Σ|Ai ∩ Aj ∩ Ak| - ... + (-1)^(n-1)|A₁ ∩ A₂ ∩ ... ∩ Aₙ|, где |A| обозначает размер множества A. | 6) Формула включений и исключений |
| Числа Стирлинга 1-го рода s(n,k) колво перестановок n эл-в с k циклами | s(n+1,k) = ns(n,k) + s(n,k-1), где s(n,0) = 0 и s(n,n) = 1 |
| s(n+1,k) = ns(n,k) + s(n,k-1) | Числа Стирлинга 1-го рода s(n,k) колво перестановок n эл-в с k циклами, где s(n,0) = 0 и s(n,n) = 1 |
| Числа Стирлинга 2-го рода S(n,k) колво способов разбиения множества n эл-в на k непустых непересекающихся подмножеств | S(n+1,k) = kS(n,k) + S(n,k-1), где S(n,0) = 0 и S(n,n) = 1. |
| Посл-ть чисел, каждое число сумма предыдущих 2 чисел | 8) Числа Фибоначчи |
| Числа Каталана | Последовательность чисел – количество правильных скобочных последовательностей длины n |
| 9) Производящие функции | Инструмент анализа КО и проведения комбинаторных расчётов. Степенные ряды, коэффициенты в которых соответствуют количеству объектов определенного типа |
| 10) Разбиения чисел | это способ представления целого числа в виде суммы положительных целых чисел. |
| Диаграммы Ферре | это графическое представление разбиения числа, которое состоит из точек на координатной плоскости. |
| 11) Действия над множествами | это операции, которые выполняются с множествами. Основными действиями над множествами являются объединение, пересечение, разность и дополнение. |
| это множество, которое содержит все элементы из A и B. Обозначается как A ∪ B. | Объединение двух множеств A и B |
| это множество, которое содержит только те элементы, которые принадлежат как множеству A, так и множеству B. Обозначается как A ∩ B. | Пересечение двух множеств A и B |
| это множество, которое содержит только те элементы, которые принадлежат A, но не принадлежат B. Обозначается как A \ B. | Разность множеств A и B |
| это множество всех элементов, которые не принадлежат множеству A. Обозначается как A' | Дополнение множества A |
| 12) Табличный способ задания булевых переменных | основан на создании таблицы истинности, в которой перечисляются все возможные значения переменных и соответствующие им значения логической функции |
| Векторный способ задания булевых переменных | основан на использовании битовых векторов. Каждая позиция в векторе соответствует одной из переменных, а значение на данной позиции соответствует значению этой переменной. |
| A B F(A,B) 0 0 0 0 1 1 1 0 1 1 1 0 | 12) Табличный способ задания булевых переменных |
| A = [0 0 1 1] B = [0 1 0 1] | Векторный способ задания булевых переменных |
| это переменная, значение которой влияет на значение логической функции | 13) Существенная переменная |
| Фиктивная переменная | это переменная, значение которой не влияет на значение логической функции |
| 14) Принцип двойственности | утверждает, что любую логическую функцию можно заменить её двойственной функцией, полученной заменой всех операций И на операции ИЛИ и наоборот, а также инверсией значений переменных. |
| 14) Принцип двойственности | F(A,B) = A И (B ИЛИ C) её двойственной будет F'(A,B) = (A ИЛИ (B И C')). |
| Конъюнкция | логическое "И" |
| отрицание | (логическое "НЕ").. |
| дизъюнкция | логическое "ИЛИ" |
| 16) Законы де Моргана | это два закона логики, утверждающие, что отрицание конъюнкции или дизъюнкции двух выражений эквивалентно дизъюнкции или конъюнкции отрицаний этих выражений соответственно. |
| 17) СДНФ | (совершенная дизъюнктивная нормальная форма) СДНФ записывается как дизъюнкция всех комбинаций литералов, принимающих значение "1", в таблице истинности функции. |
| СКНФ | (совершенная конъюнктивная нормальная форма)записывается как конъюнкция всех комбинаций литералов, принимающих значение "0", в таблице истинности функции. |
| 18) Полиномы Жегалкина | это алгебраические выражения, которые используются для описания логических функций в терминах переменных и операций И (конъюнкция) и ИЛИ (дизъюнкция). Каждому логическому выражению соответствует единственный полином Жегалкина. |
| Нахождение полинома Жегалкина | таблица истинности, наборы знач 1, составляем произведение переменных, если 1 без отрицания, 0 с отрицанием, сложить |
| 19) Замыкание | это понятие, используемое в теории множеств и математической логике. Замыкание множества A - это наименьшее замкнутое множество, которое содержит A. Множество называется замкнутым, если его дополнение является открытым множеством |
| Свойства замыкания: | Замыкание множества всегда существует и единственно. ● Множество является замкнутым тогда и только тогда, когда оно содержит все свои предельные точки. |
| 20) Основные замкнутые классы двузначной логики | Основные замкнутые классы двузначной логики включают: 1. Класс функций, сохраняющих 0 (НКА) 2. Класс функций, сохраняющих 1 (НКД) Класс функций, самодвойственных (СД) Класс функций, линейных (Л) Класс функций, монотонных (М) |
| Класс функций, сохраняющих 0 (НКА) | функции, которые принимают значение 0 на всех наборах аргументов, на которых принимает значение 0 хотя бы один из аргументов. |
| Класс функций, сохраняющих 1 (НКД) | функции, которые принимают значение 1 на всех наборах аргументов, на которых принимает значение 1 хотя бы один из аргументов. |
| Класс функций, самодвойственных (СД) | - функции, которые равны своему дуальному (то есть замене 0 на 1 и наоборот). |
| Класс функций, самодвойственных (СД) | - функции, которые равны своему дуальному (то есть замене 0 на 1 и наоборот). |
| Класс функций, монотонных (М) | - функции, для которых увеличение любого аргумента не приводит к уменьшению значения. |
| 21) Полнота системы функций | это свойство системы логических функций, при котором любая другая логическая функция может быть выражена в виде комбинации (линейной или нелинейной) базовых функций этой системы. |
| Теорема о полноте | Теорема о полноте системы функций утверждает, что система логических функций является полной тогда и только тогда, когда с её помощью можно выразить любую другую логическую функцию |
| Первое направление доказательства | Если система функций полна, то любую другую логическую функцию можно выразить через элементарные функции этой системы. Следовательно, система функций является достаточно мощной, чтобы позволить выражать любые логические функции. |
| Второе направление доказательства | Если система функций не является полной, то найдётся логическая функция, которую нельзя выразить через элементарные функции этой системы. Однако, если мы добавим новую функцию в эту систему, то система станет полной |
| 22) Теорема Поста | - это теорема, для любой логических операций не включает в себя отрицание (NOT), полная тогда и только тогда, когда выполнено хотя бы одно из двух условий:в этой системе реализуется связка Шеффера (NAND);в этой системе реализуется связка Пирса (NOR) |
| Доказательство необходимости данной теоремы Теорема Поста | . Таким образом, каждая полная система логических операций должна содержать в себе либо связку Шеффера, либо связку Пирса. |
| 23) Критериальная таблица | это таблица, используемая для определения истинности сложных логических выражений в двузначной логике (булевой алгебре). |
| 24) Минимизация СДНФ (Совершенной Дизъюнктивной Нормальной Формы) и СКНФ (Совершенной Конъюнктивной Нормальной Формы) | это процесс упрощения булевых функций, который позволяет представить функцию в виде наименьшего числа конъюнкций или дизъюнкций соответственно. |
| Для минимизации функций используются карты Карно | это графический метод, который позволяет наглядно представить значения функции для всех возможных комбинаций аргументов. |
| 25) В к-значной логике | В к-значной логике, где k>2, логические переменные могут принимать не только два возможных значения (истина или ложь), но и большее число значений. |
| Основные функции в к-значной логике | логике зависят от значения k и могут быть различными для разных систем. В двоичной логике основными функциями являются конъюнкция (AND), дизъюнкция (OR) и отрицание (NOT). В троичной логике добавляется функция импликации (IMPL) и эквивалентности (EQV). |
| 27) Три основные формы в к-значной логике | это дизъюнктивная нормальная форма (ДНФ), конъюнктивная нормальная форма (КНФ) и полиномиальная форма. |
| ДНФ | ДНФ представляет функцию в виде суммы произведений литералов или их отрицаний |
| КНФ | представляет функцию в виде произведения сумм литералов или их отрицаний. |
| Полиномиальная форма | представляет функцию в виде полинома, где каждый член соответствует одной строке таблицы истинности. |
| 28) В к-значной логике для представления булевых функций используются полиномы | Полином в к-значной логике - это выражение, состоящее из литералов и их отрицаний, где каждый литерал может принимать k различных значений. |
| Теорема о представлении полиномами | что любая булева функция может быть представлена в виде полинома. Для этого нужно составить таблицу истинности функции, затем записать каждую строку таблицы как множитель полинома и сложить все полученные произведения. |
| 29) Теорема Пикара | Теорема Пикара утверждает, что любая булева функция может быть представлена в виде ДНФ, содержащей не более 2^n элементарных конъюнкций (где n - количество переменных функции). |
| 29) Теорема Пикара | на классы эквивалентности каждый класс состоит из строк таблицы ист функция принимает одно и то же значение. кон строятся для эквивалентности,объединяются в ДНФ. Таким образом, полученная ДНФ будет содержать не более 2^n элементарных конъюнкций. |
| 30) Критерий Яблонского | утверждает, что система функций полна, если и только если для каждой переменной существует функция, которая не зависит от этой переменной, но различна от константы. |
| 31) Критерий Слупецкого | Система функций полна тогда и только тогда, когда любая функция может быть представлена в виде композиции функций данной системы. |
| Композиция функций | это последовательное применение одной функции к результату другой функции. |
| 32) Критерий Саломаа | Система функций полна тогда и только тогда, когда лежащая в ее основе множества строк таблицы истинности образуют свободный моноид, т.е. не содержат неправильных слов которые могут быть получены из других слов путем удаления или добавления символов. |
| 33) Шефферовы функции | Эти функции называются штрих Шеффера (NAND) и стрелка Пирса (NOR). Штрих Шеффера равен отрицанию конъюнкции: x NAND y = NOT(x AND y), а стрелка Пирса равна отрицанию дизъюнкции: x NOR y = NOT(x OR y).(любая другая функция) |
| 34) Теорема Янова | устанавливает, что любая функция k-значной логики может быть представлена в виде композиции k+1 функции Шеффера..состоящая из функций Шеффера и констант, полна |
| 35) Теорема Мучника (или Малцева) | устанавливает, что система функций полна тогда и только тогда, когда в ней содержится хотя бы одна функция, которая не принадлежит к множеству основных (базисных) функций. |
| Базис замкнутого класса | это минимальное множество функций, которое достаточно для построения всех функций данного замкнутого класса с помощью их композиции и возможного применения отрицания |
| В к-значной логике количество замкнутых классов | равно k^k^2, где первая степень определяет число переменных, а вторая степень - количество возможных булевых функций на k значениях. |
| Примеры полных систем в к-значной логике: | Система функций Шеффера (NAND) или стрелка Пирса (NOR). (AND), (OR) (NOT). (AND) и отрицания (NOT). импликации (IMPL) и отрицания (NOT). Важно отметить, что любая полная система функций может быть использована как базис замкнутого класса. |
| В к-значной логике существенными | называются те функции, которые не могут быть упрощены до константы путем замены одного или нескольких аргументов. Таким образом, существенные функции являются основой для построения минимальных СДНФ и СКНФ. |
| 40) Граф | это математический объект, представляющий собой множество вершин (узлов) и множество ребер (связей) между этими вершинами. |
| Мультиграфы | это графы, в которых возможны несколько ребер между одной и той же парой вершин. |
| Псевдографы | это графы, в которых возможны петли (ребра, соединяющие вершину саму с собой). |
| Степень вершины | это количество ребер, связанных с данной вершиной. Для ориентированных графов различают входящую и исходящую степень вершины. |
| Матрица инцидентности | это матрица, которая описывает связь между вершинами и ребрами графа. В матрице инцидентности i-я строка соответствует i-й вершине, а j-й столбец соответствует j-му ребру. (i,j) равно 1, если i-я вершина связана с j-м ребром, и -1в обратную сторону |
| Матрица смежности | это квадратная матрица, которая описывает связь между всеми парами вершин графа. |
| 43) Часть графа | это множество вершин и ребер, которые соединяют только эти вершины. |
| Суграф | это часть графа, которая может содержать все или лишь некоторую часть его вершин и ребер.. |
| Подграф | это суграф, который получен удалением одной или нескольких вершин графа |
| Изоморфизм графов | это отображение вершин одного графа на вершины другого графа таким образом, чтобы сохранить связи между ними. То есть два графа изоморфны, если один может быть получен из другого путем переименования вершин. |
| Гомеоморфизм графов | это более слабое условие, чем изоморфизм. Два графа считаются гомеоморфными, если один может быть получен из другого путем удаления и добавления вершин и ребер, причем сохраняются связи между вершинами. |
| Маршрут в графе | это последовательность ребер, которые соединяют вершины графа. Маршрут может проходить через одну и ту же вершину или ребро несколько раз. |
| Цепь в графе | это маршрут, в котором все ребра являются различными. |
| Цикл | это маршрут, который начинается и заканчивается в одной и той же вершине и содержит хотя бы одно ребро. Если цикл не содержит повторяющихся вершин или ребер, то он называется простым. |
| Связность графа | это свойство графа, которое означает, что любые две вершины графа можно соединить маршрутом. . Если граф связен, то он состоит из одной компоненты связности. Если же граф не связен, то он состоит из нескольких компонент связности. |
| Компонента связности | - это максимальный по мощности связный подграф графа. Другими словами, если мы удалим из графа одну вершину, которая не является мостом (то есть после ее удаления компонент связности не увеличится), то полученный граф также будет связным. |
| Матрица связности | это квадратная матрица, используемая для описания связности в неориентированных графах. Она содержит информацию о том, какие вершины связаны между собой ребрами |
| Диаметр графа | это наибольшее расстояние между любыми двумя вершинами в графе. Другими словами, это самое длинное кратчайшее расстояние между вершинами. Диаметр графа позволяет оценить его "размер" или "широту". |
| Эксцентриситет вершины | определяется как наибольшее расстояние между этой вершиной и любой другой вершиной в графе. Эксцентриситет показывает, насколько далеко от центра находится данная вершина. |
| дерево | это связный ациклический граф, то есть граф, не содержащий циклов, но при этом любые две вершины в нём соединены ровно одним путём. |
| Эйлерова цепь | - это путь, который проходит через каждое ребро графа ровно один раз |
| Эйлеров цикл | это эйлерова цепь, которая является циклической, то есть начинается и заканчивается в одной и той же вершине |
| Некоторые свойства эйлеровых цепей и циклов: | Связный неориентированный граф содержит эйлеров цикл тогда и только тогда, когда степень каждой его вершины четна. Это называется необходимы |
| Гамильтонова цепь в графе | это простой путь, который проходит через каждую вершину графа ровно один раз. |
| Гамильтонов цикл | это гамильтонова цепь, которая является циклической, то есть начинается и заканчивается в одной и той же вершине. |
| Разрезающее множество (cut set | это множество ребер, удаление которых делает граф несвязным. |
| Разрез (cut) в графе | это множество ребер, удаление которых разделяет граф на две непересекающиеся компоненты связности. |
| Связность в графе относится к степени, с которой вершины графа связаны друг с другом. | Граф называется связным, если между любыми двумя его вершинами существует путь. |
| Несвязный граф | это граф, состоящий из двух или более компонент связности, которые не связаны между собой |
| Компонента связности | это максимальное подмножество вершин графа, в котором любые две вершины связаны путем, а с остальными вершинами графа они не связаны |
| Сильно связный граф | это ориентированный граф, в котором между любыми двумя вершинами существует ориентированный путь |
| Слабо связный граф | это неориентированный граф, получаемый из ориентированного графа путем удаления ориентации ребер |
| 53) Паросочетания | это понятие из теории графов, которое связано с разбиением вершин графа на пары таким образом, чтобы каждая вершина принадлежала ровно одной паре |
| 54) Реберная раскраска графа и хроматический индекс | это также понятия из теории графов, связанные с раскраской ребер графа |
| Хроматический индекс графа | это минимальное количество цветов, необходимое для правильной реберной раскраски графа |
| Реберная раскраска графа заключается в | присвоении цветов различным ребрам таким образом, чтобы никакие два смежных ребра не имели одинакового цвета |
| 55) Вершинная раскраска и теорема о пяти красках | это понятия, связанные с раскраской вершин графа |
| Теорема о пяти красках утверждает, что любой плоский граф | (граф, который можно изобразить на плоскости без пересечения ребер) может быть правильно раскрашен вершинами с использованием не более пяти цветов. Эта теорема была доказана в 1976 году и является одной из важных теорем в теории графов. |
| Ранг графа | это число линейно независимых ребер в графе. В графе, состоящем из N вершин, ранг может быть любым целым числом от 0 до N-1. |
| Цикломатическое число | это число, которое определяет сложность программы или алгоритма. Оно вычисляется на основе количества путей и узлов в графе потока управления программы. |
| 57) Понятие алфавитного кодирования | это процесс присвоения уникальных кодов (часто представленных в виде последовательности битов) символам или элементам алфавита |
| Алфавитное кодирование используется для представления текста, чисел, знаков пунктуации и других символов в компьютерной обработке информации. | Примером алфавитного кодирования является таблица ASCII, где каждому символу сопоставлен уникальный числовой код. |
| 58) Префиксные схемы кодирования | это способ алфавитного кодирования, в котором ни один код не является префиксом другого кода |
| 59) Теорема об алфавитном кодировании с помощью графа | это теорема, которая устанавливает связь между алфавитным кодированием и графами |
| Неравенство Макмиллана | это неравенство, которое устанавливает границу для средней длины кодового слова в алфавитном кодировании. Оно гласит, что для любого префиксного кодирования с алфавитом размерности N и средней длиной L, справедливо неравенство: L ≥ H, |
| Самокорректирующиеся коды | это специальные коды, которые содержат достаточное количество дополнительной информации для обнаружения и исправления ошибок, возникающих при передаче данных или хранении информации |
| код Хэмминга | Длина кодового слова и количество добавляемых проверочных битов определяются формулой 2^r >= n + r + 1, где n - количество исходных битов данных, а r - количество проверочных битов. |
| Теорема об обнаружении ошибок и исправлении ошибок при декодировании | относится к самокорректирующимся кодам. Она устанавливает возможность обнаружения и исправления ошибок при передаче данных или хранении информации с использованием определенных типов кодов. |
| Теорема Хэмминга гласит | "Для каждого положительного целого числа r существует блочный код длины n = 2^r - 1 с r проверочными битами, который позволяет обнаруживать все одиночные ошибки и исправлять все одиночные ошибки при декодировании". |
| Хэмминг - блочный код | n = 2^r - 1 |
| n = 2^r - 1 | Хэмминг |
| A(n,k) | 2) Размещения бп |
| P(n) | 3) Перестановки |
| C(n,k) = C(n,n-k) | сочетания бп (бп) симметричны по k. |
| C(n,k) = C(n-1,k) + C(n-1,k-1) | для сочетаний бп |
| C(n,k) = C(n-1,k) * (n-k+1)/k | альтернативная форма сочетаний бп |
| 2^n | Сумма всех сочетаний из n элементов равна |
| C(2n,n) | Сумма квадратов сочетаний из n элементов равна |
| C(n,0)+C(n,1)+...+C(n,n) = 2^n | формула бинома |
| |A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Ai| - Σ|Ai ∩ Aj| + Σ|Ai ∩ Aj ∩ Ak| - ... + (-1)^(n-1)|A₁ ∩ A₂ ∩ ... ∩ Aₙ| | 6) Формула включений и исключений |
| s(n+1,k) = ns(n,k) + s(n,k-1) | Числа Стирлинга 1-го рода |
| S(n+1,k) = kS(n,k) + S(n,k-1) | Числа Стирлинга 2-го рода |
| NAND y = 2 - max(x, y) | Штрих Шеффера |
| x NOR y = min(2 - x - y, 1) | Стрелка Пирса |
| k^k^2 | количество замкнутых классов |
Created by:
Xn
Popular Math sets