# Algoritmer, grafer, dynamisk programmering och relationsdatabaser

> 32 repetitionskort på grundnivå vid universitet om sortering, grafalgoritmer, dynamisk programmering, SQL, index och transaktioner. Förutsätter grundläggande programmering, datastrukturer och SQL.

- **Canonical URL:** https://flashcards.world/flashcards/sets/111d4b6f-3f77-4b72-a4a7-faba37d2f872/
- **Markdown URL:** https://flashcards.world/flashcards/sets/111d4b6f-3f77-4b72-a4a7-faba37d2f872.md
- **Category:** Computer Science
- **Level:** basic
- **Languages:** sv → sv
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Hur skiljer sig memoisering från dynamisk programmering nedifrån och upp? | Memoisering beräknar delproblem vid behov, oftast rekursivt, och sparar resultaten. DP nedifrån och upp beräknar tillstånd i en ordning där deras beroenden redan är tillgängliga, oftast genom att fylla en tabell. |  |  |
| 2 | Hur skiljer sig primärnycklar och främmande nycklar i PostgreSQL? | En primärnyckel identifierar rader med unika värden som inte är NULL. En främmande nyckel kräver matchande refererade nyckelvärden enligt sina NULL-regler. Den kan referera till en lämplig UNIQUE-nyckel eller primärnyckel i samma eller en annan tabell. |  |  |
| 3 | Hur skiljer sig klustrade och icke-klustrade rowstore-index i SQL Server? | Ett klustrat index lagrar tabellrader i nyckelordning, så en tabell har högst ett. Ett icke-klustrat index har egna nycklar och radlokaliserare och kan innehålla andra kolumner. Termer och lagringsdetaljer varierar mellan databassystem. |  |  |
| 4 | Hur skiljer sig INNER JOIN och LEFT JOIN? | INNER JOIN returnerar radkombinationer som uppfyller kopplingsvillkoret. LEFT JOIN behåller också varje omatchad vänsterrad och fyller högerkolumnerna med NULL. Flera matchande högerrader kan ge flera utdatarader för en vänsterrad. |  |  |
| 5 | Vilken är standardrekursionen för 0/1-ryggsäcksproblemet med heltalskapacitet W? | Låt D[i,w] vara bästa värdet med de första i föremålen och kapacitet w, där vikterna wᵢ är positiva heltal. Sätt D[0,w]=0. Om wᵢ>w, kopiera D[i−1,w]; annars välj max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Tiden O(NW) är pseudopolynomiell. |  |  |
| 6 | Vad är en fantomläsning, och hur förhindras den? | En upprepad predikatfråga hittar en annan mängd matchande rader efter att en annan transaktion bekräftat ändringar. SERIALIZABLE förhindrar fantomer i standardmodellen; vissa implementationer, däribland PostgreSQL REPEATABLE READ, gör det även på en lägre nivå. |  |  |
| 7 | Hur stöder PostgreSQL WAL beständighet vid vanlig synkron commit? | Relevanta loggposter når beständig lagring innan commit bekräftas och innan ändrade datasidor skrivs. Efter en krasch kan WAL återspela ändringar som saknas i datasidorna. Asynkron commit kan förlora nyligen bekräftade transaktioner. |  |  |
| 8 | Hur skiljer sig WHERE och HAVING i en grupperad fråga? | WHERE filtrerar indatarader före grupperingen. HAVING filtrerar de resulterande grupperna och kan använda aggregatvillkor, som COUNT(*)>1. |  |  |
| 9 | Hur hanterar Bellman–Ford negativa kanter och upptäcker en nåbar negativ cykel? | Relaxera alla kanter upp till V−1 gånger. En ytterligare förbättring från ett nåbart hörn visar en negativ cykel som är nåbar från källan. Värstafallstiden är O(VE); hörn som kan nås från en sådan cykel saknar ändlig kortaste-väg-kostnad. |  |  |
| 10 | Hur skiljer sig en grannmatris från vanliga grannlistor? | För V hörn och E kanter använder en matris O(V²) utrymme och testar en kant i O(1). Listor använder O(V+E) utrymme; sökning efter kanten (u,v) i en osorterad lista tar O(deg(u)), där deg(u) är listans längd. |  |  |
| 11 | Hur skiljer sig en girig algoritm från dynamisk programmering? | En girig algoritm låser sig vid ett lokalt val och kräver bevis för att sådana val bevarar ett optimum. DP jämför alternativ via en rekursionsekvation och återanvänder delresultat. Ett globalt optimum kräver korrekt modell och rekursion, inte bara etiketten ”DP”. |  |  |
| 12 | Vad kräver första, andra och tredje normalformen? | 1NF: atomära attributvärden. 2NF: 1NF och inget icke-primattribut beror på en äkta del av någon kandidatnyckel. 3NF: 1NF och för varje icke-trivialt beroende X→A är X en supernyckel eller A ett primattribut. Ett primattribut ingår i någon kandidatnyckel. |  |  |
| 13 | Vad betyder transaktionsegenskaperna ACID? | Atomicitet: allt-eller-inget-effekter. Konsistens: korrekta transaktioner bevarar begränsningar och applikationsinvarianter. Isolering: samtidig körning följer vald isoleringsnivå. Beständighet: bekräftade effekter överlever fel som omfattas av databasens konfigurerade garantier. |  |  |
| 14 | Vad är en smutsig läsning, och vilken standardnivå för isolering förhindrar den först? | Att läsa en annan transaktions obekräftade data, oavsett om transaktionen senare rullas tillbaka. READ COMMITTED och starkare standardnivåer förbjuder smutsiga läsningar. |  |  |
| 15 | Hur konstruerar Kruskals och Prims algoritmer ett minimalt uppspännande träd? | För en sammanhängande, oriktad, viktad graf behandlar Kruskal kanter i stigande viktordning och använder Union–Find för att avvisa cykler. Prim bygger ett träd genom att upprepade gånger välja en kant med minsta vikt från trädet till ett hörn utanför det. |  |  |
| 16 | Vad kräver binärsökning, och när tar den O(log n) tid? | Den halverar upprepade gånger ett sökintervall i data som är sorterade enligt jämförelseordningen. I en array med O(1)-åtkomst via index och jämförelser i konstant tid tar sökning bland n element O(log n) tid. |  |  |
| 17 | Vad är en topologisk ordning, och hur hittar Kahns algoritm en sådan? | I en DAG placerar varje kant u→v hörnet u före v. Skriv upprepade gånger ut ett hörn med ingrad noll och ta bort dess utgående kanter; lägg nya hörn med ingrad noll i kön. Om färre än V hörn skrivs ut har den riktade grafen en cykel. |  |  |
| 18 | Varför är B+-träd användbara för databasindex och intervallfrågor? | Deras höga förgreningsgrad håller träden grunda och minskar sidåtkomster. Ordnade nycklar och länkade löv stöder intervallsökning. Hashindex är inriktade på likhetssökning och ger inte i sig samma ordnade intervallåtkomst. |  |  |
| 19 | Vad är en icke-repeterbar läsning, och vilken standardnivå för isolering förhindrar den? | När en rad läses igen har data ändrats, eller raden försvunnit, efter att en annan transaktion bekräftat en uppdatering eller radering. REPEATABLE READ och SERIALIZABLE förbjuder denna anomali. |  |  |
| 20 | Varför är dynamisk programmering användbar för många optimeringsproblem? | Optimal delstruktur gör att ett optimum kan uttryckas med delproblemens optimum. När delproblem överlappar undviker sparade svar upprepat arbete. Tillståndsdefinitioner och rekursionsekvation måste korrekt representera ursprungsproblemet. |  |  |
| 21 | Hur fungerar vanlig mergesort för arrayer, och vilka är tids- och utrymmesgränserna? | Den sorterar två halvor rekursivt och sammanfogar dem i linjär tid. Standardversionen tar Θ(n log n) tid och O(n) extra utrymme, om jämförelser tar konstant tid. |  |  |
| 22 | Varför kan quicksort ta Θ(n²) tid, och hur hjälper slumpmässighet? | Upprepade mycket ojämna uppdelningar, som att alltid välja den minsta distinkta nyckeln, ger kvadratiskt arbete. Med distinkta nycklar eller lämplig hantering av dubbletter ger slumpade pivoter förväntad O(n log n) tid. Median-av-tre är en användbar heuristik, ingen värstafallsgaranti. |  |  |
| 23 | Vilka är gränserna för värstafallstid och extra utrymme för heapsort på plats? | Att bygga en heap tar O(n), följt av totalt O(n log n) arbete för uttag. Med iterativ sift-down, som återställer heapen nedåt, i indataarrayen tar heapsort O(n log n) tid i värsta fall och O(1) extra utrymme. |  |  |
| 24 | Vilka är tvåfaslåsningens två faser, 2PL? | Växande: skaffa lås utan att släppa några. Krympande: släpp lås utan att skaffa nya. Med lämpliga konflikterande läs- och skrivlås garanterar 2PL konfliktserialiserbara scheman, men deadlock kan fortfarande uppstå. |  |  |
| 25 | Vilken är en förenklad logisk behandlingsordning för en SQL SELECT-fråga? | För en fråga utan CTE:er, fönsterfunktioner eller mängdoperationer: FROM/JOIN → WHERE → GROUP BY och aggregat → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Detta är en logisk modell, inte nödvändigtvis optimerarens fysiska körordning. |  |  |
| 26 | Hur hittar bredden-först-sökning kortaste vägar i en oviktad graf? | BFS använder en FIFO-kö och utforskar hörn efter avstånd räknat i kanter. Markering när ett hörn läggs i kön undviker upprepade besök. Den först upptäckta vägen till ett nåbart hörn har minsta möjliga antal kanter. |  |  |
| 27 | Hur fungerar insättningssortering, och vad avgör tiden för nästan sorterad indata? | Varje element sätts in i ett sorterat prefix. Den vanliga versionen med förskjutningar eller byten mellan grannar tar Θ(n+I) tid, där I är antalet inversioner. Den är linjär när I=O(n); liten indata i sig ändrar inte värstafallsgränsen Θ(n²). |  |  |
| 28 | Vad gör en sorteringsalgoritm stabil? | Element med lika nycklar behåller sin ursprungliga inbördes ordning. Mergesort kan vara stabil genom att välja vänstra elementet först vid lika nycklar; vanlig quicksort som arbetar på plats är oftast instabil. Stabiliteten beror på implementationen. |  |  |
| 29 | Hur kan djupet-först-sökning upptäcka en cykel i en riktad graf? | DFS går på djupet med rekursion eller en explicit stack. En kant till ett hörn som fortfarande är aktivt på den aktuella DFS-vägen är en bakåtkant och bevisar en riktad cykel; en kant till vilket tidigare besökt hörn som helst räcker inte. |  |  |
| 30 | När är Dijkstras algoritm giltig, och vilken gräns är vanlig med en heap? | Med icke-negativa kantvikter fastställer den upprepade gånger hörnet med minst preliminärt avstånd. En implementation med grannlistor och en binär min-heap tar O((V+E) log V). Negativa kanter kan kullkasta argumentet för fastställda avstånd. |  |  |
| 31 | När kan räkningssortering eller radixsortering gå i linjär tid? | Räkningssortering kostar O(n+k) för n nycklar i ett intervall med k värden. Radixsortering med d stabila sifferpass och bas b kostar O(d(n+b)). De är linjära endast när parametrarna tillåter det; de använder nyckelstruktur utöver jämförelser. |  |  |
| 32 | Vilken DP-rekursion ger längden av en längsta gemensam delsekvens, LCS? | Låt L[i,j] vara LCS-längden för prefix med längderna i,j. Sätt L[0,j]=L[i,0]=0. Om de sista tecknen är lika gäller L[i,j]=1+L[i−1,j−1]; annars L[i,j]=max(L[i−1,j],L[i,j−1]). Hela tabellen kräver O(mn) tid och utrymme. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/111d4b6f-3f77-4b72-a4a7-faba37d2f872/).
