Hoe bouwen Kruskals en Prims algoritmen een minimale opspannende boom?

Voor een samenhangende, ongerichte, gewogen graaf bekijkt Kruskal kanten in oplopend gewicht en gebruikt Union–Find om cycli te verwerpen. Prim breidt één boom uit door steeds een kant met minimaal gewicht te kiezen die de boom met een knoop erbuiten verbindt.

Hoe verwerkt Bellman–Ford negatieve kanten en detecteert het een bereikbare negatieve cyclus?

Relaxeer alle kanten maximaal V−1 keer. Een verdere verbetering vanuit een bereikbare knoop onthult een negatieve cyclus die vanuit de bron bereikbaar is. De slechtste-gevaltijd is O(VE); knopen die vanuit zo’n cyclus bereikbaar zijn hebben geen eindige kortste-padkosten.

Wat is een nonrepeatable read, en welk standaardisolatieniveau voorkomt die?

Bij het opnieuw lezen van een rij zijn gegevens veranderd of is de rij verdwenen nadat een andere transactie een wijziging of verwijdering heeft vastgelegd. REPEATABLE READ en SERIALIZABLE verbieden deze anomalie.

Hoe verschillen primaire en vreemde sleutels in PostgreSQL?

Een primaire sleutel identificeert rijen met unieke waarden die niet NULL zijn. Een vreemde sleutel vereist overeenkomende waarden in de verwezen sleutel, volgens de bijbehorende NULL-regels. Hij kan verwijzen naar een geschikte UNIQUE-sleutel of primaire sleutel in dezelfde of een andere tabel.

Wat is een topologische volgorde, en hoe vindt het algoritme van Kahn er een?

In een DAG staat voor elke kant u→v de knoop u vóór v. Neem herhaaldelijk een knoop met ingraad nul op in de uitvoer en verwijder zijn uitgaande kanten; voeg nieuwe knopen met ingraad nul aan de wachtrij toe. Bevat de uitvoer minder dan V knopen, dan bevat de gerichte graaf een cyclus.

Hoe werkt standaard merge sort voor arrays, en wat zijn de tijd- en ruimtegrenzen?

Het sorteert recursief twee helften en voegt ze in lineaire tijd samen. De standaardversie kost Θ(n log n) tijd en O(n) extra ruimte, bij vergelijkingen in constante tijd.

Wanneer kunnen counting sort of radix sort in lineaire tijd werken?

Counting sort kost O(n+k) voor n sleutels uit een bereik van k waarden. Radix sort met d stabiele cijferpasses en grondtal b kost O(d(n+b)). Ze zijn alleen lineair als deze parameters dat toelaten; ze gebruiken sleutelstructuur naast vergelijkingen.

Hoe verschillen geclusterde en niet-geclusterde rowstore-indexen in SQL Server?

Een geclusterde index slaat tabelrijen op in sleutelvolgorde, dus een tabel heeft er hoogstens één. Een niet-geclusterde index heeft eigen sleutels en rijverwijzingen en kan andere kolommen bevatten. Termen en opslagdetails verschillen tussen databasesystemen.

Hoe werkt insertion sort, en wat bepaalt de looptijd bij bijna gesorteerde invoer?

Elk item wordt in een gesorteerd voorste deel ingevoegd. De gebruikelijke versie met verschuivingen of verwisselingen van buren kost Θ(n+I) tijd, waarbij I het aantal inversies is. Bij I=O(n) is dit lineair; kleine invoer op zichzelf verandert de slechtste-gevalgrens Θ(n²) niet.

Hoe kan diepte-eerst zoeken een cyclus in een gerichte graaf detecteren?

DFS verkent diep via recursie of een expliciete stapel. Een kant naar een knoop die nog actief is op het huidige DFS-pad is een terugkant en bewijst een gerichte cyclus; een kant naar een willekeurige eerder bezochte knoop volstaat niet.

Wat zijn de twee fasen van tweefasenvergrendeling, 2PL?

Groeifase: vergrendelingen verkrijgen zonder er vrij te geven. Krimpfase: vergrendelingen vrijgeven zonder nieuwe te verkrijgen. Met passende conflicterende lees- en schrijfvergrendelingen garandeert 2PL conflictserialiseerbare schema’s, maar deadlocks blijven mogelijk.

