Для выполнения работы необходимо:
8. Повторить правила техники безопасности при работе с вычислительной техникой.
9. Изучить часть раздела «Кодирование сообщений» лекционного курса «Теоретические основы информационных процессов», посвященную помехоустойчивому кодированию, а также теоретическую часть лабораторной работы 2 в настоящих методических указаниях.
10. Получить у преподавателя вариант задания (образцы заданий приведены в приложении).
11. В соответствии с заданием разработать алгоритм предложенного метода помехоустойчивого кодирования и написать программу на языке высокого уровня, реализующую разработанный алгоритм.
12. Ввести программу в ЭВМ, отладить и результаты выполнения на конкретных примерах показать преподавателю.
13. В соответствии с требованиями раздела 6 оформить отчет по работе.
14. Защитить лабораторную работу, продемонстрировав знание методов помехоустойчивого кодирования и умение решать аналогичные задачи.
5. Контрольные вопросы
1. Что такое помехоустойчивое кодирование?
2. Какие методы помехоустойчивого кодирования Вы знаете?
3. Как реализуется на практике метод контроля четности?
4. Какие возможности предоставляет метод контрольных сумм?
5. Что такое кодовое расстояние?
6. Как определяется способность кодов обнаруживать ошибки?
7. Как определяется способность кодов исправлять обнаруженные ошибки?
Содержание и оформление отчета
Отчет должен содержать:
● титульный лист, название и цель работы;
● вариант задания;
● листинг программного кода;
● выводы по работе.
ЛАБОРАТОРНАЯ РАБОТА 3.
ПОИСК ДАННЫХ НА ОСНОВЕ СРАВНЕНИЯ КЛЮЧЕЙ
|
|
Цель работы
Целью работы является изучение прикладных методов поиска данных в памяти ЭВМ, основанных на сравнении ключей, и оценка их быстродействия.
Задачи
Задачами лабораторной работы являются задачи овладения навыками программной реализации указанных методов поиска на языке высокого уровня и применения разработанных программ для поиска конкретных данных в памяти ЭВМ.
Теоретическая часть
Поиск на основе сравнения ключей. Идея методов поиска данного вида состоит в просмотре некоторой таблицы записей с целью отыскания той из них, ключ которой совпадает с задаваемым извне значением аргумента поиска. В простейших методах такого поиска порядок считывания записей и сравнения их ключей с аргументом определен заранее (последовательный поиск). Более сложные методы осуществляют считывание записей по результатам сравнения с аргументом ключей предыдущих считанных записей.
Последовательный поиск. На каждом шаге считывается следующая запись таблицы и ее ключ сравнивается с аргументом поиска. Шаги начинаются с первой записи таблицы и повторяются до тех пор, пока либо ключ очередной считанной записи не совпадет с аргументом поиска, либо не будет считана последняя запись таблицы. В первом случае поиск оканчивается удачно, во втором - неудачно.
Блочный поиск. Т аблица упорядочивается по возрастанию значений ключей и записи группируются в виртуальные блоки. Для повышения быстродействия поиска каждый блок должен содержать одинаковое количество записей, наиболее близкое к квадратному корню из числа записей в таблице. На каждом шаге считывается первая запись каждого блока и ее ключ сравнивается с аргументом поиска. Шаги повторяются, начиная с первой записи таблицы, до тех пор, пока не будет выполнено одно из трех условий:
|
|
1) ключ записи совпадает с аргументом поиска - в этом случае поиск завершается удачно;
2) обнаружена запись с ключом, превышающим аргумент поиска -
в этом случае начинается последовательный просмотр записей предыдущего блока и сравнение их ключей с аргументом поиска до тех пор, пока либо не будет обнаружена искомая запись (удачный поиск),
либо блок не будет просмотрен полностью (поиск неудачен);
3) достигнут конец таблицы - в этом случае поиск завершается неудачно.
Двоичный поиск. Таблица упорядочивается по возрастанию ключей. На каждом шаге считывается и сравнивается с аргументом запись, находящаяся в середине некоторого множества последовательно расположенных записей таблицы. В качестве исходного множества таких записей выбирается вся таблица и шаги повторяются до тех пор, пока либо аргумент поиска не совпадет с ключом сравниваемой записи (поиск удачен), либо множество не станет пустым (неудачный поиск). В качестве обрабатываемого множества для следующего шага берется левое подмножество текущего шага, если аргумент поиска меньше значения ключа сравниваемой записи, или же правое подмножество, если аргумент больше ключа.
Поиск по бинарному дереву. В каждой записи таблицы помимо поля ключа «К» и атрибутов предусматривается два поля указателей «П» и «Л», в которых записываются адреса правого и левого преемников вершины дерева, соответствующей данной записи (для свободных вершин, не имеющих преемников, здесь помещается NULL). Для любой вершины значение ключа соответствующей записи больше значения ключа ее левого преемника и меньше значения ключа правого преемника. Чтобы иметь возможность начать поиск, требуется адрес записи, соответствующей корню дерева, который хранится в специальной ячейке. Чтобы найти вершину для присоединения новой записи, достаточно проследить в дереве путь неудачного поиска для аргумента, равного ключу добавляемой записи.
|
|
На каждом шаге поиска считывается и сравнивается с аргументом «А» запись с ключом «К» и указателями «Л» и «П». При этом первый шаг всегда начинается с корня дерева. По результатам сравнения принимаются следующие решения:
а) А=К - запись найдена, поиск заканчивается удачно;
б) А>К, П=NULL или А<К, Л=NULL - поиск заканчивается неудачно;
в) А>К, П не равен NULL - поиск продолжается, считывается очередная запись по указателю П;
г) А<К, П не равен NULL - поиск продолжается, считывается очередная запись по указателю Л.
г) А<К, П не равен NULL - поиск продолжается, считывается очередная запись по указателю Л.
Чистый бинарный поиск. Имеется таблица из N записей, упорядоченных по возрастанию значений ключей. Каждая запись имеет известную вероятность выбора р и выполняется условие нормировки (сумма всех р равна 1).
Поиск осуществляется следующим образом: на каждом шаге считывается и сравнивается с аргументом поиска запись, разбивающая
некоторое множество последовательно расположенных записей таблицы на два подмножества с примерно одинаковой суммарной вероятностью. В качестве исходного множества выбирается вся таблица и шаги повторяются до тех пор, пока либо аргумент поиска не совпадет с ключом сравниваемой записи (поиск удачен), либо множество не станет пустым (неудачный поиск). В качестве обрабатываемого множества для следующего шага берется левое подмножество текущего шага, если аргумент поиска меньше значения ключа сравниваемой записи, или же правое подмножество, если аргумент больше ключа.