Алгоритм Дейкстри знаходження найкоротшого шляху

⇐ Назад

Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин.

Нехай u — вершина, від якої шукаються відстані, V — множина вершин графа, di — відстань від вершини u до вершини i, , w(i, j) — вага «ребра» (i, j).

Алгоритм:

1. Множина вершин U, до яких відстань відома, встановлюється рівною {u}.

2. Якщо U=V, алгоритм завершено.

3. Потенційні відстані Di до вершин з U\V встановлюються нескінченними.

4. Для всіх ребер (i, j), де i∈U та j∈V\U, якщо Dj>di+w(i, j), то Dj присвоюється di+w(i, j).

5. Шукається i∈V\U, при якому Di мінімальне.

6. Якщо Di дорівнює нескінченності, алгоритм завершено. В іншому випадку di присвоюється значення Di, U присвоюється U∪{i} і виконується перехід до кроку 2.

39. Система доменних імен

Доменна система імен (англ. Domain Name System, DNS) — розподілена система перетворення імені хоста (комп'ютера або іншого мережевого пристрою) в IP-адресу.

Кожен комп'ютер в Інтернеті має свою власну унікальну адресу — число, яке складається з чотирьох байтів. Оскільки запам'ятовування десятків чи навіть сотень — не досить приємна процедура, то всі (чи майже всі) машини мають імена, запам'ятати які (особливо якщо знати правила утворення імен) значно легше.

Уся система імен в Інтернеті — ієрархічна. Є домени найвищого рівня (домени країн, наприклад, ua ) і домени нижчих рівнів.

За порядок у доменах, як правило, відповідає певний комп'ютер, користувачі-адміністратори якого слідкують за тим, щоб не було, наприклад, різних машин з однаковими ІР-адресами.

Служба імен DNS (Domain Name System) — це розподілена база даних доволі простої структури. Для початкового знайомства можна вважати, що це кілька таблиць, у яких записано:

яку ІР-адресу має машина з певним іменем;
яке ім'я має машина з визначеною адресою;
що це за комп'ютер і яка операційна система встановлена на ньому;
куди потрібно направляти електронну пошту для користувачів цієї машини;
які псевдоніми є у даної машини.

40. Адреси мережевих ресурсів

Гіперпосила́ння (інколи гіперланка) — це активний (виділеним кольором) текст, зображення чи кнопка на веб-сторінці, натиснення на яку (активізація гіперпосилання) викликає перехід на іншу сторінку чи іншу частину поточної сторінки.

За іншим визначенням гіперпосилання — це адреса іншого мережевого інформаційного ресурсу у форматі URL (англ. Universal Resource Locator), який тематично, логічно або будь-яким іншим способом пов'язаний з документом, у якому це посилання визначене.

Гіперпосилання — фрагмент HTML-документу та один із базових його елементів. Гіперпосилання у HTML-документі може вказувати як на файл, що лежить у тій самій директорії на сервері, так і вміщати повний шлях URL до файлу, який розташований в Інтернеті. Також можна створювати гіперпосилання на електронну пошту, відео, аудіофайли та інші документи.

Гіперпосилання для користувача — текст або графічне зображення на сайті чи електронному документі, що дозволяє переходити до інших об'єктів Інтернету

Якщо обидва файли розташовуються в одній директорії, вистачить лише вказати ім'я файлу і розширення. Якщо в сусідніх директоріях, слід вказати крім імені та розширення ще й шлях до директорії.

41. Адресація баз даних

??? може в кого в лекціях є?

42. Пошукові вказівники та каталоги

Пошук інформації за конкретними адресами не є завжди достатньо зручним, зокрема у випадку, коли адреси наперед невідомі. Для організації пошуку інформації в мережі Інгернет служать пошукові сервери (пошукові системи). Використовуючи такі сервери, можна подати запит на пошук потрібної інформації, а сервер (система) видасть вам список посилань (адрес) на електронні джерела. При цьому кожна адреса відіграє роль гіперпосилання, активізуючи яке можна тут же відкрити відповідну сторінку. За принципом дії пошукові сервери поділяють на пошукові каталоги та пошукові індекси.

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

каталоги глобальні. Як правило такі в такі каталоги збираються ресурси з усього інтернету, часто каталоги багатомовні.
каталоги регіональні. У каталозі зібрані ресурси мають відношення певної місцевості: міста, села, району.
каталоги тематичні. Каталог присвячений якої-небудь однієї певної тематики

Пошукові каталоги створюються, як правило, вручну. Висококваліфіковані редактори особисто переглядають інформаційний простір WWW, відбирають те, що, на їх думку, становить загальний інтерес, і заносять адреси до каталога. Оскільки каталоги складаються на основі експертних оцінок, то в них відображені кращі Web-ресурси. Недоліком тематичних каталогів є порівняно невелике охоплення існуючих ресурсів Мережі, оскільки відслідкувати весь обсяг інформації, який є в Інтернеті, практично нереально навіть для значного колективу персоналу, який підтримує сервер.

Пошукові індекси працюють як алфавітні- вказівники. У них запит робиться в полі пошуку у вигляді послідовності ключових слів, які відповідають змісту шуканої інформації. У відповідь на такий запит буде видано список Web-сторінок, в яких описуються вказані поняття.

Багато інформаційно-пошукових систем є одночасно і пошуковими каталогами, і пошуковими індексами. Відомими пошуковими серверами є: Google, Yahoo, Yandex, Мета Україна.

⇐ Назад