Algorytmy. Ćwiczenia
34,90 zł
PHP 7. Algorytmy i struktury danych
−30%41,30 zł
PHP 7. Algorytmy i struktury danych
−30%41,30 zł
Python. Uczenie maszynowe
69,00 zł
Android Studio. Tworzenie aplikacji mobilnych
69,00 zł
JavaScript i jQuery. Interaktywne strony WWW dla każdego
99,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 Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.

Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.

→ Czytaj całość

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.

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość
Polityka prywatnościKontakt