ScanImage005 (10)

1.2. PRZYKŁADOWY PROBLEM: POŁĄCZENIA SSSS 355S? 55SJ S5S8: >5>S!

Na rysunku 1.2 przedstawiono oba typy zastosowań na bardziej obszernych danych. Analiza tego rysunku daje pewien pogląd na to, jak złożony może być problem analizy połączeń. Jak szybko można stwierdzić, czy dane dwa punkty takiej sieci są ze sobą połączone?

Kolejny przykład omawianego zagadnienia pojawia się w pewnych środowiskach programowania, w których istnieje możliwość zadeklarowania dwóch nazw zmiennych jako równoważnych. Problem polega na tym, by mając wczytaną sekwencję deklaracji, stwierdzić, czy dane dwie nazwy są równoważne. To zastosowanie należy do jednego z pierwszych. Zainspirowało ono rozwój kilku algorytmów, którymi się zajmiemy. Ma ono związek z naszym zadaniem poprzez prostą abstrakcję zapewniającą sposób wykorzystania algorytmów w szerokiej - jak zobaczymy - gamie zastosowań.

Zastosowania takie jak problem równoważności nazw, opisany w poprzednim akapicie, wymaga skojarzenia liczby naturalnej z poszczególnymi nazwami. To skojarzenie występuje ró-wnież w aplikacjach analizujących połączenia sieciowe i elektryczne, które opisano wcześniej. Grupę algorytmów' zapewniających takie skojarzenie w efektywny sposób będziemy rozważać w' rozdziałach od 10 do 16. Możemy więc założyć w tym rozdziale, nie tracąc na ogólności, że dysponujemy n obiektami o nazwach od 0 do n - 1.

3-4	3-4
4-9	4-9
8-0	8-0
2-3	2-3
5-6	5-6
2-9		2-3-4-9
5-9	5-9
7-3	7-3
4-8	4-8
5-6		5-6
0-2		0-8-4-3-2
6-1	6-1

Rysunek 1.1

Przykład działania algorytmu analizującego połączenia

Mając zbiór par liczb naturalnych, reprezentujących połączenia między obiektami (lewa kolumna), należy za pomocą algorytmu analizującego połączenia wyznaczyć te pary, które tworzą nowe połączenia {środkowa kolumna). Na przykład para 2-9 (wprowadzona na wejściu jako szósta) nie zostanie wyprowadzona na wyjście, ponieważ między punktem 2 i 9 istnieje już połączenie (2-3-4-9) zrealizowane z udziałem wcześniej wprowadzonych par (dowód tego przedstawiony jest w prawej kolumnie).

Potrzebny jest nam program wykonujący konkretne, dobrze zdefiniowane zadanie. Ponadto istnieje wicie zadań podobnych, które też chętnie rozwiążemy. Jednym 7. pierwszych problemów', z jakim będziemy się borykać przy opracowywaniu algorytmu, będzie logiczne sformułowanie zagadnienia. W większości sytuacji możemy przyjąć, że im więcej oczekujemy od algorytmu, tym więcej czasu i pamięci będzie potrzebne do realizacji zadania. Ocena tej zależności jest niemożliwa a priori, dlatego często będziemy modyfikować specyfikację problemu, kiedy okaże się, że jego rozwiązanie jest trudne lub drogie albo - jeżeli będziemy mieli szczęście - kiedy okaże się, że algorytm może być pomocny przy wydobywaniu dodatkowych informacji ponad te, które określono w pierwotnej specyfikacji.

Na przykład specyfikacja problemu analizy połączeń wymaga tylko tego, by program w jakiś sposób stwierdzał, czy dana para p-q reprezentuje obiekty połączone, czy nie, a nie by demonstrował jakiekolwiek lub wszystkie sposoby połączeń pary obiektów. Dodanie takiego wymogu do naszej specyfikacji komplikuje problem i mogłoby doprowadzić nas do innej rodziny algorytmów, którą pokrótce zajmiemy się w rozdziale 5, a szczegółowo w części 7¹.

1

Por. przyp. 2 zc s. V.

7 JWW 3K8K I