Файл: Структуры лабы.doc

Цель работы: Изучение алгоритмов метода поиска с возвратами на примерах реализации шахматных задач и задачи динамического программирования. Освоение "жадных" алгоритмов- точного и приближенного.

Домашнее задание:

1 Изучить алгоритм метода поиска с возвратами.

2 Изучить алгоритм нахождения критического пути в задаче динамического программирования.

3 Освоить принципы построения "жадных" алгоритмов.

Порядок выполнения работы.

Открыть проект Delphi Structures.
Добавить в управляющее главное меню пункт «Лабораторная работа №7», при выборе которого должно появляться окно модуля «Poisk_with_back» (модуль Poisk_with_back» с формой добавить в проект).
Установить на форму модуля Poisk_with_back компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №2.1.
В обработчике события onClick управляющей кнопки на языке
Object Pascal написать фрагмент программы для реализации алгоритма в соответствии с вариантом.
Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.
произвести анализ запрограммированного алгоритма (по количеству сравнений ).
Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.

Таблица 7.1

№ вар.	Текст задачи
1.	Написать и отладить программу, реализующую решение задачи о "безопасном" размещении к ферзей (к<=8) на шахматной доске. Найти одно решение и отобразить его графически на форме приложения. Для нахождения " безопасного " размещения ферзей использовать метод поиска с возвратами.
2.	Написать и отладить программу, реализующую решение задачи о "безопасном" размещении 8 ферзей на шахматной доске. Найти все возможные решения и отобразить первое решение графически на форме приложения. Все найденные решения сохранить в файле. Для нахождения " безопасного " размещения ферзей использовать метод поиска с возвратами.
3.	Используя перечень номиналов ассигнаций: Const Nominal: array[0..5] of currency= (5000, 1000, 500, 100, 50, 10); , запрограммировать "жадный" алгоритм формирования выдачи заданной суммы в банкомате. Организовать сервис- диалог с заказчиком суммы и учесть в программе возможность отсутствия ассигнаций того или иного номинала.
4.	Используя перечень номиналов ассигнаций и монет: Const Nominal: array[0..10] of currency= (5000, 1000, 500, 100, 50, 10, 5, 1, 0.5, 0.1); , запрограммировать "жадный" алгоритм формирования заданной сдачи кассиром. Общее число купюр и монет в сдаче должно получиться минимальным. Организовать сервис- диалог с кассиром для выяснения обстоятельств наличия номиналов в кассе и учесть в программе возможность отсутствия ассигнаций того или иного номинала.
5.	Используя метод "жадных" алгоритмов, реализовать решение задачи "о рюкзаке ограниченного объема" , если заданы величины: V--ограничение объема рюкзака, N-- количество предметов заданного объема q[i] и стоимости c[i]. Программа должна выбрать подмножество предметов, вмещающихся в рюкзак и имеющих наибольшую общую стоимость.
6.	Пусть имеется решетка для описания последовательности работ: узлы в решетке пронумерованы формально: Рис.1 Длительность каждой работы указана возле направленной дуги. Написать и отладить программу нахождения времени окончания строительства, если решетка моделирует график работы и длительность (вес дуг).
7.	Написать и отладить программу нахождения критического пути для заданной модели-решетки (Рис.1).

Контрольные вопросы

1. Суть алгоритма метода поиска с возвратами.(МПВ).

2. Что такое 'тупик' в МПВ и как выйти из тупиковой ситуации в этом алгоритме?

3. Почему стек является непременным аксессуаром в алгоритме МПВ?

4. Сформулируйте задачу динамического программирования.

5. Опишите модель задачи динамического программирования.

6. Дайте понятие критического пути.

7. Что такое топологический порядок выбора узлов?

8. Каков механизм нахождения критического пути, если найдено время окончания работ(строительства)?

Лабораторная работа № 8 Хеширование. Алгоритмы организации и обработки хеш-таблиц.

(4 часа)

Цель работы: Освоить на практике алгоритмы организации хеш-таблиц с открытой адресацией и хеш-таблиц с разрешением коллизий методом цепочек .

Домашнее задание:

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

Порядок выполнения работы.

Открыть проект Delphi Structures.
Добавить в управляющее главное меню пункт «Лабораторная работа №8», при выборе которого должно появляться окно модуля «Hesh» (модуль «Hesh» с формой добавить в проект).
Установить на форму модуля Hesh компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №8.1.
В обработчике события onClick управляющей кнопки на языке Object Pascal написать фрагмент программы для реализации алгоритма хеширования заданного ключа и дальнейшего поиска ключа в хеш-таблице в соответствии с вариантом задания.
Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.
произвести анализ запрограммированного алгоритма (по количеству сравнений).
Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.

