33.Алгоритм пошуку в ширину

При пошуку в ширину замість стека рекурсивних викликів зберігається черга, в яку записуються вершини в порядку віддалення від початкової. Знову ж таки, введемо масив int visited[N] , а також створимо чергу для зберігання вершин (реалізуємо її у вигляді простого масиву; природно, можливі інші варіанти). На початок черги запишемо початкову вершину:

int queue[N]; queue[0] = start; visited[start] = 1; int r = 0, w = 1;

Змінна r буде вказувати позицію черзі, з якої ми читаємо дані, змінна w - позицію, куди дані будемо писати. Тоді обхід може бути написаний таким чином: while (r < w) { int curr = queue[r++]; for (int i = 0; i < N; i++) { if (!visited[i] && A[curr][i]) { visited[i] = 1; queue[w++] = i; } 34. Алгоритм Дейкстри

Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

Алгоритм Дейкстри будує найкоротші шляхи, що ведуть з вихідної вершини графа до решти вершин цього графа (якщо такі є). У процесі роботи алгоритму послідовно позначаються розглянуті вершини графа. При чому вершина, позначена останньої (на даний момент) розташована ближче до вихідної вершині, ніж всі непозначених, але далі, ніж всі помічені. Спочатку позначається вихідна вершина; наступної, очевидно, буде позначена вершина, найближча до початкової, і суміжна з нею. Нехай на якомусь кроці вже позначені кілька вершин. Відомі найкоротші шляхи, що ведуть з вихідної вершини до поміченої. Для кожної з непозначених вершин проробимо наступне:

Для пошуку найкоротших шляхів між парами вершин зваженого графу з невід'ємними вагами дуг застосовується алгоритм Дейкстри. Послідовність кроків є такою: відмічаємо стартову вершину; для кожної невідміченої вершини будуємо шляхи, що з'єднують її з останньою відміченою вершиною; вибираємо з цих шляхів найкоротший і відмічаємо наступну вершину. Процес триває доти, доки залишаються невідмічені вершини.

35. Алгоритм Флойда

Алгоритм Флойда-Воршелла — алгоритм динамічного програмування для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений в 1962 році Робертом Флойдом і Стівеном Воршеллом.

Для визначеності покладемо, що вершини графа послідовно пронумеровані від 1 до n. Алгоритм Флойда використовує матрицю А розміру п * n, в якій обчислюються довжини найкоротших шляхів. Спочатку A [i, j] = C [i, j] для всіх i! = J. Якщо дуга i - »j відсутня, то C [i, j] = infinity. Кожен діагональний елемент матриці А дорівнює 0.

Над матрицею А виконується п ітерацій. Після k-й ітерації A [i, j] містить значення найменшої довжини шляхів з вершини i в вершину у, які не проходять через вершини з номером, більшим k. Іншими словами, між кінцевими вершинами шляху i і у можуть знаходитися тільки вершини, номери яких менше або дорівнюють k. На k-й ітерації для обчислення матриці А застосовується наступна формула:

Ak[i,j]=min(Ak-1[i,j], Ak-1[i,k]+Ak-1[k,j])

Нижній індекс k позначає значення матриці А після k-й ітерації

36. хеш-функції.

Хеш функція — функція, що перетворює вхідні дані будь-якого (як правило, великого) розміру в дані фіксованого розміру. Хешування (іноді гешування, англ. hashing) - перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки, а їх результати називають хешем, хеш-кодом або дайджестом повідомлення (англ. message digest). Хешування застосовується для порівняння даних: якщо у двох масивів хеш-коди різні, масиви гарантовано розрізняються; якщо однакові - масиви, швидше за все, однакові. У загальному випадку однозначної відповідності між вихідними даними і хеш-кодом немає в силу того, що кількість значень хеш-функцій менше, ніж варіантів вхідного масиву; існує безліч масивів, що дають однакові хеш-коди - так звані колізії. Ймовірність виникнення колізій відіграє важливу роль в оцінці якості хеш-функцій. Існує безліч алгоритмів хешування з різними характеристиками (розрядність, обчислювальна складність, крипостійкість тощо). Вибір тієї чи іншої хеш-функції визначається специфікою розв'язуваної задачі. Найпростішими прикладами хеш-функцій можуть служити контрольна сума або CRC. Криптографічна хеш-функція повинна забезпечувати:

стійкість до колізій (два різні набори даних повинні мати різні результати перетворення);

необоротність (неможливість обчислити вхідні дані за результатом перетворення).