Wyszukiwarka:

Wszędzie ------------------ Artykuły Newsy Informacje Linki Pliki

Wstep do informatyki 1. Wymień o opisz struktury sterujące stosowane do budowy algorytmów. Podstawowe struktury sterujące to: 1.1. bezpośrednie następstwo – wykonaj instrukcję A, potem instrukcję B, potem instrukcję C, itd. 1.2. wybór warunkowy – jeśli warunek Q jest spełniony wykonaj instrukcję A, jeśli nie to wykonaj instrukcję B. 1.3. iteracja ograniczona – wykonaj instrukcję A dokładnie N razy. 1.4. iteracja warunkowa „dopóki” – dopóki warunek Q jest spełniony wykonuj instrukcję A. 1.5. Iteracja warunkowa „aż do” – wykonuj instrukcję A dopóki warunek Q jest spełniony. 2. Jaka jest konstrukcja algorytmu sortowania bąbelkowego? Sortowanie bąbelkowe polega na przestawianiu sąsiednich par elementów stojących w niewłaściwej kolejności. Istotne jest iż ciąg elementów przeglądany jest zawsze w tym samym kierunku, a przeglądanie to trwa dopóki mogą się w nim pojawić elementy w nieodpowiedniej kolejności. Zapis słowny algorytmu sortowania bąbelkowego: 1. wykonaj co następuje N-1 razy; 1.1. wskaż na pierwszy element; 1.2. wykonaj co następuje N-1 razy; 1.2.1. porównaj ze sobą wskazany element i element następny; 1.2.2. jeśli elementy stoją w złej kolejności to zamień je miejscami; 1.2.3. wskaż na następny element; 3. Narysuj schemat blokowy: wyboru warunkowego, iteracji warunkowych typu: „dopóki” i „aż do”. Schematy znajdują się na załączonym dodatku. 4. Zapisz słownie i naszkicuj schemat blokowy algorytmu sumowania wektora (jednowymiarowej tablicy) – n elementowego. Wykorzystaj zmienną indeksującą i znajomość długości wektora. Zapis słowny algorytmu sumowania n -elementowego wektora: 1. zanotuj na boku liczbę zero; 2. wskaż na pierwszy element wektora; 3. wykonaj co następuje n-1 razy; a. dodaj wartość wskazanego elementu do liczby zanotowanej na boku; b. wskaż na kolejny element wektora; 4. dodaj wartość wskazanego elementu do liczby na boku; 5. wypisz wartość liczby na boku; Schemat blokowy algorytmu w załączonym dodatku. 5. Jakie korzyści przynosi stosowanie procedur (podprogramów) w algorytmach? Zalety stosowania procedur są następujące: 1. oszczędność tekstu 2. znacznie większa przejrzystość i czytelność struktury algorytmu 3. znacznie większa kontrola nad poprawnością algorytmu 4. uproszczenie we wprowadzaniu poprawek i usuwaniu błędów 5. możliwość programowania analitycznego i syntetycznego 6. Na czym polega rekurencja i jak można ją wykorzystać w konstruowaniu algorytmów? Rekurencja – to zdolność podprogramu (procedury) do wywoływania samej siebie. Przykładem zastosowania procedury rekurencyjnej jest algorytm przenoszenia krążków znany z Wież Hanoi. Tam aby wykonać pewne przeniesienie należy przy okazji wykonać inne, czyli wywołać tę samą procedurę wewnątrz procedury wywoływanej na początku. Inne przykłady wykorzystania procedur rekurencyjnych to: - przeglądanie lewostronne struktur drzewiastych - obliczanie wartości n! liczby n. 7. Jakie znasz podstawowe typy danych? Jak są one kodowane binarnie? Podstawowe typy danych to: - liczby (całkowite, dziesiętne, dwójkowe, szesnastkowe) - słowa (układy liter z różnych alfabetów) - wskaźniki (dane tego typu zawierają adresy - wskazania na inne elementy w pamięci operacyjnej – dane tego typu wymagają specjalnego traktowania) Kodowanie liczb – przeliczenie ich wartości na wartości binarne, czyli zero – jedynkowe. Kodowanie słów - odbywa się za pomocą standardu ASCII (American Standard Code for Information Interchange). Zgodnie z nim każdemu znakowi przypisana jest liczba od 0 do 127 – kodowanie na ośmiu bitach. 8. Jakie znasz statyczne struktury danych? Do statycznych struktur danych należą: 1. zmienne – podstawowe obiekty w pamięci, posiadające własną nazwę i zdolność przechowywania pojedynczego elementu. 2. wektory – czyli tablice jednowymiarowe – są to obiekty w pamięci mające nadaną własną nazwę i posiadające zdolność przechowywania określonej mnogości elementów, z których każdy oznaczony jest odpowiednim, unikalnym indeksem. 3. tablice dwuwymiarowe – macierze - są to obiekty w pamięci mające nadaną własną nazwę i posiadające zdolność przechowywania określonej mnogości elementów, z których każdy oznaczony jest dwoma indeksami. 4. Tablice wielowymiarowe – są to obiekty w pamięci mające nadaną własną nazwę i posiadające zdolność przechowywania odpowiedniej mnogości elementów, z których każdy oznaczony jest n – indeksami. 9. Jaka struktura sterująca byłaby właściwa do przejrzenia tablicy dwuwymiarowej? Odpowiednią do tego zadania strukturą sterującą jest iteracja zagnieżdżona. Iteracja zewnętrzna odpowiada za przeglądanie kolumn a iteracja wewnętrzna za przegląd wierszy. 10. Z jakich obiektów są zbudowane dynamiczne struktury danych? Dynamiczne struktury danych budowane są z dwóch głównych rodzajów obiektów: 1. zmiennych kluczowych i dodatkowych (przechowujących odpowiednie dane) 2. zmiennych wskaźnikowych (wskazujących na kolejne elementy tych struktur, lub przechowujące wartość NIL) Rozróżniając dokładniej wyróżniamy: a) listy jednokierunkowe – każdy element tej struktury posiada pola kluczowe, dodatkowe i jedno pole wskaźnikowe, odwołujące się do następnego elementu struktury. b) listy dwukierunkowe – każdy element tej struktury posiada pola kluczowe, dodatkowe i dwa pola wskaźnikowe, odwołujące się do następnego i poprzedniego elementu struktury. c) drzewa – każdy element tej struktury posiada pola kluczowe, dodatkowe, pola wskaźnikowe na potomków (w liczbie n, np.: drzewa binarne 2) i pole wskaźnikowe na rodzica. 11. Jak jest zorganizowana struktura danych zwana kolejką? Kolejka (zwana także strukturą FIFO z ang. first in first out) to specjalna struktura dynamiczna, o ograniczonych możliwościach modyfikacji. Operacja dodawania elementu do struktury (insert) odbywa się zawsze na początku, a operacja odłączania (delete) elementu od struktury odbywa się zawsze na końcu tejże struktury. Zachowana zostaje kolejność dołączania i odcinania elementów od struktury – pierwszy przyłączony będzie pierwszym odłączonym. 12. Jak jest zorganizowana struktura danych zwana stosem? Stos (zwany także strukturą LIFO z ang. last in first out) to specjalna struktura dynamiczna, o ograniczonych możliwościach modyfikacji. W strukturze tego typu zarówno operacje dołączania (insert) jak i odłączania (delete) elementów struktury odbywają się z tej samej strony struktury – na początku. Porządek dołączania i odcinania elementów jest taki, że element położony na strukturze jako ostatni pierwszy będzie z niej zdjęty. 13. Jak jest zorganizowana struktura danych zwana listą? Lista to struktura składająca się z wielu odpowiednio ze sobą połączonych ze sobą elementów. Każdy element jest identyczny jak pozostałe i składa się z odpowiedniej ilości pól kluczowych, dodatkowych i wskaźnikowych (lista jednokierunkowa 1 pole wskaźnikowe, dwukierunkowa 2 pola wskaźnikowe). Pola kluczowe i dodatkowe przechowują informacje, natomiast pola wskaźnikowe zawierają adresy do elementów: następnego (jednokierunkowa) i poprzedniego (dwukierunkowa). 14. Narysuj schemat blokowy sumowania pól kluczowych obiektów z listy. Wykorzystaj pola wskaźnikowe i wartość NIL. Schemat blokowy znajduje się w załączonym dodatku. 15. Jakie znasz typy list? a) lista jednokierunkowa – każdy węzeł zawiera pole kluczowe, pola dodatkowe i jedno pole wskaźnikowe z adresem następnego węzła struktury. b) lista dwukierunkowa – każdy węzeł zawiera pole kluczowe, pola dodatkowe i dwa pola wskaźnikowe z adresami następnego i poprzedniego węzła struktury. c) lista z wartownikiem – jest to dwukierunkowa lista, z której wyeliminowano wskazanie NIL. Pierwszy węzeł jako wskazanie na węzeł poprzedni odnosi się do węzła ostatniego. Węzeł ostatni jako wskazanie na węzeł następny odnosi się do węzła pierwszego. (Jest to jak gdyby zapętlenie struktury.) d) lista jako kolejka e) lista jako stos 16. Jak jest zorganizowana struktura danych zwana drzewem? Drzewo składa się z odpowiedniej mnogości identycznych elementów - zwanych węzłami. Każdy węzeł zawiera: - pole kluczowe (zawiera dane) - pola dodatkowe (zawierają dane) - pola wskaźnikowe na potomstwo (zawierają adresy potomstwa – elementów następnych) - pole wskaźnikowe na rodzica (zawiera adres rodzica – elementu poprzedniego) Opis biologiczny drzewa: 1. wskazanie na korzeń – element wskaźnikowy (na grafie często pomijany), zawierającym adres pierwszego węzła drzewa. 2. korzeń – pierwszy węzeł drzewa (zazwyczaj w grafie umieszczony na górze), nie posiadający rodzica. 3. węzły – wszystkie elementy struktury leżące pomiędzy korzeniem a liśćmi. 4. liście – elementy leżące na najniższym poziomie drzewa i nie posiadające potomstwa (ich pola wskaźnikowe przechowują wartość NIL). Połączenia pomiędzy poszczególnymi węzłami określa się mianem gałęzi drzewa. W celu ustanowienia hierarchii w strukturze drzewiastej przyjęto iż elementy leżące na gałęziach danego węzła określa się mianem potomstwa danego węzła. Wskazany element jest zatem rodzicem elementów jemu podległych. W drzewie wyróżnia się także poziomy, przy czym ich odliczanie zaczyna się od góry: korzeń stanowi poziom pierwszy, a poziom ostatni tworzą liście. Wszystkie drzewa dzieli się na: BST – drzewo, którego rząd wyjściowy potomków ograniczony jest przez 2. PEŁNE – drzewo, w którym wszystkie wierzchołki poza liśćmi mają jednakową liczbę potomków i wszystkie liście są na tym samym poziomie. 17. Co to jest drzewo binarne? Drzewo binarne to drzewo, którego rząd wyjściowy węzłów jest ograniczony przez 2. Każdy węzeł może zatem posiadać maksymalnie 2 potomków. 18. Jaki obiekt w drzewie nazywany jest liściem a jaki korzeniem? Korzeń – jest to wierzchołek drzewa (w grafie zazwyczaj umieszczany na górze) - nie posiadający rodzica. W korzeniu mają początek wszystkie procesy algorytmiczne oparte na strukturze danych tego typu. Liść – wierzchołek końcowy drzewa (w grafie umieszczony zazwyczaj na dole) - nie posiadający potomstwa. Odpowiada on różnym wynikom zakończenia obliczeń w algorytmie. 19. Podaj na przykładzie pierwszego etapu algorytmu sortowania drzewiastego zasadę budowy drzewa BST. Aby przekształcić nieuporządkowaną listę wejściową w drzewo poszukiwań binarnych musimy wziąć pierwszy element drzewa i zapisać go jako korzeń nowopowstającego drzewa. Następnie biorąc każdy kolejny element z listy porównujemy go z elementami już należącymi do drzewa i: - jeśli element jest mniejszy umieszczamy go po lewej stronie korzenia. - jeśli element jest większy umieszczamy go po prawej stronie korzenia. Postępujemy tak aż do wyczerpania listy. 20. Z jaką strukturą sterującą związane są drzewa? Ilustrując ten związek opisz zasadę przeglądania drzewa w algorytmie sortowania drzewiastego. Drzewa związane są z rekurencją. Opis słowny algorytmu przeglądu drzewa w algorytmie sortowania drzewiastego: procedura OBEJDŹ drzewo T: 1. jeśli T jest puste to wróć 2. w przeciwnym razie wykonaj co następuje: a. wywołaj obejdź T w lewo b. wypisz element umieszczony w korzeniu c. wywołaj obejdź T w prawo Zasada przeglądu drzewa w algorytmie sortowania drzewiastego jest taka, że najpierw wywołana zostaje procedura obejdź pod-drzewo z lewej strony, wypisz wartość korzenia i obejdź pod-drzewo z prawej strony. W drzewie BST z lewej umieszczone są elementy mniejsze niż w korzeniu, a z prawej większe. Mamy więc pewność, że dzięki takiej organizacji wypisane zostaną elementy od najmniejszego do największego. Związek pomiędzy drzewem i rekurencją jest tak silny dlatego, że nawet sam graf kolejnych wywołań rekurencyjnych ma strukturę drzewiastą. 21. Według jakich zasad można systematycznie przeglądać strukturę drzewiastą? Przegląd struktury = budowanie ciągu zawierającego wszystkie elementy tej struktury. Strukturę drzewiastą można przeglądać na trzy sposoby: - wędruj i sprawdzaj (metoda rekurencyjna) Jest to prosta metoda polegająca na przejrzeniu wszystkich elementów struktury i wypisaniu kolejno wszystkich jej elementów. - przegląd w głąb (metoda iteracyjna) Schemat działania algorytmu: 1. Wypisany zostaje korzeń (jako pierwszy element ciągu) 2. Algorytm wybiera ostatni element ciągu nie posiadający etykiety „zamknięty” i postępuje zgodnie z zasadą: jeśli wierzchołek nie ma potomstwa – nadaj mu etykietę „zamknięty”, jeśli ma, wypisz potomków sprawdzając od lewej Wszystko powtarzane jest dopóki wszystkie elementy ciągu nie mają etykiety „zamknięty”. - przegląd w szerz (metoda iteracyjna) Schemat działania algorytmu: 1. Nadanie wszystkim elementom drzewa etykiety „nowy” 2. Wypisanie korzenia jako pierwszego elementu ciągu 3. Algorytm wybiera z ciągu pierwszy element z etykietą „nowy” , dopisuje do ciągu wszystkich jego potomków (nadając im etykietę „nowy”) i zdejmuje etykietę „nowy” z danego elementu. Wszystko powtarzane jest dopóki w ciągu znajdują się elementy z etykietą „nowy”. Po utworzeniu odpowiedniego ciągu, do jego przeszukiwania wykorzystujemy metodę: „wędruj i sprawdzaj”. Metoda ta polega na przechodzeniu kolejnych elementów ciągu i porównywaniu ich ze wzorcem elementu poszukiwanego. Po natrafieniu na odpowiedni element zostaje on wypisany. 22. Jakie znasz elementy składowe typowego języka programowania? Elementy składowe języka programowania to: - symbole (alfabet danego języka programowania – określa jakich znaków wolno używać podczas tworzenia programów i jakie jest ich znaczenie – np.: alfabet łaciński, grecki, znaki matematyczne itp.) - słowa kluczowe (jest to zbiór ciągów symboli o specjalnym znaczeniu – np.: komendy i instrukcje) - składnia – (zawiera: opis dostępnych struktur sterujących np.: bezpośrednie następstwo, wybór warunkowy, iteracja ograniczona – decyduje jakich struktur można używać a jakich nie; opis sposobu definiowania rozmaitych struktur sterujących – mówi w jaki sposób prawidłowo korzystać z poszczególnych instrukcji; schematy podstawowych instrukcji) - semantyka (jest to zbiór przepisów odpowiadających na pytania: „co znaczy to zdanie” lub „co znaczy ta instrukcja” – określa prawidłowość składniową zapisywanych wyrażeń) 23. Czym różni się kompilacja programu od jego interpretacji? Kompilacja – jest wykonywana jednorazowo po zakończeniu pisania programu. Jest to przełożenie całego programu napisanego w języku wysokiego poziomu na program w języku niższego poziomu. Programy napisane w językach kompilowanych np.: w C, C++ są o wiele szybsze niż identyczne programy zapisane w językach interpretowanych. Interpretacja – jest to proces tłumaczenia poszczególnych komend z języka wysokiego poziomu na kod maszynowy zrozumiały dla maszyny, w czasie ich wykonywania. Ta translacja wykonywana jest za każdym razem gdy uruchamiany jest dany program, przez co wykonywanie takiego programu jest o wiele wolniejsze od programów kompilowanych. 24. Na czym polega metoda algorytmiczna zwana „wędruj i sprawdzaj”? Metoda algorytmiczna typu „wędruj i sprawdzaj” polega na prostym przeglądzie struktury danych w celu odnalezienia zadanego elementu w tej strukturze. Przykładem wykorzystania metody „wędruj i sprawdzaj” jest algorytm wyszukiwania największej przekątnej w wielokącie wypukłym. Najpierw tworzymy tabelę dwuwymiarową zawierającą dane o odległościach dzielących wszystkie wierzchołki. Potem przeglądamy kolejno wszystkie elementy tej struktury w celu znalezienia największego elementu. Istotne dla tej metody jest uwzględnienie odpowiedniej struktury sterującej w zależności od struktury danych, którą chcemy przejrzeć, i tak: wektor, lista - iteracja tablice wielowymiarowe, listy list itp. - iteracje zagnieżdżone drzewa - rekordy 25. Na czym polega metoda algorytmiczna zwana „dziel i zwyciężaj”? Metoda „dziel i zwyciężaj” postępuje zgodnie z zasadą, że jeśli jakiś problem jest za duży by uporać się z nim w całości, to należy spróbować podzielić go na mniejsze części o takiej samej strukturze. Ta metoda algorytmiczna związana jest ściśle z procedurami rekurencyjnymi. Przykładem wykorzystania metody „dziel i zwyciężaj” jest algorytm sortowania przez scalania. Najpierw dzielimy n -elementową listę wejściową na połowy, potem otrzymane połowy znów na połowy i tak do chwili kiedy nie otrzymamy n pojedynczych elementów. Potem porównujemy ze sobą pary elementów i tworzymy uporządkowane ciągi dwuelementowe, porównujemy ciągi dwuelementowe i tworzymy posortowane ciągi cztero elementowe, i tak do chwili kiedy nie otrzymamy jednej porządkowanej n elementowej listy. Opis słowny rekurencyjnego algorytmu sortowania przez scalanie: Procedura SORTUJ LISTĘ L: 1. jeśli lista zawiera 1 element to jest posortowana 2. w przeciwnym razie wykonaj co następuje: a. podziel listę na L1 i L2 b. wywołaj SORTUJ L1 c. wywołaj SORTUJ L2 d. scal posortowane listy L1 i L2 w jedną posortowaną listę 3. wróć do poziomu wywołania 26. Na czym polega metoda algorytmiczna zwana „zachłanną”? Istnieją zadania, których rozwiązanie można budować z dobieranych kolejno elementów i do takich właśnie zadań przeznaczona jest metoda zachłanna. Postępuje ona zawsze zgodnie z zasadą „łap co masz najlepszego pod ręką i nigdy nie oddawaj tego co już masz”. Jest to metoda efektywna tylko w pewnej grupie problemów. Przykładem zastosowania metody „zachłannej” jest algorytm poszukiwania najtańszej sieci wiążącej wszystkie podane punkty (czyli budowanie minimalnego drzewa rozpinającego w zadanym grafie). Mając daną sieć punktów połączonych odcinkami o podanej wadze wybieramy najtańszy. Potem wybieramy najtańszy odchodzący od punktów które już mamy itd. Czynność powtarzamy do chwili kiedy nie połączymy wszystkich oznaczonych na płaszczyźnie punktów. Opis algorytmu: 1. wybierz odcinek o najmniejszej wadze 2. powtarzaj co następuje aż do połączenia wszystkich punktów na płaszczyźnie: - wybierz najtańszy odcinek łączący punkt który już masz, z tym dowolnym który nie jest jeszcze przyłączony Metoda ta daje bardzo dobre wyniki gdy poszukiwana jest najtańsza wagowo ścieżka połączeń wszystkich punktów na płaszczyźnie (tzw. minimalne drzewo rozpinające). Nie daje jednak poprawnych wyników gdy wykorzystuje się ją do np.: poszukiwania najtańszej drogi łączącej dwa wskazane punkty na płaszczyźnie. 27. Opisz schemat działania algorytmu sortowania przez scalanie. Sortowanie przez scalanie polega na podzieleniu za pomocą procedury rekurencyjnej n –elementowej listy wejściowej na n pojedynczych elementów. Następnie algorytm wykonuje kolejno porównania: najpierw par elementów (tworząc posortowane ciągi 2 –elementowe), potem ciągów 2 elementowych (tworząc posortowane ciągi 4 elementowe), i tak do chwili gdy nie powstanie posortowana n –elementowa lista. Najistotniejszym etapem tego algorytmu jest etap scalania. W etapie tym następuje porównanie dwóch identycznych części (n –elementowych ciągów) i przekształcenie ich tak by utworzyły 2n –elementowy, posortowany ciąg wynikowy. Porównanie odnosi się zawsze do dwóch pierwszych elementów ciągów wejściowych, a do nowopowstającego, posortowanego ciągu wynikowego przepisywany jest mniejszy element porównania. Opis słowny algorytmu: Procedura SORTUJ listę L; 1. jeśli lista zawiera tylko jeden element to jest posortowana 2. w przeciwnym razie wykonaj co następuje a. podziel listę L na L1 i L2 b. wywołaj SORTUJ listę L1 c. wywołaj SORTUJ listę L2 d. scal posortowane listy L1 i L2 w jedną posortowaną liste L (etap iteracyjny) 3. wróć do poziomu wywołania 28. Na czym polega metoda algorytmiczna zwana „programowaniem dynamicznym”? Metoda algorytmiczna zwana „programowaniem dynamicznym” opiera się o zasadę optymalności Bellmana, która mówi: „jeśli znamy najlepszą drogę przejścia z punktu początkowego do punktu końcowego prowadzącą przez kolejne punkty, to każdy fragment tej drogi pomiędzy dowolnym punktem a punktem końcowym jest najlepszą drogą przejścia od tego punktu do punktu końcowego”. Przykładem zastosowania metody „dynamicznej” jest algorytm wyszukiwania najkrótszej ścieżki łączącej dwa wskazane punkty na płaszczyźnie – grafie skierowanym (problem strudzonego wędrowca). W zadaniu tym w przeciwieństwie do metody zachłannej nie chwyta się tych elementów które w danej chwili są najlepsze lecz próbuje się ustalić jakie wyjście da najlepszy efekt końcowy. Analizując poszczególne fragmenty grafu poruszamy się od końca – czyli od punktu oznaczonego flagą „meta”. Badając kolejne ścieżki grafu poznajemy wagę wszystkich możliwych dróg spośród których wybieramy najlepszą. 29. Jakie znasz rodzaje błędów popełniane przy konstrukcji i zapisie algorytmów? Jakie mogą być ich konsekwencje? Najczęściej spotykanymi rodzajami błędów są: Błędy językowe (składniowe). Powstają w wyniku naruszenia składni używanego języka programowania. np.: - użycie for(i=0, i Automat skończony wykorzystywany jest przede wszystkim w problemach decyzyjnych. 57. Czy automat skończony może służyć do przedstawiania algorytmów obliczeniowych? Automat skończony nie może być stosowany do wykonywania obliczeń, bo nie potrafi liczyć. Wynika to z jego ograniczeń konstrukcyjnych – porusza się on tylko w jedną stronę (zatem nie może powracać do miejsc w których już była) i nie posiada funkcji zapisu (bo i tak nie mogłaby powrócić do zapisanych danych). Bez możliwości zapisu maszyna nie jest wstanie wykonywać działań matematycznych a jedynie może rozwiązywać problemy decyzyjne. 58. Jakie znasz modele współpracy procesorów pracujących równolegle? Pamięć dzielona: - dzielenie dostępu tylko podczas odczytywania - dzielenie dostępu podczas zapisywania Nieograniczona pamięć dzielona jest praktycznie niemożliwa do zrealizowania, ze względu na bardzo dużą złożoność połączeń elementów pamięci i procesorów Sieci o ustalonej konfiguracji połączeń: - każdy procesor może być połączony z co najwyżej pewną stałą liczbą (w zależności od sieci) liczbą procesorów sąsiadujących - sieci są konstruowane często jako równoległe maszyny rozwiązujące szczególne problemy algorytmiczne Dobrze znanym przykładem są sieci logiczne (boolowskie): bramki – procesory realizujące proste funkcje logiczne na bitach (AND, OR, NOT, NAND, itp.) 59. Wyjaśnij pojęcie zasobu krytycznego w systemach pracujących współbieżnie (problem prysznica i chińskich filozofów). Zasób krytyczny to taki zasób systemowy, który jest ograniczony ilościowo i jednocześnie przeznaczony do użytku wszystkich pracujących w danym systemie procesorów. Zasobem krytycznym może być pamięć operacyjna, linie lub łącza transmisyjne. Analogią do zasobu krytycznego w problemie „prysznica hotelowego” jest sam prysznic. Jest on tylko jeden, a wszyscy chcą z niego korzystać. W przykładzie „chińskich filozofów” zasobem krytycznym są pałeczki. Dla N filozofów jest zaledwie N/2+1 pałeczek, a każdy z filozofów potrzebuje dwóch by się posilić. 60. Wyjaśnij pojęcie zastoju w systemach pracujących współbieżnie. Zastój w systemach pracujących współbieżnie to sytuacja, w której następuje zakleszczenie wszystkich procesorów i żaden z procesorów, nigdy już nie otrzyma dostępu do zasobu krytycznego. Analogia w przykładzie „prysznica hotelowego” jest sytuacja, gdy jeden z gości hotelowych zasłabł pod prysznicem, jeden z gości hotelowych nie przychodzi skorzystać z prysznica gdy nadchodzi jego kolej lub po prostu jeden pokój jest pusty. W takim wypadku numer na tablicy informacyjnej umieszczonej na drzwiach prysznica nigdy już się nie zmieni i nigdy żaden inny mieszkaniec hotelu nie będzie mógł skorzystać z prysznica. 61. Wyjaśnij pojęcie zagłodzenia w systemach pracujących współbieżnie. Zagłodzenie procesora w systemie pracującym współbieżnie to sytuacja, w której jednemu z procesorów brakuje dostępu do zasobu krytycznego zawsze gdy ten jest mu potrzebny. Analogia w przykładzie „prysznica hotelowego” jest taka, że w pierwotnej wersji jeden z gości zameldowanych w ów hotelu, przychodzi sprawdzić czy prysznic jest wolny, i zawsze trafia na sytuację kiedy jest zajęty. 62. Wyjaśnij pojęcie aktywnego czekania w systemach pracujących współbieżnie. Aktywne czekanie to czekanie z ciągłym sprawdzaniem, czy dostęp do zasobu krytycznego przypadkiem nie został zwolniony. Analogią do aktywnego czekania w przypadku „prysznica hotelowego” było ciągłe sprawdzanie mieszkańców hotelu, czy na tablicy wstępu pod prysznic nie pojawił się przypadkiem numer ich pokoju. W przypadku „chińskich filozofów” było to ciągłe sprawdzanie czy przypadkiem dany filozof nie ma w danej chwili dostępu do dwóch pałeczek.