Wat is de standaardrecurrentie voor het 0/1-rugzakprobleem met gehele capaciteit W?

Laat D[i,w] de beste waarde zijn met de eerste i items en capaciteit w, met positieve gehele gewichten wᵢ. Stel D[0,w]=0. Als wᵢ>w, neem D[i−1,w] over; anders neem max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). De tijd O(NW) is pseudopolynomiaal.

Hoe verschilt een gulzig algoritme van dynamisch programmeren?

Een gulzig algoritme legt zich vast op een lokale keuze; er is een bewijs nodig dat zulke keuzes een optimum behouden. DP vergelijkt alternatieven via een recurrentie en hergebruikt deelresultaten. Een globaal optimum vereist een correct model en correcte recurrentie, niet alleen het label “DP”.

Wat is een vereenvoudigde logische verwerkingsvolgorde van een SQL SELECT-query?

Voor een query zonder CTE’s, vensterfuncties of verzamelingsbewerkingen: FROM/JOIN → WHERE → GROUP BY en aggregaten → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Dit is een logisch model, niet noodzakelijk de fysieke uitvoeringsvolgorde van de optimizer.

Wat vereist binair zoeken, en wanneer kost het O(log n) tijd?

Het halveert herhaaldelijk een zoekinterval in gegevens die volgens de vergelijkingsvolgorde gesorteerd zijn. In een array met O(1)-toegang via een index en vergelijkingen in constante tijd kost zoeken in n elementen O(log n) tijd.

Hoe vindt breedte-eerst zoeken kortste paden in een ongewogen graaf?

BFS gebruikt een FIFO-wachtrij en verkent knopen op afstand in aantal kanten. Een knoop markeren bij het toevoegen aan de wachtrij voorkomt herhaalde bezoeken. Het eerst gevonden pad naar een bereikbare knoop heeft het kleinste aantal kanten.

Hoe verschillen INNER JOIN en LEFT JOIN?

INNER JOIN geeft rijcombinaties terug die aan de joinvoorwaarde voldoen. LEFT JOIN behoudt ook elke niet-gematchte linkerrij en vult de rechterkolommen met NULL. Meerdere passende rechterrijen kunnen voor één linkerrij meerdere uitvoerrijen opleveren.

Wat betekenen de ACID-eigenschappen van transacties?

Atomiciteit: alles-of-niets-effecten. Consistentie: correcte transacties behouden beperkingen en applicatie-invarianten. Isolatie: gelijktijdig gedrag voldoet aan het gekozen isolatieniveau. Duurzaamheid: vastgelegde effecten overleven storingen die onder de ingestelde databasegaranties vallen.

Wat vereisen de eerste, tweede en derde normaalvorm?

1NF: atomaire attribuutwaarden. 2NF: 1NF en geen niet-priem attribuut hangt af van een echt deel van enige kandidaatsleutel. 3NF: 1NF en bij elke niet-triviale afhankelijkheid X→A is X een supersleutel of A priem. Een priem attribuut behoort tot minstens één kandidaatsleutel.

Waarom zijn B+-bomen nuttig voor database-indexen en bereikquery’s?

Hun grote vertakkingsfactor houdt bomen ondiep, waardoor minder paginatoegangen nodig zijn. Geordende sleutels en gekoppelde bladeren ondersteunen bereikscans. Hashindexen zijn gericht op gelijkheidszoekacties en bieden niet vanzelf dezelfde geordende bereiktoegang.

Waarom is dynamisch programmeren nuttig bij veel optimalisatieproblemen?

Optimale deelstructuur maakt het mogelijk een optimum uit te drukken via optima van deelproblemen. Bij overlappende deelproblemen voorkomt het bewaren van antwoorden herhaald werk. Toestanden en recurrentie moeten het oorspronkelijke probleem correct weergeven.

Wat zijn de tijdsgrens in het slechtste geval en de extra ruimte van in-place heapsort?

Een heap bouwen kost O(n), gevolgd door in totaal O(n log n) werk voor extracties. Met iteratief omlaag herstellen in de invoerarray kost heapsort in het slechtste geval O(n log n) tijd en O(1) extra ruimte.