Таблица 8.1

№ вар.	Текст задачи
1.	Организовать хеш-таблицу с открытой адресацией, используя хеш-функцию h(k)=trunc(MFrac(kd)), где d=(sqrt(5)-1)/2, M - размер хеш-таблицы. Организовать процедуру поиска по ключу в этой хеш-таблице. Результат поиска - номер ячейки с найденным ключом или (-1).
2.	Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования хеш-адреса использовать хеш-функцию универсального хеширования и процедуру линейного исследования для разрешения коллизии.
3.	Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования начального хеш-адреса использовать метод деления, а затем при возникновении коллизии процедуру квадратичного исследования.
4.	Построить хеш-таблицу с открытой адресацией, используя двойное хеширование, как способ открытой адресации. Хеш-функция h₁(k) и h₂(k) организовать методом деления. Формирование таблицы - с помощью процедуры поиска и вставки по ключу.
5.	Организовать хеш-таблицу, используя хеш-функцию h(k) по методу умножения для формирования хеш-адреса. разрешение коллизий - методом внешних цепочек. а) Написать процедуру поиска и вставки по ключу. б) Написать процедуру удаления ключа.
6.	Организовать хеш-таблицу с помощью идеального хеширования - двухуровневая схема с универсальным хешированием на каждом уровне. Запрограммировать процедуру поиска и вставки по ключу.
7.	Организовать программно хеширование 100 записей в таблицу. состоящую из 20 ссылок на линейные списки (стеки), первоначально пустые. записи имеют неотрицательные целые ключи k<50, формируемые случайным образом. Хеш-функцию организовать методом умножения в отдельной Function.
8.	Организовать программно хеширование 50 записей в таблицу. состоящую из 10 ссылок на линейные списки (очереди), первоначально пустые. записи имеют неотрицательные целые ключи k<30, формируемые случайным образом. Хеш-функцию организовать методом деления в отдельной Function

№ вар.

Текст задачи

Организовать хеш-таблицу с открытой адресацией, используя хеш-функцию h(k)=trunc(M*Frac(k*d)), где d=(sqrt(5)-1)/2, M - размер хеш-таблицы. Организовать процедуру поиска по ключу в этой хеш-таблице. Результат поиска - номер ячейки с найденным ключом или (-1).

Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования хеш-адреса использовать хеш-функцию универсального хеширования и процедуру линейного исследования для разрешения коллизии.

Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования начального хеш-адреса использовать метод деления, а затем при возникновении коллизии процедуру квадратичного исследования.

Построить хеш-таблицу с открытой адресацией, используя двойное хеширование, как способ открытой адресации. Хеш-функция h₁(k) и h₂(k) организовать методом деления. Формирование таблицы - с помощью процедуры поиска и вставки по ключу.

Организовать хеш-таблицу, используя хеш-функцию h(k) по методу умножения для формирования хеш-адреса. разрешение коллизий - методом внешних цепочек.

а) Написать процедуру поиска и вставки по ключу.

б) Написать процедуру удаления ключа.

Организовать хеш-таблицу с помощью идеального хеширования - двухуровневая схема с универсальным хешированием на каждом уровне. Запрограммировать процедуру поиска и вставки по ключу.

Организовать программно хеширование 100 записей в таблицу. состоящую из 20 ссылок на линейные списки (стеки), первоначально пустые. записи имеют неотрицательные целые ключи k<50, формируемые случайным образом. Хеш-функцию организовать методом умножения в отдельной Function.

Организовать программно хеширование 50 записей в таблицу. состоящую из 10 ссылок на линейные списки (очереди), первоначально пустые. записи имеют неотрицательные целые ключи k<30, формируемые случайным образом. Хеш-функцию организовать методом деления в отдельной Function

Контрольные вопросы

1. Что такое хеширование?

2. Какую структуру данных используют для формирования хеш-таблицы?

3.Что мы называем ситуацией конфликта или коллизией, возникающей при хешировании?

4. Как организована -таблица с прямой адресацией?

5. В чем заключается метод цепочек разрешения коллизии при хешировании?

6. Какие вы знаете хеш-функции?

7. Что такое хеш-таблица с открытой адресацией и каковы способы разрешения коллизий для нее?

8. Какова основная идея идеального хеширования?

9. Сформулируйте основное правило формирования вторичной хеш-таблицы.