Transcript
Krakow 20.12.2010
Zagadnienia do egzaminu pisemnego z Teoretycznych Podstaw Informatyki
1. Co to jest pozycyjny system zapisu liczb, wymie´ n znane ci przyklady?. 2. Om´ow, na czym polega system kodowania wielko´sci liczbowych: znak-modul, uzupelnieniowy, staloprzecinkowy, zmiennoprzecinkowy, cecha-mantysa. Kt´ory stosujemy dla wielko´sci liczbowych calkowitych, a kt´ory dla rzeczywistych i dlaczego. Czy ble‘ dy wzgle‘ dny i bezwzgle‘ dny sa‘ stale dla danego systemu kodowania? 3. Na czym polega wste‘ puja‘ce i zste‘ puja‘ce podej´scie do zagadnienia programistycznego? 4. Co to jest algorytm i jakie znasz sposoby jego zapisu? Zilustruj na przykladzie dowolnego prostego algorytmu. 5. Om´ow na czym polegaja‘ naste‘ puja‘ce typ´ow algorytm´ow: algorytm liniowy, algorytm z rozgale‘ zieniem, algorytm z powrotami, algorytm oparty na programowaniu dynamicznym, algorytm dziel i zwycie‘ z˙ aj, algorytm zachlanny. Wymie´ n znane ci wady/zalety poszczeg´olnych typ´ow oraz przyklad znanego ci zastosowania. 6. Co to jest zlo˙zono´s´c obliczeniowa ´srednia i zlo˙zono´s´c obliczeniowa asymptotyczna? Om´ow dla kilku wybranych przykladowych algorytm´ow. 7. Om´ow poje‘ cie notacji du˙ze O, Ω, Θ oraz znane ci wlasno´sci. Zilustruj na wybranych przykladach. 8. Co to jest algorytm iteracyjny, co to jest algorytm rekurencyjny. Podaj definicje‘ , oraz om´ow znane ci przyklady zastosowa´ n. Por´ownaj effektywno´s´c obu algorytm´ow na wybranym przykladzie. 9. Podaj przyklad algorytmu rekurencyjnego. Jak wygla‘da zale˙zno´s´c dla obliczania jego zlo˙zono´sci obliczeniowej? Narysuj drzewo rekursji dla tego algorytmu. 10. Jakie znasz metody rozwia‘zywania rekurencji (znajdowania zlo˙zono´sci obliczeniowej dla algorytmu rekurencyjnego)? Przedstaw na wybranym przykladzie. 11. Om´ow poje‘ cie (technike‘ ) indukcji zupelnej i cze‘ ´sciowej. Na czym polega dow´od indukcyjny? Podaj znany ci przyklad zastosowania. 12. Na czym polega process sortowania. Przedyskutuj zlo˙zono´s´c obliczeniowa‘ algorytmu sortowania przez wybieranie i algorytmu sortowania przez dzielenie i scalanie. 13. Om´ow rekurencyjny algorytm do wyznaczania liczby kombinacji. Om´ow znane Ci interesuja‘ce wlasno´sci tej funkcji. 14. Om´ow poje‘ cie modelu danych i struktury danych. Zilustruj na wybranym przykladzie. Co to sa‘ statyczne i dynamiczne elementy modelu danych. 1
15. Om´ow model danych je‘ zyka C. 16. Om´ow poje‘ cie modelu danych opartego na drzewach. Jakie znasz struktury danych kt´ore sa‘ u˙zywane do ich reprezentacji. 17. Om´ow poje‘ cie drzewa binarnego i drzewa przeszukiwania binarnego. Jak sa‘ realizowane podstawowe operacje: wstaw, usu´ n , znajd´z dla drzewa przeszukiwania binarnego. 18. Om´ow poje‘ cie zr´ownowa˙zonego drzewa cze‘ ´sciowo uporza‘dkowanego oraz operacji sortowania stogowego. 19. Om´ow poje‘ cie listy jednokierunkowej. Jaka jest zlo˙zono´s´c obliczeniowa wykonania na takiej liscie operacji: wstaw, usu´ n , znajd´z. 20. Zdefiniuj poje‘ cie abstrakcyjnego typu danych: slownik, stos, kolejka. Czym r´oz˙ ni sie‘ ich implementacja ( zlo˙zono´s´c obliczeniowa‘ operacji) przy pomocy struktury danych: lista jednokierunkowa. 21. Om´ow algorytm kt´ory bedzie znajdowal najdlu˙zszy wsp´olny podcia‘g dw´och list. 22. Zdefiniuj poje‘ cie abstrakcyjnego typu danych: zbi´or. Jakiego typu operacje wykonujemy na zbiorach? Jakie znasz struktury danych dla implementacji modelu danych zbi´or? 23. Wytlumacz dlaczego dla implementacji modelu danych zbi´or przy pomocy list jednokierunkowych posortowanie list znacza‘co skraca czas operacji suma. 24. Por´ownaj zlo˙zono´s´c obliczeniowa operacji i zajmowana‘ pamie‘ ´c dla reprezentacji zbioru przy pomocy abstrakcyjnego typu danych opartego na: liscie jednokierunkowej, wektorze wlasnym, tablicy mieszaja‘cej. 25. Co to jest grafowy model danych. Om´ow podstawowa‘ terminologie‘ dotycza‘ca‘ klasyfikacji graf´ow. 26. Om´ow dwie metody implementacji graf´ow: macierze sa‘siedztwa i listy sa‘siedztwa. Zilustruj przykladem. 27. Co to jest sp´ojna skladowa grafu, co to jest drzewo rozpinaja‘ce. Om´ow algorytm Kruskala dla znajdowania minimalnego drzewa rozpinaja‘cego. 28. Na czym polega sortowanie topologiczne grafu, podaj przykladowe zastosowanie. 29. Om´ow algorytm Dikstry. Jaka jest zlo˙zono´s´c obliczeniowa dla znalezienia najkr´otszej drogi pomiedzy wybranym wierzcholkiem oraz wszystkimi innymi wierzcholkami. 30. Om´ow algorytm Floyda. Jaka jest zlo˙zono´s´c obliczeniowa dla znalezienia najkr´otszej drogi pomiedzy wybranym wierzcholkiem oraz wszystkimi innymi wierzcholkami. 31. Co to jest relacyjny model danych, baza danych, schemat bazy danych. 32. Co nazywamy kluczem relacji, struktura‘ indeksu gl´ownego, struktura‘ indeksu drugorze‘ dowego. 33. Om´ow operator selekcji, la‘czenia i rzutowania algebry relacyjnej oraz podstawowe prawa dla tych operator´ow.
2
34. Co to jest drzewo wyra˙ze´ n algebry relacyjnej? Zilustruj podstawowe prawa algebry relacyjnej przeksztalcaja‘c drzewo wyra˙ze´ n. 35. Co to jest wzorzec, na czym polegaja‘ podstawowe sposoby jego opisu: automat, wyra˙zenie regularne, gramatyka? 36. Co to jest automat deterministyczny? 37. Co to jest automat niedeterministyczny? Om´ow podstawowe r´oz˙ nice pomie‘ dzy automatem deterministycznym i niedeterministycznym. 38. Na dowolnym przykladzie om´ow technike‘ konstrukcji podzbior´ow kt´ora umo˙zliwia systematyczne przej´scie od automatu niedeterministycznego do deterministycznego. 39. Co to jest wyra˙zenie regularne. Jak wygla‘daja‘ automaty dla przypadk´ow bazowych wyra˙ze´ n regularnych. 40. W jaki spos´ob konstruujemy automat z epsilon przej´sciami dla wyra˙zenia regularnego? 41. Jak przechodzimy od automat´ow do wyra˙ze´ n regularnych. Om´ow technike‘ eliminacji stan´ow. 42. Om´ow poje‘ cie gramatyki bezkontekstowej oraz je‘ zyka gramatyki. 43. Co to sa‘ drzewa rozbioru i w jaki spos´ob je konstruujemy dla danej gramatyki. 44. Co to znaczy niejednoznaczno´s´c gramatyki. Podaj przyklady. 45. Om´ow technike‘ schodzenia rekurencyjnego oraz konstrukcje‘ analizator´ow skladniowych. 46. Om´ow konstrukcje‘ analizatora skladniowego opartego na tabeli. 47. Om´ow przyklad je‘ zyka dla kt´orego istnieje gramatyka, ale nie istnieje wyra˙zenie regularne.
3
