Algorytmy
49,00 zł
Nowoczesne receptury w Javie. Proste rozwiązania trudnych problemów
−30%38,43 zł
Wprowadzenie do obliczeń równoległych
−16%49,45 zł
Informatyka Europejczyka. Podręcznik dla szkoły podstawowej. Klasa 8
9,90 zł
Python. Uczenie maszynowe
69,00 zł
TDD. Techniki programowania sterowanego testami
59,00 zł

Algorytm

Algorytm genetyczny, schemat blokowy Przykład zapisu algorytmu za pomocą schematu blokowego

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

Zapis algorytmu

Algorytm można zapisać na różne sposoby. Najczęściej stosowane metody zapisu algorytmu to:

  • język naturalny (opis słowny),
  • schemat blokowy,
  • pseudokod (zapis przypominający język programowania, jednak nie będący nim),
  • język programowania.

Złożoność obliczeniowa

Do oceny algorytmu zazwyczaj wyznacza się jego złożoność czasową i pamięciową, czyli zależność pomiędzy rozmiarem danych wejściowych a czasem wykonania algorytmu i ilością wymaganej pamięci. Czas działania algorytmu jest wyrażony jako liczba operacji elementarnych (np. operacji porównania czy przypisania), które trzeba wykonać. Obliczanie czasu w fizycznych jednostkach byłoby znacznie mniej uniwersalne, ponieważ zależałoby to m.in. od szybkości komputera. Aby uprościć analizę, najczęściej bierze się pod uwagę wyłącznie wybrane operacje, określane jako operacje dominujące – są to operacje, których liczba wykonań jest proporcjonalna do liczby wykonań wszystkich operacji elementarnych.

Zazwyczaj nie jest potrzebna postać funkcji określającej złożoność, ale jedynie jej rząd wielkości. Jest to określane jako asymptotyczna złożoność obliczeniowa. Do oznaczania tej złożoności powszechnie stosuje się tzw. notację dużego O. Notacja ta określa asymptotyczne ograniczenie górne funkcji złożoności. Jeśli funkcja jest rzędu O(g(n)), to dla wystarczająco dużego n spełniona jest zależność 0≤f(n)≤cg(n), gdzie c jest stałą.

Powszechnie uznaje się, że akceptowalne są algorytmy o złożoności co najwyżej wielomianowej (O(nk), gdzie k nie zależy od rozmiaru danych wejściowych). Algorytmy o złożonościach wyższych rzędów (np. O(kn), O(n!), O(nn)) w praktyce działają w rozsądnym czasie tylko dla danych wejściowych o niewielkich rozmiarach.

Bibliografia

  1. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012.
  2. Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 27 czerwca 2017 18:10, ostatnia edycja: 1 lutego 2018 16:19.

Zobacz też

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość

Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.

→ Czytaj całość

Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.

Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.

Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:

  • Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
  • Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).

Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.

→ Czytaj całość
Polityka prywatnościKontakt