Pytania TMO i GiS
Kiedy system masowej obsługi jest stabilny?
Gdy ρ < 1
Kiedy system masowej obsługi nie jest stabilny?
Gdy ρ >= 1
Kiedy system masowej obsługi M/M/n/∞ nie jest stabilny?
Gdy ρ = λ/(nμ) >= 1
Podaj równanie stabilności kolejki dla systemu M/M/4/∞.
ρ = λ/(4μ) < 1
Co to jest stabilność systemu masowej obsługi?
Zjawisko niepowstawania nieskończenie długiej kolejki.
W jaki sposób można poprawić stabilność systemu.
zwiększając ilość stanowisk obsługi
zwiększając szybkość obsługi
zmniejszając ilość klientów
Wymień podstawowe rozkłady losowe stosowane w systemach masowej obsługi?
Jednostajny
Normalny
Wykładniczy
Erlanga
Wymień co najmniej dwa znane ci regulaminy kolejki.
FIFO
FILO
SIRO (losowa kolejność)
Podaj przykład systemu M/M/1/∞.
Stoisko na bazarze z 1 sprzedawcą.
Podaj przykład systemu M/M/1/4.
Sklep z jedną ekspedientką, w którym mieszczą się 4 osoby.
Podaj przykład systemu M/M/2/∞.
Stoisko na bazarze, w którym klientów obsługuje ojciec z córką
Podaj przykład systemu M/M/3/5.
Warsztat samochodowy z trzema stanowiskami i parkingiem na 5 miejsc
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
Na czym polega regulamin kolejki FIFO.
Pierwszy wchodzi => pierwszy wychodzi.
Na czym polega regulamin kolejki LIFO.
Ostatni wchodzi => pierwszy wychodzi (jest obsługiwany)
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
Podaj znaczenie terminu oczekiwanie w systemie masowej obsługi.
Czas od momentu zgłoszenia do chwili rozpoczęcia obsługi
Podaj znaczenie terminu przebywanie w systemie masowej obsługi.
Czas od momentu zgłoszenia do systemu do momentu opuszczenia systemu
Scharakteryzuj parametr oceniający strumień zgłoszeń w SMO.
λ - ilość zgłoszeń w jednostce czasu
Scharakteryzuj parametr oceniający proces obsługi w SMO.
μ - ilość klientów obsługiwanych w jednostce czasu
Co to jest czterokanałowy system masowej obsługi.
System posiadający 4 stanowiska obsługi.
Co to jest wielokanałowy system masowej obsługi.
System posiadający więcej niż jedno stanowisko obsługi.
Podaj wzór na intensywność (natężenie) ruchu w SMO.
ρ = λ/(μ)
Podaj wzór na intensywność (natężenie) ruchu w dwukanałowym SMO.
ρ = λ/(2μ)
Ś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]
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]
Intensywność zgłoszeń do systemu l=12 sam/godz. Jaki jest średni odstęp czasu pomiędzy zgłaszającymi się samochodami.
5 minut.
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
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.
Zapis zbioru wierzchołków w postaci macierzy
Konstrukcja funkcji Boole'wskiej
Znalezienie minimalnej formuły alternatywnej (nie dającej się zredukować)
Określenie baz minimalnych
Określenie maksymalnych podgrafów pustych
Znalezienie pokryć minimalnych.
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 przemienny ciąg gałęzi, parami przyległych. ???????
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?
Do warstwy 0 należą wierzchołki niemające poprzedników
każdy wierzchołek ma poprzedniki tylko w warstwach wcześniejszych
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?
Wierzchołki grafu Hertza symbolizują składowe silnej spójności
99. Czy graf Hertza może być cykliczny?
W sensie dróg - nie; normalnie tak.
100. Wymień etapy algorytmu wyznaczania drogi Hamiltona w grafie.
Wyznaczenie SSS (algorytm Leifmana)
Stworzenie Grafu Hertza
Wyznaczenie warstw grafu Hertza (aby się udało muszą mieć po 1 wierzchoku)
Wyznaczenie drogi Hamiltona w grafie Hertza
„Zszycie” poszczególnych SSS (może się nie udać)
101. O czym informuje liczna cyklomatyczna grafu?
O istnieniu lub nieistnieniu łańcuchów cyklicznych.
102. Co to jest karkas grafu?
Dowolny graf częściowy spełniający 2 z 3 warunków:
m(T)=m(G)-λ(G)
κ(T)=κ(G)
λ(G)=0
103. Co to jest najtańszy karkas grafu? SIECI!!!
Karkas, dla którego suma wartości na jego krawędziach jest najmniejsza.
104. Podaj przykład zastosowania algorytmu wyznaczania drzewa ekonomicznego.
Budowa sieci dróg łączących miasta, budowa sieci połączeń między komputerami.
105. Wymień znane ci algorytmy wyznaczania najtańszego karkasu grafu. SIECI!!!
Algorytm Prima, algorytm Kruskala
106. Co to jest długość drogi łączącej wybrane wierzchołki w grafie?
Ilość gałęzi wchodzących w skład tej drogi
107. Co to jest maksymalny dendryt dróg najkrótszych w grafie?
Spójny digraf i unigraf bez pętli, mający jeden wierzchołek zwany początkiem dendrytu (bez poprzedników) i pozostałe wierzchołki mające po jednym następniku. Drogi od początku dendrytu do poszczególnych wierzchołków są drogami najkrótszymi.
108. Co to jest maksymalny dendryt dróg najdłuższych w grafie?
Spójny digraf i unigraf bez pętli, mający jeden wierzchołek zwany początkiem dendrytu (bez poprzedników) i pozostałe wierzchołki mające po jednym następniku. Drogi od początku dendrytu do poszczególnych wierzchołków są drogami najdłuższymi.
109. Co decyduje o wyborze algorytmu wyznaczania dróg ekstremalnych w sieciach?
skierowanie, lub jego brak
cykliczność lub acykliczność w sensie dróg
110. Wymień etapy algorytmu wyznaczania dróg ekstremalnych w sieciach acyklicznych
Wyznaczenie warstw
Cechowanie wierzchołków leżących w kolejnych warstwach grafu
111. W jakich sieciach możemy stosować metodę dekompozycji przy wyznaczaniu dróg ekstremalnych w sieciach? ??????????????
W sieciach zawierających łuki i krawędzie.
112. Jakim grafem powinna być opisana sieć czynnościowa w metodzie CPM/PERT.
Unigrafem skierowanym, acyklicznym w sensie dróg.
113. Co reprezentuje łuk w metodzie CPM/PERT?
Czynność konieczną do wykonania projektu
114. Czy w metodzie CPM/PERT sieć czynnościowa może być cykliczna? ????
Sieć musi być acykliczna w sensie dróg.
115. Czym jest ścieżka krytyczna w metodzie CPM/PERT?
Drogą najdłuższą pomiędzy rozpoczęciem, a zakończeniem przedsięwzięcia ???????
116. Jak wyznaczamy najwcześniejszy możliwy czas realizacji przedsięwzięcia w metodzie CPM/PERT?
Szukamy ścieżki krytycznej.
117. Co to jest luz czasowy w sieci czynnościowej?
Wartość, o którą może zwiększyć się czas wykonania danej czynności bez wydłużenia czasu realizacji projektu.
118. Ile wynosi luz czasowy na ścieżce krytycznej w metodzie CPM?
0
119. Jakie zapasy czasu wyznacza się w metodzie analizy czynnościowej?
zapas całkowity
zapas swobodny
zapas niezależny
120. Co to jest przepływ w sieci?
Dowolna funkcja określona na zbiorze krawędzi taka, że:
przyjmuje wartości nieujemne
przyjmuje wartości mniejsze od przepustowości
wielkość przepływu wpływającego do danego wierzchołka jest równa wielkości wypływającego
121. Co to jest przepływ zaspokajający w sieci?
Przepływ towarów pomiędzy „magazynami” a „odbiorcami”, który zaspokaja ich zapotrzebowania.
122. Co to jest przepływ zaspokajający o minimalnym koszcie w sieci?
Przepływ towarów pomiędzy „magazynami” a „odbiorcami”, który zaspokaja ich zapotrzebowania i dodatkowo zapewnia minimalizację kosztów transportu..
123. Co to jest wartość przepływu w sieci?
Ilość jednostek przesłanych od źródła do odpływu.
124. Czemu jest równa wartość przepływu maksymalnego w sieci?
Sumie przepustowości gałęzi skierowanych od W1 do W2 przechodzących przez minimalny przekrój rozdzielający.
125. Podaj warunki definiujące przepływ w sieci.
?????????
126. Co to jest ścieżka powiększalna w algorytmie wyznaczania przepływu maksymalnego w sieci?
Droga, na której można zwiększyć przepływ, o tyle jednostek, ile wynosi aktualna (z tego etapu cechowania) druga cecha odpływu.
127. Kiedy przepływ maksymalny w sieci jest przepływem zaspokajającym?
Gdy łuki łączące źródło z magazynami i odbiorców z odpływem są nasycone. (w sieci poszerzonej)
128. Co to są przydziały wzajemnie jednoznaczne?
Przyporządkowanie elementów zbioru A elementom zbioru B w sposób taki, że jednemu elementowi ze zbioru A odpowiada dokładnie jeden element ze zbioru B i odwrotnie.
129. Sformułuj zagadnienie przydziałów?
Przydzielamy kierowców do pojazdów tak, aby każdy pojazd był obsadzony (nie każdy kierowca może jeździć każdym pojazdem)
130. Co to jest tablica oczek dopuszczalnych?
Tablica wykorzystywana w metodzie wyznaczania przydziału najliczniejszego.
131. Co to są niezależne oczka dopuszczalne w algorytmie wyznaczania przydziału najliczniejszego? ???????????????
Oczka takie, że w danym wierszu i kolumnie wybrane jest nie więcej niż jedno oczko
132. Kiedy przerywamy etap cechowania i przechodzimy do zmiany układu jedynek w algorytmie wyznaczania przydziału najliczniejszego?
Podczas sprawdzania kolumny zorientujemy się, że w sprawdzanej kolumnie nie ma jedynki. (gdy ocechujemy kolumnę, w której nie ma jedynki)
133. Kiedy stwierdzamy optymalność rozwiązania w algorytmie wyznaczania przydziału najliczniejszego?
Gdy podczas sprawdzania ocechowanych wierszy nie pojawiła się żadna nowa ocechowana kolumna lub gdy nie jesteśmy w stanie ocechować żadnego wiersza.
134. Kiedy stwierdzamy optymalność rozwiązania w algorytmie wyznaczania przydziału optymalnego z kryterium maxmin?
Gdy wstawienie do tablicy oczka niedopuszczalnego w miejscu wielkości odpowiadającej aktualnej (w danej iteracji) wielkości produkcji (mniejszych) powoduje niemożność wykonania zadania.
135. Kiedy stwierdzamy optymalność rozwiązania w algorytmie wyznaczania przydziału optymalnego z kryterium minmax?
Gdy wstawienie do tablicy oczka niedopuszczalnego w miejscu wielkości czasu odpowiadającej czasowi wykonania zadania (i wszystkich większych) powoduje jego niewykonanie.
136. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego o minimalnym koszcie?
Podział zleceń pomiędzy pracowników o stawkach godzinowych zależnych od rodzaju wykonywanej pracy.
137. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego o maksymalnym zysku?
Podział pracy wśród pracowników przynoszącej różne efekty, dający największy zysk pracodawcy.
138. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego(wąskie gardło) z kryterium minmax?
Minimalizacja czasu pracy grupy pracowników o różnych umiejętnościach wysłanych w kosmos.
139. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego(wąskie gardło) z kryterium maxmin?
Produkcja zestawów elementów, organizacja zabaw dla dzieci (żadne nie powinno się nudzić)
140. Jak zmodyfikować algorytm wyznaczania przydziału optymalnego o minimalnym koszcie aby uzyskać przydział optymalny o maksymalnym zysku?
Pomnożyć wszystkie wartości w tablicy przez -1 i realizować algorytm dokładnie tak, jak dla minimalnego kosztu.
141. Co to jest skojarzenie najliczniejsze w grafie?
??????