Hoe verschillen memoïsatie en dynamisch programmeren van onderaf?

Memoïsatie berekent deelproblemen op aanvraag, meestal recursief, en bewaart resultaten. DP van onderaf berekent toestanden in een volgorde waarin hun afhankelijkheden al beschikbaar zijn, meestal door een tabel te vullen.

Wat is de DP-recurrentie voor de lengte van een langste gemeenschappelijke deelsequentie, LCS?

Laat L[i,j] de LCS-lengte van voorvoegsels met lengtes i,j zijn. Stel L[0,j]=L[i,0]=0. Bij gelijke laatste tekens geldt L[i,j]=1+L[i−1,j−1]; anders L[i,j]=max(L[i−1,j],L[i,j−1]). De volledige tabel kost O(mn) tijd en ruimte.

Wat maakt een sorteeralgoritme stabiel?

Items met gelijke sleutels behouden hun oorspronkelijke onderlinge volgorde. Merge sort kan stabiel zijn door bij gelijkheid eerst het linker item te nemen; standaard quicksort dat in dezelfde array werkt is doorgaans instabiel. Stabiliteit hangt af van de implementatie.

Wanneer is Dijkstra’s algoritme geldig, en wat is een gebruikelijke grens met een heap?

Bij niet-negatieve kantgewichten legt het telkens de knoop met de kleinste voorlopige afstand definitief vast. Een implementatie met adjacentielijsten en een binaire min-heap kost O((V+E) log V). Negatieve kanten kunnen de redenering achter definitieve afstanden ongeldig maken.

Wat is een phantom read, en hoe wordt die voorkomen?

Een herhaalde query met hetzelfde predicaat vindt een andere verzameling passende rijen nadat een andere transactie wijzigingen vastlegt. SERIALIZABLE voorkomt dit in het standaardmodel; sommige implementaties, waaronder PostgreSQL REPEATABLE READ, doen dit ook op een lager niveau.

Hoe verschillen WHERE en HAVING in een gegroepeerde query?

WHERE filtert invoerrijen vóór het groeperen. HAVING filtert de resulterende groepen en kan aggregatievoorwaarden gebruiken, zoals COUNT(*)>1.

Waarom kan quicksort Θ(n²) tijd kosten, en hoe helpt randomisatie?

Herhaaldelijk sterk ongelijke partities, bijvoorbeeld telkens de kleinste sleutel kiezen bij onderling verschillende sleutels, veroorzaken kwadratisch werk. Met verschillende sleutels of geschikte verwerking van duplicaten geven willekeurige pivots een verwachte tijd van O(n log n). Mediaan-van-drie is een nuttige heuristiek, geen garantie voor het slechtste geval.

Hoe ondersteunt PostgreSQL WAL duurzaamheid bij gewone synchrone commit?

Relevante logrecords bereiken duurzame opslag vóór de commit wordt bevestigd en vóór gewijzigde gegevenspagina’s worden geschreven. Na een crash kan WAL ontbrekende wijzigingen in gegevenspagina’s opnieuw uitvoeren. Bij asynchrone commit kunnen recent bevestigde transacties verloren gaan.

Wat is een dirty read, en welk standaardisolatieniveau voorkomt die als eerste?

Het lezen van niet-vastgelegde gegevens van een andere transactie, ongeacht of die later wordt teruggedraaid. READ COMMITTED en sterkere standaardisolatieniveaus verbieden dirty reads.

Hoe verhouden een adjacentiematrix en gewone adjacentielijsten zich tot elkaar?

Voor V knopen en E kanten gebruikt een matrix O(V²) ruimte en test die een kant in O(1). Lijsten gebruiken O(V+E) ruimte; in een ongesorteerde lijst zoeken naar kant (u,v) kost O(deg(u)), waarbij deg(u) de lengte van die lijst is.

Algoritmen, grafen, dynamisch programmeren en relationele databases

32 herhalingskaarten op universitair niveau over sorteren, graafalgoritmen, dynamisch programmeren, SQL, indexen en transacties. Veronderstelt basiskennis van programmeren, gegevensstructuren en SQL.

