Kwalifikacja: INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych
Zawód: Technik informatyk , Technik programista
Kategorie: Programowanie webowe Algorytmy i podstawy informatyki
Technika projektowania algorytmów polegająca na dzieleniu problemu na mniejsze podproblemy, aż staną się na tyle proste, że można je rozwiązać bezpośrednio, to:
Odpowiedzi
Źle. To konkretny algorytm sortowania, a nie technika projektowania.
Źle. Sito Eratostenesa to algorytm wyznaczania liczb pierwszych.
Źle. To pojęcie z teorii ciągów, nie metoda projektowania algorytmów.
Dobrze. Problem dzieli się na podproblemy, rozwiązuje i scala wyniki.
Informacja zwrotna
„Dziel i zwyciężaj” (divide and conquer) to ogólna technika projektowania algorytmów: problem dzieli się na mniejsze podproblemy tego samego typu, rozwiązuje je (często rekurencyjnie), a następnie scala wyniki w rozwiązanie całości. Podział trwa, aż fragmenty staną się trywialne. Tak działają m.in. sortowanie szybkie (quicksort), sortowanie przez scalanie (merge sort) czy wyszukiwanie binarne. Dlatego opisana metoda to „dziel i zwyciężaj”.