Autor: Rafał Kumorek (kumorek_at_sawan.com.pl)
Data: Thu 18 Jan 2001 - 12:40:59 MET
Mrocq wrote:
>
> 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")?
Facet, to dla mnie wygląda jak powtórka ze studiów.
Szukaj książek do:
-Struktury danych,programowanie(np.Wirtha Algorytmy+Struktury
Danych=Programy) lub cos innego tego autora lub Aho,Hopcroft ,Ulmann,
-cos do systemów operacyjnych by Ci sie też przydało: Nie znam autora
ani tytułu(chyba Systemy operacyjne) ale na okładce był obraz Rembranta
z sekcją zwłok,
-cos na temat Teorii Programowania i Analizy Algorytmów też ci sie
przyda, ale tytułów już zapomniałem.
- no i jeszcze Teoria Języków i Automatów chyba Chomsky był od tego.
Tak na marginesie o problemie "filozofów" (z tego co pamiętam to oni tam
jedli spaghetti więc dlaczego chińscy ?)słyszałem a co to jest problem
"prysznica" ?
Pozdrowienia !
Rafał Kumorek
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 21:18:52 MET DST