Основные законы алгебры логики

22..Булевой функцией называется функция(x₁, x₂, x₃..xn) аргумент которой x₁, x₂, x₃...-независимая переменная и сама функция принимают значения 0 и 1 булева функция (0, 1)ⁿ→ (0, 1) Каноническая форма - формула, построенная по определенному правилу. Нахождение канонических форм: ДНФ(Дизъюнктивная нормальная форма)- логическая сумма элементарных логических произведений, в каждое из которых аргумент или его отрицание входит не более 1 раза. F(A, B, C)=A + C+Ā C …Если элементарное произведение содержит все переменные или их отрицания – Минтерм, а если сумма минтермов СДНФ(совершенная дизъюнктивная форма). КНФ(конъюнктивная нормальная форма)- логическое произведение элементарных логических сумм, в каждое из которых аргумент или его отрицание входит не более 1 раза. если такая сумма содержит все переменные или

их отрицания – Макстерм, а произведение макстермов- СКНФ(совершенная конъюнктивная нормальная форма).

23.Сущность и свойства алгоритм ов это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами для получения искомого результата. Сущность алгоритма заключается в том что если алгоритм разработан то его можно вручить для выполнения любому исполнителю незнакомому с решением задачи и точно следуя правлам алгоритма исполнитель получит его решение.При разработке алгоритма необходимо формулировать процесс решения задачи сводя его к применению конечной последовательности достаточно простых правил. Свойства: дискретность, понятность, определенность, массовость, результативность.сходимость, эффективность, наличие однородной дискретной конечной или бесконечной памяти, точность, устойчивость. Сложность алгоритма количество элементарных действий в вычислительном процессе данного алгоритма как функция от исходных данных. Время сложности алгоритма= это время Т необходимое для его выполнения в зависимости от исходных данных.ЭТО Т=kt.

24.Формы записи алгоритмов На практике наиболее распространены следующие формы представления алгоритмов: словесная; графическая; псевдокоды. программная. 1. Словесный способ записи алгоритма.Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. 2Наибольшее распространение благодаря своей наглядности получил графический способ записи алгоритмов. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.

3. Псевдокод. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.

Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст.

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

25. Алгоритмы организации сортировки. Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

1.Сортировка простыми вставками. Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. 2. Обменная сортировка (методом “пузырька”). Если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены. 3.Сортировка посредством простого выбора “линейная сортировка”. Сначала выделяется наименьший (или, может быть, наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся и т.д. Шаги алгоритма: 1)Найти номер минимального значения в текущем списке2)Произвести обмен этого значения со значением первой неотсортированной позиции3)Сортировка хвоста списка, исключив уже отсортированные элементы.