Nr 01 · Słownik · Teoria informatyki · Algorytmy i struktury danych

Paradygmaty algorytmiczne

23 pojęć w 17 podgrupach, z prostymi definicjami i źródłami.

Decyzje bez przyszlosci · 1

  • 01algorytm onlineAlgorytm przetwarzający dane wejściowe w strumieniu i podejmujący nieodwołalne decyzje bez znajomości przyszłych danych.

Dekompozycja rekurencyjna · 1

  • 01dziel i zwyciężajParadygmat rozwiązywania problemu przez podział na mniejsze podproblemy tego samego typu, ich niezależne rozwiązanie i scalenie wyników.

Gwarancja jakosci · 1

  • 01algorytm aproksymacyjnyAlgorytm dla problemu optymalizacyjnego zwracający rozwiązanie z gwarantowanym ograniczeniem odchylenia od optimum.

Kierunek obliczen · 2

  • 01podejście wstępująceang. bottom-upSposób organizacji obliczeń od najmniejszych podproblemów ku problemowi głównemu, z wypełnianiem tablicy rozwiązań.
  • 02podejście zstępująceang. top-downSposób organizacji obliczeń rekurencyjnych od problemu głównego ku podproblemom, zwykle z zapamiętywaniem wyników.

Konstrukcja stopniowa · 2

  • 01algorytm inkrementalnyAlgorytm budujący rozwiązanie przez dodawanie elementów wejścia po jednym i aktualizację bieżącego rozwiązania.
  • 02algorytm zamiataniaang. sweep lineTechnika geometryczna przetwarzająca obiekty w kolejności przecięcia ich z ruchomą linią lub płaszczyzną zamiatającą.

Losowosc w obliczeniach · 3

  • 01algorytm Las VegasAlgorytm zrandomizowany zawsze zwracający poprawny wynik, którego czas działania jest zmienną losową.
  • 02algorytm Monte CarloAlgorytm zrandomizowany o gwarantowanym czasie działania, którego wynik może być błędny z ograniczonym prawdopodobieństwem.
  • 03algorytm zrandomizowanyAlgorytm wykorzystujący w trakcie działania losowe wybory, którego wynik lub czas działania zależy od źródła losowości.

Odcinanie galezi · 1

  • 01metoda podziału i ograniczeńang. branch and boundTechnika rozwiązywania zadań optymalizacji przez podział przestrzeni na podzbiory i odcinanie tych, których oszacowanie wyklucza optimum.

Optymalizacja ciagla · 1

  • 01programowanie linioweLP (ang. linear programming)Metoda optymalizacji funkcji liniowej przy ograniczeniach w postaci liniowych nierówności i równości.

Optymalizacja podstrukturalna · 1

  • 01programowanie dynamiczneTechnika rozwiązywania problemów z podproblemami nakładającymi się, polegająca na jednokrotnym obliczaniu i zapamiętywaniu rozwiązań podproblemów.

Oszacowania · 1

  • 01relaksacjaZłagodzenie ograniczeń problemu w celu uzyskania łatwiejszego zadania, którego rozwiązanie daje oszacowanie optimum oryginału.

Podejscie zstepujace · 1

  • 01memoizacjaTechnika przyspieszania obliczeń przez buforowanie wyników wywołań funkcji i zwracanie ich przy powtórnym wywołaniu z tymi samymi argumentami.

Podzial przeszukiwania · 1

  • 01metoda spotkania w środkuang. meet in the middleTechnika redukcji przeszukiwania wyczerpującego przez podział wejścia na dwie połowy, przeszukanie każdej i połączenie częściowych wyników.

Przesuwne indeksy · 1

  • 01metoda dwóch wskaźnikówang. two pointersTechnika przetwarzania struktury liniowej przy użyciu dwóch indeksów poruszających się po niej według ustalonej reguły.

Przeszukiwanie systematyczne · 2

  • 01powrótang. backtrackingMetoda przeszukiwania przestrzeni rozwiązań przez systematyczne rozszerzanie częściowego rozwiązania i wycofywanie się po napotkaniu ślepej ścieżki.
  • 02przeszukiwanie wyczerpująceang. brute forceStrategia rozwiązywania problemu przez systematyczne wygenerowanie i sprawdzenie wszystkich kandydatów na rozwiązanie.

Rozwiazania przyblizone · 2

  • 01heurystykaReguła lub metoda dająca akceptowalne rozwiązanie szybciej niż metoda dokładna, bez gwarancji optymalności.
  • 02metaheurystykaOgólny szkielet heurystyk wyższego poziomu sterujący przeszukiwaniem przestrzeni rozwiązań, niezależny od konkretnego problemu.

Transformacja problemu · 1

  • 01redukcjaPrzekształcenie jednego problemu w inny, tak że rozwiązanie drugiego daje rozwiązanie pierwszego; podstawa projektowania i klasyfikacji złożoności.

Wybor lokalny · 1

  • 01algorytm zachłannyStrategia budowy rozwiązania przez wybór w każdym kroku opcji lokalnie najlepszej, bez rewizji wcześniejszych decyzji.

Pozostałe grupy — Algorytmy i struktury danych

Grupa pojęć · Algorytmy i struktury danych23 haseł