Login lub e-mail Hasło   

Algorytmy wyszukujące - wstęp

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Wyszukiwanie informacji należy do podstawowych problemów programowania, z którymi spotka się codziennie każdy programista. A oto kilka przykładów, gdzie w...
Wyświetlenia: 3.968 Zamieszczono 02/11/2006

Wyszukiwanie informacji należy do podstawowych problemów programowania, z którymi spotka się codziennie każdy programista. A oto kilka przykładów, gdzie wyszukiwanie jest niezbędne:
  • Bankowość - wyszukiwanie dłużników, którzy nie spłacają kredytów. Również wyszukiwanie wzorowych klientów. Wyszukanie klienta o podanym numerze konta lub znalezienie numeru konta na podstawie danych osobowych klienta.
  • Sport - na podstawie osiągniętych wyników wyznaczenie trzech kolejnych zwycięzców na pierwsze, drugie i trzecie miejsce.
  • Hotelarstwo - wyszukiwanie wolnych pokoi w danym terminie oraz pokoi zarezerwowanych.
  • Fizyka - wyszukanie w danych pomiarowych wartości spełniających określone wymagania.
  • Chemia - wyszukiwanie związków chemicznych na podstawie ich własności.
  • Kryminalistyka - wyszukiwanie osób o podanych cechach (np. wzrost, waga, rozmiar obuwia, odciski palców, kolor włosów itp.).
  • Samochody - wyszukiwanie właściciela pojazdu na podstawie numeru rejestracyjnego lub określonych cech samochodu (marka, kolor, rok produkcji, numer silnika lub nadwozia, itp.).

Przykłady można mnożyć w nieskończoność. Celem naszego artykułu jest zaznajomienie uczniów z podstawowymi algorytmami wyszukiwania danych w zbiorach uporządkowanych oraz nieuporządkowanych.

W informatyce algorytm wyszukujący otrzymuje na wejściu pewien problem i daje na wyjściu jego rozwiązanie po przetestowaniu pewnej ilości możliwych rozwiązań.

Większość algorytmów rozwiązujących problemy (np. algorytmy gry w szachy, warcaby, karty itp.) są pewnego rodzaju algorytmami wyszukującymi. Zbiór wszystkich możliwych rozwiązań danego problemu nosi nazwę przestrzeni poszukiwań (ang. search space). Najprostszymi algorytmami wyszukującymi są algorytmy naiwne, które stosują najbardziej intuicyjną metodę wyszukiwania w przestrzeni poszukiwań. Wymyślono jednakże bardziej zaawansowane metody wykorzystujące wiedzę na temat samej struktury przestrzeni poszukiwań w celu zmniejszenia ilości czasu traconego na poszukiwania.

Problem wyszukiwania danych jest powiązany z problemem sortowania - duża klasa algorytmów wyszukujących operuje na zbiorach posortowanych. Dlatego polecamy naszym czytelnikom zapoznanie się z artykułem o algorytmach sortujących.

Omawiane tematy są ilustrowane licznymi przykładami prostych programów, które uczeń może pobrać z naszej witryny, przeanalizować oraz uruchomić na swoim komputerze.

   
   
   

Przykładowe programy w języku Pascal zostały uruchomione w środowisku Borland Delphi 7.0 Personal Edition, które można darmowo i legalnie ściągnąć z witryny firmy Borland. Gorąco polecamy to rozwiązanie, gdyż uzyskujemy produkt w pełni funkcjonalny i licencjonowany - nie możemy jedynie przy jego pomocy tworzyć aplikacji komercyjnych.

Aby pobrać odpowiednie pliki instalacyjne, musisz zarejestrować się w witrynie firmy Borland. Tutaj znajdziesz dokładną instrukcję procedury rejestracyjnej.

 
       

 

   
   
   

Przykładowe programy w języku C++ zostały uruchomione w środowisku Borland C++ Builder Personal Edition, które można darmowo i legalnie ściągnąć z witryny firmy Borland. Gorąco polecamy to rozwiązanie, gdyż uzyskujemy produkt w pełni funkcjonalny i licencjonowany - nie możemy jedynie przy jego pomocy tworzyć aplikacji komercyjnych.

Aby pobrać odpowiednie pliki instalacyjne, musisz zarejestrować się w witrynie firmy Borland. Tutaj znajdziesz dokładną instrukcję procedury rejestracyjnej.

 
       

 

   
   
   

