74804 ScanImage004 (11)

WPROWADZENIE

sa# mf &ms && vss& om

Wybór najlepszego algorytmu dla danego zadania może być procesem złożonym, wymagającym często znajomości zaawansowanego aparatu matematycznego. Dziedzina informatyki, której domeną jest badanie omawianych tu kwestii, nazywa się analizą algorytmów. Zajmujący się nią naukowcy wykazali dla wielu przedstawionych w tym podręczniku algorytmów, że mają one wysoką wydajność. O pozostałych algorytmach wiadomo z praktyki, żc działają dobrze.

Naszym głównym celem jest zaprezentowanie algorytmów o rozsądnym stopniu złożoności dla ważniejszych problemów, choć będziemy również zw racać szczególną uwagę na porównania wydajności różnych metod rozwiązywania zadań. Nie zdarzy się, żc zastosujemy algorytm, nie wnikając w to, jakie zasoby może on pochłaniać. Nasze aspiracje oscylują zawsze wokół dążenia do wyznaczenia lub choćby przybliżenia wydajności każdego algorytmu.

1.2. Przykładowy problem: Połączenia

Dany jest zbiór par liczb naturalnych. Każda liczba reprezentuje obiekt pewnego typu. Parę p-q interpretujemy jako zdanie „p jest połączono z q”. Zakładamy, że relacja, jest połączone z” jest przechodnia, czyli jeśli p jest połączone z q. a q jest połączone z. r, to pjest połączone z r. Zadanie polega na napisaniu programu, który przefiltruje pary ze zbioru w następujący sposób: program ma przesłać na wyjście podaną mu na wejściu parę p-q tylko wtedy, gdy na podstawie relacji między parami wcześniej wprowadzonymi można wywnioskować, iż między p i q istnieje połączenie. Jeżeli nie da się wywnioskować, że takie połączenie między p i q istnieje, wówczas program powńnien zignorować parę p-q i przejść do pobierania następnej pary. Przykładowe działanie filtru pokazano na rysunku 1.1.

Należy' więc napisać program, który' będzie pamiętał takąporcję informacji o parach, które wcześniej podano mu na wejściu, aby mógł zadecydować, czy nowa para reprezentuje obiekty połączone, czy nie. Nieformalnie możemy opracowanie metody postępowania tego programu nazwać rozwiązywaniem problemu połączeniowego. Problem taki występuje w wiciu ważnych dziedzinach. Poniżej przedstawiono pokrótce trzy przykłady rzeczywistych sytuacji, w których się on pojawia. Na ich podstawie łatwiej zrozumieć jego naturę.

Liczby naturalne mogą reprezentować komputery z ogromnej sieci, a pary połączenia sieciowe. Wówczas nasz program mógłby podejmować decyzje, czy w celu prowadzenia komunikacji między komputerami p i q potrzebne jest nawiązanie now'ego połączenia bezpośredniego między nimi, czy też wystarczy skorzystać z połączeń istniejących (ze ścieżki takich połączeń). Może się okazać, żc taka aplikacja będzie używana do rozpatrywania milionów punktów' (komputerów) i miliardów połączeń. Jak niebawem zostanie pokazane, zadania takiego nie da się rozwiązać za pomocą nieefektywnego algorytmu.

Liczby naturalne mogą również reprezentować punkty połączeniowe skomplikowanego obwodu elektronicznego, a pary - przewody łączące te punkty. W tym przypadku nasz program mógłby zostać wykorzystany do znalezienia sposobu połączenia wszystkich punktów' bez użycia zbędnych przewodów, o ile byłoby to możliwie. Nic ma gwarancji, że kraw-ędzie z listy wystarczą do połączenia wszystkich punktów i rzeczywiście, przekonamy się w'krótcc, że odpowiedź na pytanie, czy wystarczą, może być głównym zadaniem, do którego zastosujemy nasz program.

\ SWW: 6