Level: basic
Languages: nl → nl
Cards: 32
Markdown: Algoritmen, grafen, dynamisch programmeren en relationele databases (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Hoe bouwen Kruskals en Prims algoritmen een minimale opspannende boom?	Voor een samenhangende, ongerichte, gewogen graaf bekijkt Kruskal kanten in oplopend gewicht en gebruikt Union–Find om cycli te verwerpen. Prim breidt één boom uit door steeds een kant met minimaal gewicht te kiezen die de boom met een knoop erbuiten verbindt.
2	Hoe verwerkt Bellman–Ford negatieve kanten en detecteert het een bereikbare negatieve cyclus?	Relaxeer alle kanten maximaal V−1 keer. Een verdere verbetering vanuit een bereikbare knoop onthult een negatieve cyclus die vanuit de bron bereikbaar is. De slechtste-gevaltijd is O(VE); knopen die vanuit zo’n cyclus bereikbaar zijn hebben geen eindige kortste-padkosten.
3	Wat is een nonrepeatable read, en welk standaardisolatieniveau voorkomt die?	Bij het opnieuw lezen van een rij zijn gegevens veranderd of is de rij verdwenen nadat een andere transactie een wijziging of verwijdering heeft vastgelegd. REPEATABLE READ en SERIALIZABLE verbieden deze anomalie.
4	Hoe verschillen primaire en vreemde sleutels in PostgreSQL?	Een primaire sleutel identificeert rijen met unieke waarden die niet NULL zijn. Een vreemde sleutel vereist overeenkomende waarden in de verwezen sleutel, volgens de bijbehorende NULL-regels. Hij kan verwijzen naar een geschikte UNIQUE-sleutel of primaire sleutel in dezelfde of een andere tabel.
5	Wat is een topologische volgorde, en hoe vindt het algoritme van Kahn er een?	In een DAG staat voor elke kant u→v de knoop u vóór v. Neem herhaaldelijk een knoop met ingraad nul op in de uitvoer en verwijder zijn uitgaande kanten; voeg nieuwe knopen met ingraad nul aan de wachtrij toe. Bevat de uitvoer minder dan V knopen, dan bevat de gerichte graaf een cyclus.
6	Hoe werkt standaard merge sort voor arrays, en wat zijn de tijd- en ruimtegrenzen?	Het sorteert recursief twee helften en voegt ze in lineaire tijd samen. De standaardversie kost Θ(n log n) tijd en O(n) extra ruimte, bij vergelijkingen in constante tijd.
7	Wanneer kunnen counting sort of radix sort in lineaire tijd werken?	Counting sort kost O(n+k) voor n sleutels uit een bereik van k waarden. Radix sort met d stabiele cijferpasses en grondtal b kost O(d(n+b)). Ze zijn alleen lineair als deze parameters dat toelaten; ze gebruiken sleutelstructuur naast vergelijkingen.
8	Hoe verschillen geclusterde en niet-geclusterde rowstore-indexen in SQL Server?	Een geclusterde index slaat tabelrijen op in sleutelvolgorde, dus een tabel heeft er hoogstens één. Een niet-geclusterde index heeft eigen sleutels en rijverwijzingen en kan andere kolommen bevatten. Termen en opslagdetails verschillen tussen databasesystemen.
9	Hoe werkt insertion sort, en wat bepaalt de looptijd bij bijna gesorteerde invoer?	Elk item wordt in een gesorteerd voorste deel ingevoegd. De gebruikelijke versie met verschuivingen of verwisselingen van buren kost Θ(n+I) tijd, waarbij I het aantal inversies is. Bij I=O(n) is dit lineair; kleine invoer op zichzelf verandert de slechtste-gevalgrens Θ(n²) niet.
10	Hoe kan diepte-eerst zoeken een cyclus in een gerichte graaf detecteren?	DFS verkent diep via recursie of een expliciete stapel. Een kant naar een knoop die nog actief is op het huidige DFS-pad is een terugkant en bewijst een gerichte cyclus; een kant naar een willekeurige eerder bezochte knoop volstaat niet.
11	Wat zijn de twee fasen van tweefasenvergrendeling, 2PL?	Groeifase: vergrendelingen verkrijgen zonder er vrij te geven. Krimpfase: vergrendelingen vrijgeven zonder nieuwe te verkrijgen. Met passende conflicterende lees- en schrijfvergrendelingen garandeert 2PL conflictserialiseerbare schema’s, maar deadlocks blijven mogelijk.
12	Wat is de standaardrecurrentie voor het 0/1-rugzakprobleem met gehele capaciteit W?	Laat D[i,w] de beste waarde zijn met de eerste i items en capaciteit w, met positieve gehele gewichten wᵢ. Stel D[0,w]=0. Als wᵢ>w, neem D[i−1,w] over; anders neem max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). De tijd O(NW) is pseudopolynomiaal.
13	Hoe verschilt een gulzig algoritme van dynamisch programmeren?	Een gulzig algoritme legt zich vast op een lokale keuze; er is een bewijs nodig dat zulke keuzes een optimum behouden. DP vergelijkt alternatieven via een recurrentie en hergebruikt deelresultaten. Een globaal optimum vereist een correct model en correcte recurrentie, niet alleen het label “DP”.
14	Wat is een vereenvoudigde logische verwerkingsvolgorde van een SQL SELECT-query?	Voor een query zonder CTE’s, vensterfuncties of verzamelingsbewerkingen: FROM/JOIN → WHERE → GROUP BY en aggregaten → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Dit is een logisch model, niet noodzakelijk de fysieke uitvoeringsvolgorde van de optimizer.
15	Wat vereist binair zoeken, en wanneer kost het O(log n) tijd?	Het halveert herhaaldelijk een zoekinterval in gegevens die volgens de vergelijkingsvolgorde gesorteerd zijn. In een array met O(1)-toegang via een index en vergelijkingen in constante tijd kost zoeken in n elementen O(log n) tijd.
16	Hoe vindt breedte-eerst zoeken kortste paden in een ongewogen graaf?	BFS gebruikt een FIFO-wachtrij en verkent knopen op afstand in aantal kanten. Een knoop markeren bij het toevoegen aan de wachtrij voorkomt herhaalde bezoeken. Het eerst gevonden pad naar een bereikbare knoop heeft het kleinste aantal kanten.
17	Hoe verschillen INNER JOIN en LEFT JOIN?	INNER JOIN geeft rijcombinaties terug die aan de joinvoorwaarde voldoen. LEFT JOIN behoudt ook elke niet-gematchte linkerrij en vult de rechterkolommen met NULL. Meerdere passende rechterrijen kunnen voor één linkerrij meerdere uitvoerrijen opleveren.
18	Wat betekenen de ACID-eigenschappen van transacties?	Atomiciteit: alles-of-niets-effecten. Consistentie: correcte transacties behouden beperkingen en applicatie-invarianten. Isolatie: gelijktijdig gedrag voldoet aan het gekozen isolatieniveau. Duurzaamheid: vastgelegde effecten overleven storingen die onder de ingestelde databasegaranties vallen.
19	Wat vereisen de eerste, tweede en derde normaalvorm?	1NF: atomaire attribuutwaarden. 2NF: 1NF en geen niet-priem attribuut hangt af van een echt deel van enige kandidaatsleutel. 3NF: 1NF en bij elke niet-triviale afhankelijkheid X→A is X een supersleutel of A priem. Een priem attribuut behoort tot minstens één kandidaatsleutel.
20	Waarom zijn B+-bomen nuttig voor database-indexen en bereikquery’s?	Hun grote vertakkingsfactor houdt bomen ondiep, waardoor minder paginatoegangen nodig zijn. Geordende sleutels en gekoppelde bladeren ondersteunen bereikscans. Hashindexen zijn gericht op gelijkheidszoekacties en bieden niet vanzelf dezelfde geordende bereiktoegang.
21	Waarom is dynamisch programmeren nuttig bij veel optimalisatieproblemen?	Optimale deelstructuur maakt het mogelijk een optimum uit te drukken via optima van deelproblemen. Bij overlappende deelproblemen voorkomt het bewaren van antwoorden herhaald werk. Toestanden en recurrentie moeten het oorspronkelijke probleem correct weergeven.
22	Wat zijn de tijdsgrens in het slechtste geval en de extra ruimte van in-place heapsort?	Een heap bouwen kost O(n), gevolgd door in totaal O(n log n) werk voor extracties. Met iteratief omlaag herstellen in de invoerarray kost heapsort in het slechtste geval O(n log n) tijd en O(1) extra ruimte.
23	Hoe verschillen memoïsatie en dynamisch programmeren van onderaf?	Memoïsatie berekent deelproblemen op aanvraag, meestal recursief, en bewaart resultaten. DP van onderaf berekent toestanden in een volgorde waarin hun afhankelijkheden al beschikbaar zijn, meestal door een tabel te vullen.
24	Wat is de DP-recurrentie voor de lengte van een langste gemeenschappelijke deelsequentie, LCS?	Laat L[i,j] de LCS-lengte van voorvoegsels met lengtes i,j zijn. Stel L[0,j]=L[i,0]=0. Bij gelijke laatste tekens geldt L[i,j]=1+L[i−1,j−1]; anders L[i,j]=max(L[i−1,j],L[i,j−1]). De volledige tabel kost O(mn) tijd en ruimte.
25	Wat maakt een sorteeralgoritme stabiel?	Items met gelijke sleutels behouden hun oorspronkelijke onderlinge volgorde. Merge sort kan stabiel zijn door bij gelijkheid eerst het linker item te nemen; standaard quicksort dat in dezelfde array werkt is doorgaans instabiel. Stabiliteit hangt af van de implementatie.
26	Wanneer is Dijkstra’s algoritme geldig, en wat is een gebruikelijke grens met een heap?	Bij niet-negatieve kantgewichten legt het telkens de knoop met de kleinste voorlopige afstand definitief vast. Een implementatie met adjacentielijsten en een binaire min-heap kost O((V+E) log V). Negatieve kanten kunnen de redenering achter definitieve afstanden ongeldig maken.
27	Wat is een phantom read, en hoe wordt die voorkomen?	Een herhaalde query met hetzelfde predicaat vindt een andere verzameling passende rijen nadat een andere transactie wijzigingen vastlegt. SERIALIZABLE voorkomt dit in het standaardmodel; sommige implementaties, waaronder PostgreSQL REPEATABLE READ, doen dit ook op een lager niveau.
28	Hoe verschillen WHERE en HAVING in een gegroepeerde query?	WHERE filtert invoerrijen vóór het groeperen. HAVING filtert de resulterende groepen en kan aggregatievoorwaarden gebruiken, zoals COUNT(*)>1.
29	Waarom kan quicksort Θ(n²) tijd kosten, en hoe helpt randomisatie?	Herhaaldelijk sterk ongelijke partities, bijvoorbeeld telkens de kleinste sleutel kiezen bij onderling verschillende sleutels, veroorzaken kwadratisch werk. Met verschillende sleutels of geschikte verwerking van duplicaten geven willekeurige pivots een verwachte tijd van O(n log n). Mediaan-van-drie is een nuttige heuristiek, geen garantie voor het slechtste geval.
30	Hoe ondersteunt PostgreSQL WAL duurzaamheid bij gewone synchrone commit?	Relevante logrecords bereiken duurzame opslag vóór de commit wordt bevestigd en vóór gewijzigde gegevenspagina’s worden geschreven. Na een crash kan WAL ontbrekende wijzigingen in gegevenspagina’s opnieuw uitvoeren. Bij asynchrone commit kunnen recent bevestigde transacties verloren gaan.
31	Wat is een dirty read, en welk standaardisolatieniveau voorkomt die als eerste?	Het lezen van niet-vastgelegde gegevens van een andere transactie, ongeacht of die later wordt teruggedraaid. READ COMMITTED en sterkere standaardisolatieniveaus verbieden dirty reads.
32	Hoe verhouden een adjacentiematrix en gewone adjacentielijsten zich tot elkaar?	Voor V knopen en E kanten gebruikt een matrix O(V²) ruimte en test die een kant in O(1). Lijsten gebruiken O(V+E) ruimte; in een ongesorteerde lijst zoeken naar kant (u,v) kost O(deg(u)), waarbij deg(u) de lengte van die lijst is.