Przykładowe programy w języku Basic zostały uruchomione w środowisku Microsoft Visual Basic 2005 Express Edition, które jest częścią pakietu Visual Studio 2005 Express Edition udostępnionego zupełnie darmowo przez firmę Microsoft. Legalną kopię pakietu Visual Basic możesz pobrać z witryny internetowej firmy Microsoft. Polecamy instalację tego pakietu, gdyż firma Microsoft udostępnia nam nawet darmową licencję na komercyjne wykorzystanie utworzonych w tym systemie programów.

 
       

 

   
   
   

Język Python jest popularnym językiem skryptowym, który jest zarówno prosty w nauce jak i potężny w zastosowaniach. Posiada on wiele ciekawych cech przydatnych dla młodych informatyków. Środowisko programowania w języku Python jest darmowe i ogólnie dostępne ze strony firmowej. W razie problemów, plik instalacyjny (dla instalatora Windows) można również pobrać z naszego serwera. Jednak polecamy ten pierwszy sposób, ponieważ język jest ciągle ulepszany i poprawiany, zatem u producenta dostaniesz zawsze najnowszą wersję.

Instalacja jest bardzo prosta:

  1. Ściągnij na swój dysk twardy plik instalacyjny - u nas jest to python.msi.

  2. Kliknij dwukrotnie myszką w ten plik - powinien zostać uruchomiony instalator Windows.

  3. W okienkach instalacyjnych zaznacz odpowiedni katalog, gdzie ma być zainstalowany Python.

  4. Po instalacji z menu głównego wybieramy IDLE (Python GUI).

  5. W okienku interpretera wybieramy opcję File -> New Window, która otwiera okno edytora.

  6. W oknie edytora wprowadzamy program i uruchamiamy go klawiszem F5. Program można zapisać na dysku i uruchamiać tak, jak każdy inny program w Windows - przez podwójne kliknięcie myszką.

Programy możemy przenosić z naszych stron do edytora poprzez schowek Windows.

 
       

 

   
   
   

Przykłady w języku JavaScript można uruchomić nawet przy pomocy ogólnie dostępnego Notatnika z systemu Windows. Jednakże nie polecamy tego sposobu - my korzystaliśmy z programu Microsoft Frontpage. Aby uruchomić przykłady, należy zaznaczyć na stronie WWW fragment obejmujący tekst programu wraz z odpowiednim kodem HTML, skopiować go do schowka Windows, wkleić do notatnika lub edytora kodu html w programie FrontPage i zapisać na dysku pod dowolną nazwą z rozszerzeniem htm lub html (np. index.html). Tak utworzony plik możemy w dalszej kolejności uruchomić w dowolnej przeglądarce internetowej - najlepiej Internet Explorer. W razie problemów proszę skontaktować się z autorem artykułu.

 
       

 

Ponieważ dostaję dużo listów od nieuważnych czytelników, wyjaśniam, iż prezentowane programy są jedynie przykładami realizacji opisywanych algorytmów w wybranych językach programowania. W żadnym razie nie są one celem artykułu. Celem są ALGORYTMY. Znając algorytm można napisać dobry program w dowolnym języku programowania. Dla uzasadnienia mojej postawy przytoczę znany cytat profesora Donalda Knutha (jednego z największych współczesnych autorytetów w dziedzinie informatyki):

"Languages come and go,
but algorithms stand the test of time
"

Donald Knuth

"Języki programowania pojawiają się i odchodzą,
lecz algorytmy wytrzymują próbę czasu
"


Donald Knuth

Zapraszam do lektury
mgr Jerzy Wałaszek

 

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


7
komentarze: 1 | wyświetlenia: 6262
16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64980
12
komentarze: 3 | wyświetlenia: 29779
37
komentarze: 9 | wyświetlenia: 28522
11
komentarze: 2 | wyświetlenia: 33154
18
komentarze: 11 | wyświetlenia: 9268
7
komentarze: 1 | wyświetlenia: 34650
17
komentarze: 4 | wyświetlenia: 14189
15
komentarze: 5 | wyświetlenia: 32763
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 2 | wyświetlenia: 18506
11
komentarze: 1 | wyświetlenia: 86408
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska