Algorytmy, grafy, programowanie dynamiczne i relacyjne bazy danych
32 fiszki na poziomie studiów o sortowaniu, algorytmach grafowych, programowaniu dynamicznym, SQL, indeksach i transakcjach. Zakłada znajomość podstaw programowania, struktur danych i SQL.
- Category
- Computer Science
- Level
- basic
- Languages
- pl → pl
- Cards
- 32
- Markdown
- Algorytmy, grafy, programowanie dynamiczne i relacyjne bazy danych (.md)
Flashcards (32)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | Czym różnią się klucze główne i obce w PostgreSQL? | Klucz główny identyfikuje wiersze unikatowymi wartościami innymi niż NULL. Klucz obcy wymaga dopasowania do wartości wskazanego klucza z uwzględnieniem zasad NULL. Może wskazywać odpowiedni klucz UNIQUE lub główny w tej samej albo innej tabeli. | ||
| 2 | Czym jest odczyt fantomowy i jak się mu zapobiega? | Powtórzone zapytanie z predykatem znajduje inny zbiór pasujących wierszy po zatwierdzeniu zmian przez inną transakcję. SERIALIZABLE zapobiega fantomom w modelu standardowym; niektóre implementacje, w tym PostgreSQL REPEATABLE READ, zapobiegają im także na niższym poziomie. | ||
| 3 | Czym różnią się indeksy klastrowane i nieklastrowane dla magazynu wierszowego w SQL Server? | Indeks klastrowany przechowuje wiersze tabeli w porządku klucza, więc tabela może mieć najwyżej jeden. Nieklastrowany ma własne klucze i lokalizatory wierszy oraz może zawierać inne kolumny. Terminologia i szczegóły przechowywania różnią się między systemami baz danych. | ||
| 4 | Jaka jest uproszczona logiczna kolejność przetwarzania zapytania SQL SELECT? | Dla zapytania bez CTE, funkcji okienkowych i operacji na zbiorach: FROM/JOIN → WHERE → GROUP BY i agregaty → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. To model logiczny, niekoniecznie fizyczna kolejność wykonania wybrana przez optymalizator. | ||
| 5 | Czym algorytm zachłanny różni się od programowania dynamicznego? | Zachłanny nieodwracalnie wybiera lokalną opcję i wymaga dowodu, że takie wybory zachowują optimum. DP porównuje alternatywy przez rekurencję i wykorzystuje wyniki podproblemów ponownie. Globalne optimum wymaga poprawnego modelu i rekurencji, a nie samej nazwy „DP”. | ||
| 6 | Co sprawia, że algorytm sortowania jest stabilny? | Elementy o równych kluczach zachowują pierwotną kolejność względem siebie. Sortowanie przez scalanie może być stabilne, jeśli przy równości najpierw wybiera lewy element; standardowy quicksort w miejscu zwykle nie jest stabilny. Stabilność zależy od implementacji. | ||
| 7 | Jak przeszukiwanie wszerz znajduje najkrótsze ścieżki w grafie nieważonym? | BFS używa kolejki FIFO i odwiedza wierzchołki według odległości mierzonej liczbą krawędzi. Oznaczenie wierzchołka przy dodaniu do kolejki zapobiega powtórnym odwiedzinom. Pierwsza odkryta ścieżka do osiągalnego wierzchołka ma najmniej krawędzi. | ||
| 8 | Czym jest porządek topologiczny i jak znajduje go algorytm Kahna? | W DAG każda krawędź u→v wymaga umieszczenia u przed v. Kolejno wypisujemy wierzchołek o zerowym stopniu wejściowym i usuwamy jego krawędzie wychodzące, dodając do kolejki nowe wierzchołki o zerowym stopniu wejściowym. Jeśli wypisano mniej niż V wierzchołków, graf skierowany zawiera cykl. | ||
| 9 | Jak algorytmy Kruskala i Prima budują minimalne drzewo rozpinające? | Dla spójnego nieskierowanego grafu ważonego Kruskal rozpatruje krawędzie rosnąco według wagi i używa Union–Find do odrzucania cykli. Prim rozbudowuje jedno drzewo, wybierając za każdym razem krawędź o najmniejszej wadze między drzewem a wierzchołkiem poza nim. | ||
| 10 | Jakie są najgorsze koszty czasu i dodatkowej pamięci sortowania przez kopcowanie w miejscu? | Budowa kopca trwa O(n), a wszystkie usunięcia łącznie O(n log n). Przy iteracyjnym przesiewaniu w dół w tablicy wejściowej sortowanie zajmuje O(n log n) czasu w najgorszym przypadku i O(1) dodatkowej pamięci. | ||
| 11 | Jakie są dwie fazy blokowania dwufazowego (2PL)? | Wzrost: uzyskiwanie blokad bez zwalniania. Kurczenie: zwalnianie bez uzyskiwania nowych. Przy odpowiednich konfliktujących blokadach odczytu i zapisu 2PL gwarantuje harmonogramy szeregowalne względem konfliktów, lecz zakleszczenia nadal są możliwe. | ||
| 12 | Czym różnią się INNER JOIN i LEFT JOIN? | INNER JOIN zwraca kombinacje wierszy spełniające warunek złączenia. LEFT JOIN zachowuje też każdy niedopasowany lewy wiersz, uzupełniając prawe kolumny wartościami NULL. Kilka pasujących prawych wierszy może dać kilka wyników dla jednego lewego. | ||
| 13 | Dlaczego quicksort może zajmować Θ(n²) czasu i jak pomaga losowość? | Powtarzające się bardzo nierówne podziały, np. każdorazowy wybór najmniejszego spośród różnych kluczy, powodują pracę kwadratową. Dla różnych kluczy lub przy odpowiedniej obsłudze duplikatów losowe pivoty dają oczekiwany czas O(n log n). Mediana trzech jest użyteczną heurystyką, a nie gwarancją dla najgorszego przypadku. | ||
| 14 | Jaka jest standardowa rekurencja problemu plecakowego 0/1 dla całkowitej pojemności W? | Niech D[i,w] oznacza największą wartość z pierwszych i przedmiotów przy pojemności w i dodatnich całkowitych wagach wᵢ. Przyjmij D[0,w]=0. Jeśli wᵢ>w, skopiuj D[i−1,w]; w przeciwnym razie wybierz max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Czas O(NW) jest pseudowielomianowy. | ||
| 15 | Jak działa sortowanie przez wstawianie i od czego zależy czas dla niemal uporządkowanych danych? | Wstawia każdy element do uporządkowanego prefiksu. Zwykła wersja przesuwająca lub zamieniająca sąsiednie elementy zajmuje Θ(n+I), gdzie I to liczba inwersji. Jest liniowa, gdy I=O(n); sam mały rozmiar danych nie zmienia najgorszej granicy Θ(n²). | ||
| 16 | Czego wymagają pierwsza, druga i trzecia postać normalna? | 1NF: atomowych wartości atrybutów. 2NF: 1NF oraz braku zależności atrybutu niekluczowego od właściwego podzbioru atrybutów dowolnego klucza kandydującego. 3NF: 1NF, a dla każdej nietrywialnej zależności X→A — X jest nadkluczem lub A należy do jakiegoś klucza kandydującego. Atrybut niekluczowy nie należy do żadnego klucza kandydującego. | ||
| 17 | Czym jest brudny odczyt i jaki standardowy poziom izolacji jako pierwszy mu zapobiega? | To odczyt niezatwierdzonych danych innej transakcji, niezależnie od tego, czy zostanie ona później wycofana. READ COMMITTED i silniejsze standardowe poziomy izolacji zabraniają brudnych odczytów. | ||
| 18 | Jak WAL w PostgreSQL wspiera trwałość przy zwykłym synchronicznym zatwierdzaniu? | Odpowiednie rekordy dziennika trafiają do trwałego nośnika przed potwierdzeniem zatwierdzenia i przed zapisem zmienionych stron danych. Po awarii WAL może odtworzyć zmiany brakujące na stronach. Asynchroniczne zatwierdzanie może utracić ostatnio potwierdzone transakcje. | ||
| 19 | Czego wymaga wyszukiwanie binarne i kiedy działa w czasie O(log n)? | Wielokrotnie dzieli na pół przedział wyszukiwania w danych uporządkowanych zgodnie z porównaniem. W tablicy z dostępem indeksowym O(1) i porównaniami o stałym koszcie wyszukanie wśród n elementów zajmuje O(log n). | ||
| 20 | Dlaczego programowanie dynamiczne pomaga w wielu zadaniach optymalizacji? | Optymalna podstruktura pozwala wyrazić optimum przez optima podproblemów. Gdy podproblemy się powtarzają, przechowywanie wyników eliminuje ponowną pracę. Definicje stanów i rekurencja muszą poprawnie odzwierciedlać problem pierwotny. | ||
| 21 | Kiedy sortowanie przez zliczanie lub pozycyjne może działać liniowo? | Zliczanie kosztuje O(n+k) dla n kluczy z zakresu k wartości. Sortowanie pozycyjne z d stabilnymi przebiegami po cyfrach i podstawą b kosztuje O(d(n+b)). Liniowość zachodzi tylko przy odpowiednich parametrach; algorytmy wykorzystują strukturę kluczy poza samymi porównaniami. | ||
| 22 | Jak działa standardowe sortowanie tablicy przez scalanie i jakie ma koszty czasu oraz pamięci? | Rekurencyjnie sortuje dwie połowy, a następnie scala je w czasie liniowym. Standardowa wersja zajmuje Θ(n log n) czasu i O(n) pamięci pomocniczej, przy porównaniach o stałym koszcie. | ||
| 23 | Kiedy algorytm Dijkstry jest poprawny i jaki jest typowy koszt wersji z kopcem? | Przy nieujemnych wagach krawędzi kolejno ustala wierzchołek o najmniejszej tymczasowej odległości. Implementacja z listami sąsiedztwa i binarnym kopcem minimum kosztuje O((V+E) log V). Ujemne krawędzie mogą unieważnić argument o ostateczności ustalonej odległości. | ||
| 24 | Jak przeszukiwanie w głąb wykrywa cykl w grafie skierowanym? | DFS zagłębia się, używając rekurencji lub jawnego stosu. Krawędź do wierzchołka wciąż aktywnego na bieżącej ścieżce DFS jest krawędzią wsteczną i dowodzi istnienia cyklu skierowanego; krawędź do dowolnego wcześniej odwiedzonego wierzchołka nie wystarcza. | ||
| 25 | Jak Bellman–Ford obsługuje ujemne krawędzie i wykrywa osiągalny cykl o ujemnej wadze? | Relaksuje wszystkie krawędzie do V−1 razy. Dalsza poprawa z osiągalnego wierzchołka ujawnia ujemny cykl osiągalny ze źródła. Najgorszy czas to O(VE); dla wierzchołków osiągalnych z takiego cyklu nie ma skończonego kosztu najkrótszej ścieżki. | ||
| 26 | Czym jest niepowtarzalny odczyt i jaki standardowy poziom izolacji mu zapobiega? | Ponowny odczyt wiersza daje zmienione dane albo wiersz znika po zatwierdzeniu aktualizacji lub usunięcia przez inną transakcję. REPEATABLE READ i SERIALIZABLE zabraniają tej anomalii. | ||
| 27 | Dlaczego B+ drzewa nadają się do indeksów baz danych i zapytań zakresowych? | Duża liczba potomków utrzymuje niewielką wysokość drzewa i ogranicza odwołania do stron. Uporządkowane klucze i połączone liście wspierają skanowanie zakresów. Indeksy haszujące służą do wyszukiwania po równości i same nie zapewniają takiego uporządkowanego dostępu do zakresu. | ||
| 28 | Czym różnią się WHERE i HAVING w zapytaniu grupującym? | WHERE filtruje wiersze wejściowe przed grupowaniem. HAVING filtruje powstałe grupy i może używać warunków agregujących, np. COUNT(*)>1. | ||
| 29 | Co oznaczają własności transakcji ACID? | Atomowość: wszystkie skutki albo żadne. Spójność: poprawne transakcje zachowują ograniczenia i niezmienniki aplikacji. Izolacja: współbieżność podlega wybranemu poziomowi izolacji. Trwałość: zatwierdzone skutki przetrwają awarie objęte skonfigurowanymi gwarancjami bazy. | ||
| 30 | Czym różnią się memoizacja i programowanie dynamiczne od dołu? | Memoizacja oblicza podproblemy na żądanie, zwykle rekurencyjnie, i zapisuje wyniki. Podejście od dołu oblicza stany w kolejności, w której potrzebne zależności są już dostępne, zwykle wypełniając tabelę. | ||
| 31 | Jak porównać macierz sąsiedztwa ze zwykłymi listami sąsiedztwa? | Dla V wierzchołków i E krawędzi macierz zajmuje O(V²) pamięci i sprawdza krawędź w O(1). Listy zajmują O(V+E); szukanie krawędzi (u,v) na nieuporządkowanej liście trwa O(deg(u)), gdzie deg(u) jest długością tej listy. | ||
| 32 | Jaka jest rekurencja dynamiczna dla długości najdłuższego wspólnego podciągu (LCS)? | Niech L[i,j] będzie długością LCS prefiksów o długościach i,j. Ustal L[0,j]=L[i,0]=0. Jeśli ostatnie znaki są równe, L[i,j]=1+L[i−1,j−1]; inaczej L[i,j]=max(L[i−1,j],L[i,j−1]). Pełna tabela zajmuje O(mn) czasu i pamięci. |