deelprobleem

Deelprobleem is een term uit de wiskunde en informatica die verwijst naar een subprobleem dat voortkomt uit het oplossen van een groter probleem door het op te splitsen in kleinere taken. Elk deelprobleem is op zichzelf een probleem dat, wanneer het is opgelost, bijdraagt aan de oplossing van het oorspronkelijkeprobleem. Het idee ligt aan de basis van veel oplossingsstrategieën voor complexe taken.

In de computerwetenschap spelen deelproblemen een centrale rol bij algoritmeontwerp. Bij divide-and-conquer wordt een probleem opgesplitst in kleinere, meestal soortgelijke deelproblemen die apart worden opgelost en vervolgens worden samengevoegd tot een oplossing voor het hoofdprobleem. Bij dynamisch programmeren bestaan vaak overlappende deelproblemen; nadat een deelprobleem is opgelost, wordt het resultaat hergebruikt via memoization of via een bottom-up berekening, waardoor efficiëntie wordt bereikt.

Voorbeelden zijn onder meer: de Fibonacci-reeks, waarbij fib(n) afhankelijk is van de oplossingen voor fib(n-1) en fib(n-2); mergesort, waarbij de array wordt gesorteerd door de twee helften als deelproblemen te sorteren en vervolgens te combineren; en kortste-padproblemen, waarbij de kosten om een knoop te bereiken afhangen van optimale kosten om eerdere knopen te bereiken.

Identificeren van deelproblemen gebeurt door te zoeken naar recursieve herhaling, subtaken die het oorspronkelijke probleem spiegelbeeldig weergeven en potentieel hergebruik van oplossingen. Een belangrijke onderscheiding is die tussen overlappende deelproblemen (waar dynamisch programmeren toegevoegde waarde biedt) en onafhankelijke deelproblemen (vaak bij divide-and-conquer). Etymologisch komt deel van het Nederlandse deel en probleem van het woord probleem.

Deelproblemen vormen een fundamenteel concept in algoritmen, optimalisatie en onderwijs over probleemoplossing.