Beste antwoord
Classificatie naar doel
Elk algoritme heeft een doel, het doel van het Quick Sort-algoritme is bijvoorbeeld om gegevens in oplopende of aflopende volgorde te sorteren. Maar het aantal doelen is oneindig en we moeten ze groeperen op soort doelen.
Classificatie door implementatie
Een algoritme kan worden geïmplementeerd volgens verschillende basisprincipes.
- Recursief of iterative Een recursief algoritme is een algoritme dat zichzelf herhaaldelijk aanroept totdat een bepaalde voorwaarde overeenkomt. Het is een methode die gebruikelijk is bij functioneel programmeren. Iteratieve algoritmen gebruiken repetitieve constructies zoals lussen. Sommige problemen zijn beter geschikt voor de ene implementatie of de andere. Het probleem van de torens van Hanoi wordt bijvoorbeeld goed begrepen bij recursieve implementatie. Elke recursieve versie heeft een iteratief equivalent iteratief, en vice versa.
- Logisch of procedureel Een algoritme kan worden gezien als gecontroleerde logische deductie. Een logische component drukt de axiomas uit die bij de berekening kunnen worden gebruikt en een besturingscomponent bepaalt de manier waarop deductie op de axiomas wordt toegepast. Dit is de basis van de logische programmering. In pure logische programmeertalen ligt de besturingscomponent vast en worden algoritmen gespecificeerd door alleen de logische component te leveren.
- Serieel of parallel Algoritmen worden doorgaans besproken in de veronderstelling dat computers één instructie van een algoritme tegelijk uitvoeren. Dit is een serieel algoritme, in tegenstelling tot parallelle algoritmen, die gebruikmaken van computerarchitecturen om meerdere instructies tegelijk te verwerken. Ze verdelen het probleem in deelproblemen en geven deze door aan meerdere verwerkers. Iteratieve algoritmen zijn over het algemeen parallelliseerbaar. Sorteeralgoritmen kunnen efficiënt worden geparallelliseerd.
- deterministisch of niet-deterministisch Deterministische algoritmen lossen het probleem op met een vooraf gedefinieerd proces, terwijl niet-deterministische algoritmen bij elke stap de beste oplossing moeten raden door middel van heuristieken.
Classificatie volgens ontwerpparadigma
Een ontwerpparadigma is een domein in onderzoek of een klasse van problemen waarvoor een speciaal soort algoritme vereist is:
- Verdeel en heers Een verdeel en heers-algoritme reduceert herhaaldelijk een instantie van een probleem tot een of meer kleinere instanties van hetzelfde probleem (meestal recursief), totdat de instanties klein genoeg zijn gemakkelijk op te lossen. Een voorbeeld van verdeel en heers is het sorteren van samenvoegingen. Sorteren kan worden gedaan op elk gegevenssegment nadat de gegevens in segmenten zijn verdeeld en het sorteren van volledige gegevens kan in de veroveringsfase worden verkregen door ze samen te voegen. Het binaire zoekalgoritme is een voorbeeld van een variant van verdeel en heers genaamd algoritme voor afname en heers , dat een identiek subprobleem oplost en de oplossing van dit subprobleem gebruikt om op te lossen het grotere probleem.
- Dynamisch programmeren Het kortste pad in een gewogen grafiek kan worden gevonden door het kortste pad naar het doel te gebruiken vanaf alle aangrenzende hoekpunten. Wanneer de optimale oplossing voor een probleem kan worden geconstrueerd van optimale oplossingen tot subproblemen, voorkomt het gebruik van dynamische programmering het opnieuw berekenen van oplossingen die al zijn berekend. – Het belangrijkste verschil met de “verdeel en heers” -benadering is dat subproblemen onafhankelijk zijn in verdeel en heers, terwijl de overlap van subproblemen zich voordoen bij dynamisch programmeren. – Dynamisch programmeren en memo maken gaan hand in hand. Het verschil met ongecompliceerde recursie zit in caching of memoisatie van recursieve oproepen. Waar subproblemen onafhankelijk zijn, is dit nutteloos. Door memoisatie te gebruiken of een tabel met reeds opgeloste subproblemen bij te houden, reduceert dynamisch programmeren de exponentiële aard van veel problemen tot polynoomcomplexiteit.
- De hebzuchtige methode Een hebberig algoritme is vergelijkbaar met een dynamisch programmeeralgoritme, maar het verschil is dat oplossingen voor de deelproblemen niet in elke fase bekend hoeven te zijn. In plaats daarvan kan een “hebzuchtige” keuze worden gemaakt van wat op dit moment de beste oplossing lijkt. Het meest populaire hebzuchtige algoritme is het vinden van de minimaal opspannende boom, zoals gegeven door Kruskal.
- Lineair programmeren Het probleem wordt uitgedrukt als een reeks lineaire ongelijkheden en vervolgens wordt een poging gedaan om de input te maximaliseren of te minimaliseren. Dit kan veel problemen oplossen, zoals de maximale stroom voor gerichte grafieken, met name door het simplex-algoritme te gebruiken.Een complexe variant van lineair programmeren wordt programmeren met gehele getallen genoemd, waarbij de oplossingsruimte beperkt is tot alle gehele getallen.
- Reductie ook wel transformeren en overwinnen Los een probleem op door het om te zetten in een ander probleem. Een eenvoudig voorbeeld: het vinden van de mediaan in een ongesorteerde lijst is eerst dit probleem vertalen in een sorteerprobleem en het middelste element in een gesorteerde lijst vinden. Het belangrijkste doel van reductie is het vinden van de eenvoudigst mogelijke transformatie.
- Grafieken gebruiken Veel problemen, zoals schaken, kunnen worden gemodelleerd als problemen op grafieken. Er worden algoritmen voor het verkennen van grafieken gebruikt. Deze categorie bevat ook de zoekalgoritmen en backtracking.
- Het probabilistische en heuristische paradigma Probabilistisch Degenen die willekeurig bepaalde keuzes maken. Genetisch Probeer oplossingen voor problemen te vinden door biologische evolutionaire processen na te bootsen, waarbij een cyclus van willekeurige mutaties opeenvolgende generaties van “oplossingen” oplevert. Ze bootsen dus reproductie en “survival of the fittest” na. Heuristiek waarvan het algemene doel niet is om een optimale oplossing te vinden, maar een oplossing bij benadering waarbij de tijd of middelen om een perfecte oplossing te vinden niet praktisch zijn.
Classificatie naar complexiteit
Sommige algoritmen voltooien in lineaire tijd, en sommige voltooien in exponentiële tijd, en sommige worden nooit voltooid.
Bron: Classificatie van algoritmen
Antwoord
Het volgende is een andere manier om algoritmen te classificeren.
Bij competitief programmeren zijn er vier hoofdproblemen: paradigmas oplossen.
Met andere woorden, gegeven een probleem, zijn hier de verschillende benaderingen / tools die u moet nemen om het op te lossen.
- Brute Force / complete zoekopdracht: een methode die naar alle mogelijkheden kijkt en de beste oplossing selecteert.
- Voordelen: eenvoudig, zou altijd de oplossing moeten vinden aangezien u naar alle mogelijkheden kijkt.
- Nadelen : niet haalbaar als de aantal mogelijkheden groeit exponentieel naarmate het aantal items toeneemt
- Verdeel en heers: methode die het probleem in kleinere delen verdeelt en die vervolgens oplost onderdelen. Denk aan binair zoeken.
- Hebzuchtige benadering: methode die op dit moment de beste optie kiest, zonder rekening te houden met de toekomst.
- Voordelen: snel, eenvoudig, kan de beste oplossing krijgen, of een beetje dichtbij komen
- Nadelen: meestal zullen we niet de beste oplossing vinden
- Dynamisch programmeren: Methode die opbouwt naar een oplossing met eerder gevonden deeloplossingen. Absoluut een van de meer geavanceerde technieken, maar buitengewoon krachtig en toepasbaar.
- Voordelen: vindt de optimale oplossing voor veel problemen in polynoomtijd ( terwijl brute kracht exponentieel zou duren)
- Nadelen : moeilijk te begrijpen en toe te passen, kost tijd om de verschillende toestanden en herhaling te begrijpen
Bronnen
Halim, Steven en Felix Halim. Competitief programmeren: de nieuwe ondergrens van programmeerwedstrijden . Lulu, 2013.