И коммуникаций республики узбекистан

15.Структура данных в виде двоичных наборов


Под двоичным набором y = < y1, y2,...,yn> yi E {0, 1} понимается совокупность значений аргументов х1, х2, ..., xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 1.1 передставлены все двоичные наборы длины 3.
Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы х1, х2, ..., xn в порядке возрастания их индексов. Тогда любой двоичный набор y = < y1, y2,...,yn> yi E {0, 1} можно рассматривать как целое двоичное число N:
N=y1*2n-1+y2*2n-2+...+yn
называемое номером набора y. Например, двоичные наборы 101 и 111 имеют номера 5 и 7 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл. 1.2).
Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать 28 = 256 строк. Поэтому для задания функций многих переменных удобно использовать модификацию таблицы истинности.
Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: х1, х2, ..., хj-1 и хj, хj+1, ..., хn. Переменными x1, x2, ..., xn отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными xj, xj+i, ..., xn отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1.


16. Сравнительный анализ алгоритмов поиска
Одним из важных типов задач является поиск. Задача поиска связана с нахождением заданного значения, называемого ключом поиска, среди заданного множества. Существует огромное количество алгоритмов поиска. Их сложность варьируется от самых простых алгоритмов поиска методом последовательного сравнения, до чрезвычайно эффективных, но ограниченных алгоритмов бинарного поиска, а также алгоритмов, основанных на представлении базового множества в иной, более подходящей для выполнения поиска форме. Для решения задачи поиска также не существует единого алгоритма, который бы наилучшим образом подходил для всех случаев. Некоторые из алгоритмов выполняются быстрее остальных, но для их работы требуется дополнительная оперативная память. Другие выполняются очень быстро, но их можно применять только для предварительно отсортированных массивов и так далее. Рассмотрим три алгоритма поиска в отсортированном массиве: двоичный (бинарный поиск), фибоначчиев и интерполяционный поиск. Необходимо отметить, что все три метода подробно описаны и проанализированы в [2]. Бинарный поиск представляет собой эффективный алгоритм для поиска в отсортированном массиве. Он работает путем сравнения искомого ключа K со средним элементом массива А[m]. Если они равны, алгоритм прекращает работу. В противном случае та же операция рекурсивно повторяется для первой половины массива, если K < А[m], и для второй, если K > А[m]. Еще одним примером алгоритма поиска в отсортированном массиве является интерполяционный поиск. Интерполяционный поиск учитывает значение ключа поиска при определении элемента массива, который будет сравниваться с ключом. При выполнении итерации поиска между элементами А[l] (крайним слева) А[r] (крайним справа), алгоритм предполагает, что значения в массиве растут линейно. В соответствии с этим предположением, значение v ключа поиска сравнивается с элементом, индекс которого вычисляется (с округлением) как координата x точки на прямой, проходящей через (l, A[l]) (r, A[r]), координата y которой равна значению v
17.Сравнительный анализ алгоритмов сортировки

Сортировка больших объемов данных отнимает много сил и времени. Алгоритмы сортировки, как упоминалось ранее, позволяют облегчить выполнение этой задачи.

Алгоритмы сортировки позволяют упорядочить заданные списки и массивы данных с помощью операторов сравнения. Эти операторы применяются к элементам массива и определяют их последовательность в структуре данных.
К примеру, символы ниже идут в порядке возрастания согласно кодировке ASCII. В процессе сортировки идет сравнение элементов между собой. Чем выше значение символа в таблице ASCII, тем дальше от начала списка он будет расположен.