greedy algoritmer begrippen

Vad är en greedy algoritm?

En algoritm som gör lokala optimala val i hopp om att hitta en global optimal lösning.

Ge ett exempel på en greedy algoritm.

Kruskal's algoritm för att hitta minimal spännande träd.

Sant eller falskt: Greedy algoritmer garanterar alltid bästa lösningen.

Falskt. De ger inte alltid den globala optimala lösningen.

Definiera 'lokalt optimalt val'.

Ett val som är bäst vid det aktuella tillfället utan att beakta framtida konsekvenser.

Vad är ett greedy choice property?

Egenskapen att lokala optimala val leder till en global lösning.

Fyll i: Greedy algoritmer arbetar ofta med ________.

sorterade eller prioriterade data.

Jämför greedy algoritmer med dynamisk programmering.

Greedy: lokala val, snabba. Dynamisk programmering: global lösning, mer beräkningskrävande.

Nämn en fördel med greedy algoritmer.

De är ofta enklare och snabbare att implementera.

Vad innebär 'optimal substruktur'?

En lösning av ett problem kan byggas upp av optimala lösningar av dess delproblem.

Ge ett exempel på när en greedy algoritm fungerar.

Aktivitetsschemaläggning där man väljer den mest tidsoptimala aktiviteten.

Vad står 'greedy' för?

Ordet beskriver algoritmens benägenhet att välja det mest fördelaktiga alternativet varje gång.

Vad är en kritisk egenskap för greedy algoritmer?

Att de måste uppfylla både greedy choice property och optimal substruktur.

Vad är ett exempel på ett greedy algoritm?

Prim's algoritm för att hitta minimala spännande träd.

Vad används Dijkstra's algoritm för?

Att hitta den kortaste vägen i en graf med positiva vikter.

Sant eller falskt: Greedy algoritmer ger alltid en optimal lösning.

Falskt - de ger inte alltid optimal lösning, men ofta en bra approximation.

Fyll i: Greedy algoritmer bygger på _______.

lokala optima.

Jämför: Greedy algoritmer vs dynamisk programmering.

Greedy: lokal lösning; Dynamisk: global lösning.

Vilket problem löser aktivitetsval algoritmen?

Maximera antalet aktiviteter som kan utföras i ett tidsintervall.

Ge ett exempel på ett problem där greedy algoritmer fungerar bra.

Mynterväxlingsproblem med standardvaluta.

Hur används Huffman-kodning?

För effektiv kodning av data genom att använda kortare koder för vanliga tecken.

Sant eller falskt: Greedy algoritmer är alltid snabba.

Sant - de har ofta låg tidskomplexitet.

Vad är en tillämpning av Knapproblem?

Maximera värdet av föremål som kan bäras i en ryggsäck med begränsad vikt.

Ge ett exempel på tillämpning av greedy algoritmer inom nätverk.

Minimala kostnadsbrytningar i nätverksdesign.

Hur fungerar greedy algoritmer i schemaläggningsproblem?

De väljer den mest lovande uppgiften baserat på kortast tidsåtgång.

Vad innebär tidskomplexitet för greedy algoritmer?

Tidskomplexitet beskriver hur algoritmens körningstid ökar med storleken på indata. Greedy algoritmer har ofta en tidskomplexitet på $\displaystyle O(n imes ext{log} n)$ eller $\displaystyle O(n)$ beroende på implementeringen.

Vad innebär rumskomplexitet?

Rumskomplexitet refererar till den mängd minnesutrymme som krävs av algoritmen för att köra. Greedy algoritmer är vanligtvis effektiva med minne och kräver ofta $\displaystyle O(1)$ eller $\displaystyle O(n)$.

Är greedy algoritmer alltid optimala?

Falskt. Greedy algoritmer ger ibland inte den bästa lösningen. De fungerar bäst när problemet uppfyller optimalitetsprincipen.

Ge exempel på en greedy algoritm.

Ett exempel är Dijkstra's algoritm för kortaste vägen. Den väljer successivt den minst kostsamma noden tills målet uppnås.

Vad är skillnaden mellan greedy och dynamisk programmering?

Greedy algoritmer gör lokala optimeringar; dynamisk programmering löser delproblem och bygger upp till en global lösning. - Greedy: snabbare, enklare. - Dynamisk programmering: mer minneskrävande, mer exakt.

Fyll i: Greedy algoritmer använder ______ för att fatta beslut.

lokala optimala val

Hur analyserar man rumskomplexitet?

Genom att räkna antalet variabler och datastrukturer som används under algoritmens körning. Notera minnesanvändning vid varje steg.

Vad påverkar prestandan hos en greedy algoritm?

Prestandan påverkas av datamängdens storlek, typen av greedy val som görs, och eventuell sortering av indata.

Ge ett exempel på en icke-optimal greedy algoritm.

Kruskal's algoritm kan ge icke-optimal lösning i vissa grafiska problem när inte alla kanter beaktas initialt.

Vad är en vanlig metod för att bevisa korrekthet hos greedy algoritmer?

Induktiv bevismetod. Man visar att om algoritmen fungerar för en mindre del av problemet, så fungerar den för hela problemet.

Hur kan vi förbättra prestandan hos greedy algoritmer?

Genom att optimera valmetoder, använda effektiva datastrukturer som prioritetsköer, och minska onödig beräkning.

Är greedy algoritmer alltid snabba?

Falskt. Även om de är snabba i många fall kan prestandan variera beroende på indata och problemets natur.