Pytania TMO i GiS
1. Kiedy system masowej obsługi jest stabilny?
Gdy ρ < 1
2. Kiedy system masowej obsługi nie jest stabilny?
Gdy ρ >= 1
3. Kiedy system masowej obsługi M/M/n/∞ nie jest stabilny?
Gdy ρ = λ/(nμ) >= 1
4. Podaj równanie stabilności kolejki dla systemu M/M/4/∞.
ρ = λ/(4μ) < 1
5. Co to jest stabilność systemu masowej obsługi?
Zjawisko nie powstawania nieskończenie długiej kolejki.
6. W jaki sposób można poprawić stabilność systemu.
a) zwiększając ilość stanowisk obsługi
b) zwiększając szybkość obsługi
c) zmniejszając ilość klientów
7. Wymień podstawowe rozkłady losowe stosowane w systemach masowej obsługi?
- Jednostajny
- Normalny
- Wykładniczy
- Erlanga
8. Wymień co najmniej dwa znane ci regulaminy kolejki.
- FIFO
- FILO
- SIRO (losowa kolejność)
9. Podaj przykład systemu M/M/1/∞.
Stoisko na bazarze z 1 sprzedawcą.
10. Podaj przykład systemu M/M/1/4.
Sklep z jedną ekspedientką, w którym mieszczą się 4 osoby.
11. Podaj przykład systemu M/M/2/∞.
Stoisko na bazarze, w którym klientów obsługuje ojciec z córką
12. Podaj przykład systemu M/M/3/5.
Warsztat samochodowy z trzema stanowiskami i parkingiem na 5 miejsc
13. Wymień co najmniej trzy parametry charakteryzujące system masowej obsługi.
- średnia ilość oczekujących w kolejce
- prawdopodobieństwo braku kolejki
- średnia ilość obiektów w systemie
- zgłoszenia w jednostce czasu
- obsługa w jednostce czasu
- prawdopodobieństwo oczekiwania w kolejce dłużej niż T
- prawdopodobieństwo wystąpienia kolejki
14. Na czym polega regulamin kolejki FIFO.
Pierwszy wchodzi => pierwszy wychodzi.
15. Na czym polega regulamin kolejki LIFO.
Ostatni wchodzi => pierwszy wychodzi (jest obsługiwany)
16. Co to jest klasyfikacja Kendalla.
Klasyfikacja systemów MO. Zawiera informacje o:
- rozkładzie zgłoszeń
- rozkładzie czasu obsługi
- ilości stanowisk obsługi
- dopuszczalnej długości kolejki
17. Podaj znaczenie terminu oczekiwanie w systemie masowej obsługi.
Czas od momentu zgłoszenia do chwili rozpoczęcia obsługi
18. Podaj znaczenie terminu przebywanie w systemie masowej obsługi.
Czas od momentu zgłoszenia do systemu do momentu opuszczenia systemu
19. Scharakteryzuj parametr oceniający strumień zgłoszeń w SMO.
λ – ilość zgłoszeń w jednostce czasu
20. Scharakteryzuj parametr oceniający proces obsługi w SMO.
μ – ilość klientów obsługiwanych w jednostce czasu
21. Co to jest czterokanałowy system masowej obsługi.
System posiadający 4 stanowiska obsługi.
22. Co to jest wielokanałowy system masowej obsługi.
System posiadający więcej niż jedno stanowisko obsługi.
23. Podaj wzór na intensywność (natężenie) ruchu w SMO.
ρ = λ/(μ)
24. Podaj wzór na intensywność (natężenie) ruchu w dwukanałowym SMO.
ρ = λ/(2μ)
25. Średni odstęp czasu pomiędzy zgłaszającymi się pojazdami wynosi 5 minut. Scharakteryzuj proces zgłoszeń do systemu masowej obsługi.
λ = 12 [poj/h]
26. Podaj charakterystykę procesu obsługi w sklepie z czterema stanowiskami kasowymi, w których obsługa na jednym stanowisku trwa średnio trzy minuty.
μ = 20 [kl/h]; 4 μ = 100 [kl/h]
27. Intensywność zgłoszeń do systemu l=12 sam/godz. Jaki jest średni odstęp czasu pomiędzy zgłaszającymi się samochodami.
5 minut.
28. Jaka jest intensywność ruchu w warsztacie samochodowym o trzech stanowiskach obsługi do którego zgłasza się średnio 6 samochodów na godzinę. Stanowisko obsługuje samochody średnio przez 20 minut.
ρ = λ/(3μ) = 6/(3*3)= 0,667
29. Jaka jest intensywność ruchu w warsztacie samochodowym o dwóch stanowiskach obsługi do którego zgłasza się samochód średnio co 12 minut. Stanowisko może obsłużyć średnio 3 samochody na godzinę.
ρ = λ/(2μ) = 5/(2*3) = 5/6
30. Co to jest graf?
Trójka uporządkowana zawierająca:
- zbiór wierzchołków
- zbiór gałęzi
- określenie relacji pomiędzy wierzchołkami i gałęziami
31. Co to jest sieć?
Graf wraz określeniem funkcji określonych na wierzchołkach i/lub gałęziach
32. Czym różni się sieć od grafu?
Niepustym zbiorem funkcji określonych na wierzchołkach i lub krawędzich
33. Kiedy sieć stanie się grafem?
Gdy dołączymy do niej zbiór funkcji określonych na wierzchołkach i/lub gałęziach
34. Wymień rodzaje gałęzi w grafie.
- krawędzie
- łuki
- pętle
35. Co to jest łuk w grafie?
Gałąź posiadająca skierowanie, incydentna z dwoma wierzchołkami
36. Co to jest pętla w grafie?
Gałąź posiadająca skierowanie, incydentna z jednym wierzchołkiem
37. Co to jest krawędź w grafie?
Gałąź nieposiadająca skierowania
38. Kiedy dwa wierzchołki są przyległe?
Gdy są połączone gałęzią.
39. Kiedy dwie gałęzie są przyległe?
Gdy istnieje co najmniej jeden wierzchołek incydentny jednocześnie z jedną i drugą gałęzią.
40. Co to znaczy, że wierzchołek i gałąź są incydentne?
Że dana gałąź zaczyna się lub kończy w wierzchołku
41. Co to jest macierz przyległości wierzchołków grafu?
Określa ilość gałęzi łączących parę wierzchołków grafu. Jest symetryczna.
42. Co to jest macierz przejść grafu?
O ilości (ilość krawędzi + ilość odpowiednio skierowanych łuków)możliwych do realizacji przejść pomiędzy dwoma wierzchołkami
43. O czym informuje binarna macierz przejść grafu?
O możliwości lub braku możliwości przejścia pomiędzy wierzchołkami
44. O czym informuje binarna macierz przyległości grafu?
O przyległości lub braku przyległości danych wierzchołków grafu (jest symetryczna)
45. Co to jest stopień wierzchołka grafu?
Ilość krawędzi incydentnych + il. Łuków wchodzących + il łuków wychodzących + il. pętli
46. Co to jest rozwidlenie wierzchołka grafu?
Ilość krawędzi incydentnych + il. Łuków wchodzących + il łuków wychodzących + 2 * il. Pętli
Lub
Stopień + liczba pętli
47. Czym różni się rozwidlenie wierzchołka od jego stopnia?
Różni się o ilość pętli incydentnych z danym wierzchołkiem
48. Dla których wierzchołków stopień i rozwidlenie wierzchołków są równe?
Dla tych, które nie mają incydentnych z nimi pętli
49. Dla których wierzchołków stopień i rozwidlenie wierzchołków są różne?
Dla tych, które mają incydentne z nimi pętle
50. Co to jest graf skierowany?
Graf posiadający wyłącznie łuki i pętle
51. Jakich gałęzi nie posiada graf skierowany?
krawędzi
52. Co to jest graf niezorientowany?
Posiadający tylko krawędzie i pętle
53. Jakich gałęzi nie posiada graf niezorientowany?
Łuków
54. Co to jest graf pusty?
Graf nieposiadający gałęzi.
55. Jakich gałęzi nie posiada graf pusty?
Jakichkolwiek
56. Jaka jest krotność unigrafu?
1
57. Jaka jest krotność multigrafu?
Więcej niż 1
58. Co to jest graf zwykły?
Niezorientowany, bez pętli (posiada tylko krawędzie)
59. Co to jest graf Berge’a?
Digraf i unigraf
60. Co to jest podgraf?
Wybrana część wierzchołków i wszystkie gałęzie incydentne z nimi
61. Co to jest graf częściowy?
Wszystkie wierzchołki i wybrana ilość gałęzi
62. Co to jest podgraf pusty?
Podgraf będący grafem pustym
63. Co to jest maksymalny podgraf pusty?
Taki podgraf pusty, którego zbiór wierzchołkow nie jest podgrafem żadnego innego podgrafu pustego
64. Wymień etapy metody wyznaczania optymalnego kolorowania wierzchołków grafu.
1. Zapis zbioru wierzchołków w postaci macierzy
2. Konstrukcja funkcji Boole’wskiej
3. Znalezienie minimalnej formuły alternatywnej (nie dającej się zredukować)
4. Określenie baz minimalnych
5. Określenie maksymalnych podgrafów pustych
6. Znalezienie pokryć minimalnych.
7. Najmniej liczne pokrycia określają zbiory wierzchołków, które mogą mieć ten sam kolor
65. Zdefiniuj problem pokryć minimalnych zbioru.
Znalezienie najmniejszej liczby podzbiorów danego zbioru tworzących cały ten zbiór.
67. Wymień metody suboptymalnego kolorowania wierzchołków grafu.
Usuwanie kolejnych wierzchołków o najmniejszym stopniu (tworzenie grafów częściowych). Kolorowanie rozpoczynamy od ostatniego usuniętego wierzchołka.
68. Zdefiniuj problem kolorowania wierzchołków grafu.
Znalezienie minimalnej liczby kolorów, którymi należy pokolorować wierzchołki grafu tak, aby żadna para przyległych wierzchołków nie miała tego samego koloru.
69. Podaj przykład zastosowania metody kolorowania wierzchołków grafu.
Kolorowanie mapy politycznej, lokalizacja zespołów pogotowia ratunkowego.
70. Co to jest marszruta w grafie?
Dowolny ciąg przemienny wierzchołków i gałęzi.
71. Co to jest łańcuch w grafie?
Marszruta, w której wszystkie gałęzie są różne
72. Podaj definicję drogi w grafie?
Łańcuch skierowany
73. Podaj definicję drogi prostej w grafie?
Droga o różnych wierzchołkach (przechodzi przez każdy wierzchołek co najwyżej raz)
74. Podaj definicję drogi cyklicznej prostej w grafie?
Droga o różnych wierzchołkach pośrednich, ale wspólnym wierzchołku początkowo-końcowym.
75. Podaj definicję łańcucha prostego w grafie?
Łańcuch o różnych wierzchołkach.
76. Podaj definicję łańcucha cyklicznego prostego w grafie?
Łańcuch o różnych wierzchołkach pośrednich, ale wspólnym wierzchołku początkowo-końcowym.
77. Jaką marszrutą jest droga cykliczna?
Skierowaną, o różnych krawędziach, różnych wierzchołkach pośrednich, wspólnym wierzchołku początkowo-końcowym.
78. Jakim łańcuchem jest droga prosta?
Skierowanym, o różnych wierzchołkach
79. Co to jest łańcuch najkrótszy?
Łańcuch zawierający najmniejsza liczbę gałęzi.
80. Podaj zastosowanie algorytmu znajdowania łańcucha najkrótszego?
81. Kiedy graf jest spójny?
Gdy 2 dowolne wierzchołki można połączyć marszrutą
82. Co to jest składowa spójności grafu?
Każdy maksymalny podgraf będący grafem spójnym.
83. Co to jest składowa silnej spójności grafu?
Każdy maksymalny podgraf będący grafem silnie spójnym.
84. Co oznacza, że graf posiada trzy składowe spójności ?
Istnieją w nim 3 niedające się połączyć marszruty
85. Co to jest łańcuch Eulera?
Łańcuch zawierający wszystkie wierzchołki garu.
86. Co to jest droga Hamiltona?
Droga przechodząca dokładnie raz przez każdy w wierzchołków grafu.
87. Jaka jest różnica pomiędzy drogą Eulera a drogą Hamiltona.
Droga Eulera przechodzi dokładnie raz przez każdą gałąź, droga Hamiltona przez każdy wierzchołek
88. Podaj warunki istnienia łańcucha Eulera.
wszystkie wierzchołki mają parzyste rozwidlenia lub są tylko 2 o rozwidleniach nieparzystych
89. Podaj warunki istnienia drogi Eulera.
- graf jest digrafem
- dla każdego wierzchołka il. Łuków wchodzących i il. Łuków wychodzących są sobie równe lub
- istnieją dwa wierzchołki, dla których te wielkości się różnią o 1
90. Kiedy w grafie istnieje cykliczny łańcuch Eulera?
Gdy wszystkie wierzchołki mają parzyste rozwidlenia
91. Kiedy w grafie istnieje cykliczna droga Eulera?
gdy dla każdego wierzchołka il. Łuków wchodzących i il. Łuków wychodzących są sobie równe
92. Kiedy graf skierowany jest cykliczny w sensie dróg?
Gdy zawiera drogi cykliczne (nie da się rozłożyć na warstwy).
93. Kiedy graf skierowany jest acykliczny w sensie dróg?
Gdy nie zawiera dróg cyklicznych (da się rozłożyć na warstwy).
94. Jakie warunki spełniają wierzchołki warstwy grafu?
1. Do warstwy 0 należą wierzchołki niemające poprzedników
2. każdy wierzchołek ma poprzedniki tylko w warstwach wcześniejszych
3. każdy wierzchołek musi mieć poprzednik w warstwie poprzedzającej.
95. Dla jakich grafów można wyznaczyć jego warstwy? !!!
Acyklicznych w sensie dróg.
96. Jaki podgraf tworzą wierzchołki warstwy grafu? Pusty.
97. Do czego służy algorytm Leifmana?
Do znalezienia wszystkich składowych silnej spójności
98. Czym są wierzchołki grafu Hertza?...
ArchyArch