Теория на алгоритмите

20

Хеш-татблиците е структора от данни, за която е характерен директен достъп до елементите, независимо от типа им. Сложноста на елементарните операции по ключ(търсене, вмъкване, изтриване и актуализиране) в общия случай е константа, което я прави изключително полезна в много ситуации. При дефинирането на хеш – таблица като абстрактна структура ще се ограничим до следните три класически операции:

Void put(key,data); - включване на елементи

Data get (key); - търсене на елемент

Void remove (key); - изключване на елемент

Всеки елемент на хеш – таблиата се характеризира с две полета: ключ key и данни data. Ключът представлява уникален идентификатор:ако два елемента имат един и същ ключ те се считат за идентични.

Прецесът при който по зададен ключ на елемент се определя неговият адрес с константна сложност се нарича хеширане


Класически хеш – функции

Дали даден избор на хеш – функция е удачен се определя от две неща: хеш – функцията да не отнема много изчислително време и да разпределя елементите относително равномерно в различните хеш – адреси


Хеш – функции върху части от ключа

  • извличане на цифри

При тази схема от ключа се извличат само цифри, намиращи се на определи позиции.

  • сгъване

Този метод се прилага най-често когато ключовете са много големи числа.Например числото може да се раздели на две и повече части и сумата от получените числа да определя хеш – адреса

  • повдигане на средата в квадрат

Тази схема се основава на извличане на средните p цифри ма ключа и повдигането им в квадрат. Например за ключа 125657134280980 средните цифри са 134. Повдигаме ги в квадрат 134.134 =17956, ако резултатът надхвърля n се премахват първите няколко значещи цифри: например ако n = 10001 то от 17956 се премахва първата цифра и полученият хеш – адрес е 7956










14

Нека е даден ориентиран граф G(V,E) и търсим най-кратките растояния от даден връх S до всички останали върхове. Щв приемем че работим с матрицата на теглата A(i),(j) на графа G. В случаите когато не съществува реброто (i,j) като стойност на A(i),(j) ще бъде записано безкр.(знак) .

Алгоритъм на форд – белман


Други реферати:
Източник на комуникации
Начало на организирано националноосвободително движение
Илюстрация на подкрепящия стил на комуникация
Начало на организирано национално-революционно движение 50-те-60-те год. на 19 век
Имидж-бизнескомуникации


Изтегли реферата



Имидж-бизнескомуникации - Facebook Image
Сайтът се поддържа от DH Studio | pomagalo1.com © 2012 | Общи условия