Autor: Mrocq (apg_at_go2.pl)
Data: Tue 16 Jan 2001 - 22:46:43 MET
Czesc
Mam do opracwania pare pytan i nie bardzo wiem gdzie mam szukac
odpowiedzi...moze mi wskazecie miejsce gdzie znajde odpowiedz, a moze sami
odpowiecie.
Z gory dziekuje za wytrwalosc w czytaniu pytan oraz za ew. odpowiedzi.
Pozdrawiam
Adam
PS
Jesli macie gotowa odpowiedz, to poprosze na priva.
1. Wymień i opisz podstawowe struktury sterujące stosowane do budowy
algorytmów.
2. Jaka jest konstrukcja algorytmu sortowania bąbelkowego?
3. Narysuj schematy blokowe wyboru warunkowego, iteracji warunkowych typu
"dopóki" i "aż do" oraz iteracji ograniczonej.
4. Narysuj schemat blokowy sumowania (jednowymiarowej tablicy) wektora
n-elementowego (wykorzystaj zmienną indeksującą i znajomość długości
wektora).
5. Jakie korzyści przynosi stosowanie podprogramów (procedur) w algorytmach?
6. Na czym polega rekurencja w konstruowaniu algorytmów?
7. Jakie znasz podstawowe typy danych? Jak są one kodowane binarnie?
8. Jakie znasz statyczne struktury danych?
9. Jaka struktura sterująca byłaby właściwa dla przejrzenia tablicy
dwuwymiarowej?
10. Z jakich obiektów są budowane struktury dynamiczne?
11. Jak jest zorganizowana struktura danych zwana kolejką?
12. Jak jest zorganizowana struktura danych zwana stosem?
13. Jak jest zorganizowana struktura danych zwana listą?
14. Narysuj schemat blokowy sumowania pól kluczowych obiektów z listy
(wykorzystaj pola wskaźnikowe i symboliczną wartość nil).
15. Jakie znasz typy list - opisz ich cechy charakterystyczne?
16. Jak jest zorganizowana struktura danych zwana drzewem?
17. Co to jest drzewo binarne?
18. Jaki obiekt w drzewie nazywamy korzeniem a jaki liściem?
19. Podaj na przykładzie pierwszego etapu algorytmu sortowania drzewiastego
zasadę budowania drzewa BST.
20. Z jaką strukturą sterującą związane są drzewa? Ilustrując ten związek
opisz zasadę przeglądania drzewa w algorytmie sortowania drzewiastego?
21. Według jakich zasad można systematycznie przeglądać wierzchołki drzewa?
22. Jakie znasz elementy składowe typowego języka programowania?
23. Czym różni się kompilacja programu od jego interpretacji?
24. Na czym polega metoda rozwiązywania problemu algorytmicznego zwana
"wędruj i sprawdzaj" (podaj przykład algorytmu)?
25. Na czym polega metoda rozwiązywania problemu algorytmicznego zwana
"dziel i zwyciężaj" (podaj przykład algorytmu)?
26. Opisz schemat działania algorytmu sortowania przez scalanie.
27. Na czym polega metoda rozwiązywania problemu algorytmicznego zwana
"zachłanną" (podaj przykład algorytmu)?
28. Na czym polega metoda rozwiązywania problemu algorytmicznego zwana
"programowaniem dynamicznym" (podaj przykład algorytmu)?
29. Jakie znasz rodzaje błędów popełnianych przy konstrukcji i zapisie
algorytmów? Jakie mogą być ich konsekwencje?
30. Jaka jest różnica pomiędzy częściową i całkowitą poprawnością algorytmu?
31. Co nazywamy niezmiennikiem i zbieżnikiem przy analizie poprawności
algorytmów?
32. Jak określana jest złożoność algorytmów? Jakie znasz jej rodzaje?
33. Jak formalnie stwierdzamy, że dwa algorytmy maja złożoność tego samego
rzędu?
34. Podaj definicję i oznaczenie logarytmicznej złożoności algorytmu.
35. Podaj definicję i oznaczenie liniowej złożoności algorytmu.
36. Podaj definicję i oznaczenie kwadratowej złożoności algorytmu.
37. Podaj definicję i oznaczenie wykładniczej złożoności algorytmu.
38. Opisz schemat działania algorytmu wyszukiwania binarnego z listy
uporządkowanej? Jaką ma on złożoność?
39. Jaką złożoność mają znane Ci algorytmy sortowania?
40. Czym różni się analiza złożoności algorytmu w najgorszym przypadku od
analizy w średnim przypadku?
41. Jaki problem nazywamy zamkniętym z punktu widzenia złożoności
obliczeniowej?
42. Podaj przykłady problemów algorytmicznych zamkniętych z punktu widzenia
złożoności obliczeniowej i przykłady luk algorytmicznych?
43. Jaką złożoność ma problem wież Hanoi?
44. Co to znaczy, że jakiś fragment algorytmu ma dominującą złożoność?
45. Co to znaczy, że jedna funkcja złożoności jest ograniczona z góry przez
drugą?
46. Co to znaczy, że problem ma złożoność wielomianową?
47. Jakiego rodzaju problemy tworzą klasę problemów NP-zupełnych (podaj
przykłady)?
48. Jakie byłyby konsekwencje udowodnienia, że wybrany problem NP-zupełny
nie może być rozwiązany deterministycznym algorytmem o złożoności
wielomianowej?
49. Jakie byłyby konsekwencje skonstruowania dla wybranego problemu
NP-zupełnego deterministycznego algorytmu o złożoności wielomianowej?
50. Na czym polega idea konstruowania algorytmów przybliżonych?
51. Jakie problemy nazywamy nierozstrzygalnymi? Opisz przykładowy problem.
52. Co to jest problem stopu w algorytmie? Co wiadomo o tym problemie?
53. Co to jest maszyna Turinga, do czego służy i jak jest zbudowana?
54. Jak wygląda sterowanie w maszynie Turinga?
55. O czym mówi teza Churcha-Turinga i jakie ma znaczenie dla analizy
złożoności problemów algorytmicznych?
56. Co to jest automat skończony i jak jest zbudowany?
57. Czy automat skończony może służyć do przedstawiania algorytmów
obliczeniowych (uzasadnij odpowiedź)?
58. Skonstruuj diagram przejść dla automatu skończonego, który pracując nad
alfabetem {a, b} stwierdzi wystąpienie w ciągu danych sekwencji "aaa".
59. Jakie znasz modele współpracy procesorów pracujących równolegle?
60. Wyjaśnij pojęcie zasobu krytycznego w systemach pracujących współbieżnie
(na przykładzie problemów "prysznica" i "chińskich filozofów")?
61. Wyjaśnij pojęcie zastoju w systemach pracujących współbieżnie (na
przykładzie problemów "prysznica" i "chińskich filozofów")?
62. Wyjaśnij pojęcie zagłodzenia w systemach pracujących współbieżnie (na
przykładzie problemów "prysznica" i "chińskich filozofów")?
63. Wyjaśnij pojęcie aktywnego czekania w systemach pracujących współbieżnie
(na przykładzie problemów "prysznica" i "chińskich filozofów")?
64. Jak można rozwiązywać problem wzajemnego wykluczania w systemach
pracujących współbieżnie (wyjaśnij na przykładzie problemów "prysznica" i
"chińskich filozofów")?
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 21:18:37 MET DST