Mogą być powypisywane głupoty. Nie wiem, czy pytania się powtórzą - powinny być podobne. Mógłby sobie ktoś z piszących zerówkę parę pytań spróbować przypomnieć..
Rozwiązań poprawnych nie jestem w stanie podać na dzisiejszy dzień :].

Przybliżenie asymptotyczne funkcji:
- jest funkcją zbieżą do tej funkcji
- nieskończonym rozwinięciem tej funkcji
- zawiera skończoną liczbę wyrazów tej funkcji

Zdanie (które jest prawdziwe ?):
- małe tw. Fermata 2^(m-1) = 1 (mod m) dla każdego m?
- relacja kongruencji jest przechodnia?
- działanie mnożenia jest jest rozłączne w zbiorze 2p z działaniem *p
n + pm = (nm) mod p wtedy i tylko wtedy, gdy (mn) mod p = m mod p *p n mod p (???)
- podłoga(xy) = podłoga(x)podłoga(y)
podłoga(x+y) = podłoga(x) + podłoga(y)
- na podstawie algorytmu dzielenia można obliczyć resztę z dzielenia

Graf Berge'a:
- w łańcuchu Hamiltona muszą występować wszystkie łuki i pętle grafu
- w drodze Eulera muszą występować wszystkie łuki i pętle grafu
- wierzchołki grafu pokolorowanego nie są przyległe
- każda permutacja zbioru wierzchołków reprezentowana jest odpowiednim ciągiem krawędzi

Prawdziwe jest zdanie:
- sieć PERT jest siecią acykliczną
- drzewo karkas ekonomiczne zawiera wszystkie te krawędzie które mają największe wartości
- nie można zwiększyć wartości przepływu jeśli w sieci istnieje łańcuch powiększalny
- dwie liczby całkowite przystają do siebie <=> ich iloczyn jest podzielny przez modulnik

Dla grafu zwykłego
- łańcuch Hamiltona zawiera wszystkie krawędzie grafu
- każda baza minimalna odpowiada wektorowi minimalnemu pewnej funkcji boolowskiej
- jądro grafu jest zbiorem wewnętrznie stabilnym
- każdemu łańcuchowi Hamiltona odpowiada kod Gray'a
- graf jest permutacją zbioru wierzchołków

Zdanie:
- długość drogi w sieci jest równa sumie długości łuków wchodzących w skłąd tej drogi
- wartość ptrzepływu nie może być większa od przepustowości dowolnego łuku w grafie
- jądro grafu jest zbiorem wewnętrznie stabilnym
- w metodzie PERT wyznaczane są drogi najkrótsze

Zdanie:
- f(n) = O(g(n)) oznacza równość obu stron
- O(f(n)) + O(g(n)) = O(f(n) + g(n))
- O(O(f(n))) = O(f(n))
- nie jest prawdziwe f(n) = O(g(n)) => O(g(n)) = f(n)

Zdanie:
- algorytm Euklidesa oblicza NWD wyłącznie dla liczb względnie pierwszych
- nie można rozwiązać układu kongruencji rozpatrywanego na wykładzie jeśli modulniki nie są liczbami względnie pierwszymi
- zmodyfikowany algorytm Euklidesa jest jego dostosowaniem do liczb pierwszych

Dla grafu Berge'a:
- metodę minimalizacji monotonicznych funkcji boolowskich stosuje się przy wyznaczaniu zb. maksymalnych
- jądro grafu jest zbiorem zewnętrznie stabilnym
- każda baza jest dopełnieniem zbioru wewnętrznie stabilnego do zbioru wierzchołków
- każdej permutacji zb. wierzchołków odpowiada cykl Hamiltona
- droga Eulera musi być cyklem

Zdanie:
- droga ekstremalna w sieci nie zawiera powtarzających się wierzchołków
- ścieżka krytyczna w układzie PERT jest drogą najkrótszą
- każdy przydział optymalny w sieci jest przydziałem najliczniejszym

Zdanie:
- iloczyn funkcji tworzących jest funkcją tworzącą splotu ciągów
- całkowaniu funkcji tworzących odpowiada całkowanie ciągu
- sumie ciągów odpowiada iloczyn ich funkcji tworzących
- podzielenie funkcji tworzącej przez z^3 odpowiada przesunięciu ciągu o 3 w lewo

Zdanie:
- sufit(x + y) = sufit(x) + sufit(y)
- dla każdego n działanie dodawania jest rozłączne w zbiorze z działaniem +p
- relacja kongruencji jest relacją równoważności
- na podstawie twierdzenia zwanego algorytmem dzielenia można obliczyć ile razy dzielnik mieści się w dzielnej

Zdanie:
- dwie liczby całkowite przystają <=> iloczyn podzielny przez modulnik
- z twierdzenia zwanego algorytmem dzielenia wynika, że istnieje dokładnie jedno rozwiązanie (q,r) równania diofantycznego 129 = 11q + r spełniające zależność 0<r<=11

Kiedy dwie liczby są ze sobą w < (to śmiesznie wygięte <):
- mają te same znaki
- granica iloczynu funkcji dąży do zera
- logarytmy funkcji są w hierarchii
- moduł pierwszej rośnie szybciej niż moduł drugiej pomnożonej przez stałą
- odwrotności są w relacji w odwrotnej

Czy ktos juz cokolwiek z tego zrobil? Jak tak to niech wrzuci odpowiedzi.

zadanie:
Przybliżenie asymptotyczne funkcji:
- jest funkcją zbieżą do tej funkcji
- nieskończonym rozwinięciem tej funkcji
- zawiera skończoną liczbę wyrazów tej funkcji

Pogrubione prawdziwe: (oczywiście nie na pewno)

Dla grafu zwykłego
- łańcuch Hamiltona zawiera wszystkie krawędzie grafu
- każda baza minimalna odpowiada wektorowi minimalnemu pewnej funkcji boolowskiej na pewno w drugą stronę tak - każdy wektor minimalny odpowiada bazie minimalnej
- jądro grafu jest zbiorem wewnętrznie stabilnym
- każdemu łańcuchowi Hamiltona odpowiada kod Gray'a
- graf jest permutacją zbioru wierzchołków

Kiedy dwie liczby są ze sobą w < (to śmiesznie wygięte <):
- mają te same znaki
- granica iloczynu funkcji dąży do zera
- logarytmy funkcji są w hierarchii
- moduł pierwszej rośnie szybciej niż moduł drugiej pomnożonej przez stałą
- odwrotności są w relacji w odwrotnej kolejności

Zdanie (które jest prawdziwe ?):
małe tw. Fermata 2^(m-1) = 1 (mod m) dla każdego m? nie tylko dla m pierwszych
- relacja kongruencji jest przechodnia? jest nawet relacją równoważności
działanie mnożenia jest jest rozłączne w zbiorze 2p z działaniem *p
- podłoga(xy) = podłoga(x)podłoga(y)
-podłoga(x+y) = podłoga(x) + podłoga(y)
- na podstawie algorytmu dzielenia można obliczyć resztę z dzielenia

ktore zdania sa prawdziwe:
- iloczyn funkcji tworzących jest funkcją tworzącą splotu ciągów
- całkowaniu funkcji tworzących odpowiada całkowanie ciągu
- sumie ciągów odpowiada iloczyn ich funkcji tworzących
- podzielenie funkcji tworzącej przez z^3 odpowiada przesunięciu ciągu o 3 w lewo

Zdanie:
- sufit(x + y) = sufit(x) + sufit(y)
- dla każdego n działanie dodawania jest rozłączne w zbiorze z działaniem +p
- relacja kongruencji jest relacją równoważności
- na podstawie twierdzenia zwanego algorytmem dzielenia można obliczyć ile razy dzielnik mieści się w dzielnej

Podobno te zadania pojawily sie na poprawie MD w zeszlym roku na wykładzie. Podajcie jak najszybciej rozwiazania! JAk macie jakies inne cynki to podajcie!



W grafie Kőniga:
-wierzchołek x występuje przed wierzchołkiem x w konstruowanym łańcuchu powiększanym i jest on poprzednikiem wierzchołka y
-Wyznaczenie maksymalnego przepływu zero jedynkowego jest niemożliwe
-Rozwidlenie wierzchołka w łańcuchu Eulera jest możliwe <=> gdy jest to cykl nieograniczony
-liczność wierzchołków jest mniejsza niż liczność przydziału


Które zdanie jest prawdziwe:
- O(f(n))+O(g(n)) jest nieokreślony
- nieprawdą jest że f(n)=O(g(n)) => O(g(n))=f(n)
- O(O(f(n)))=O(f(n))
- f(n)=O(g(n)) oznacza równość stron
- O(f(n))+O(g(n))=O(f(n)+g(n))

W przekształceniu MFA:
- każdy iloczyn odpowiada minimalnemu pokryciu
- każdy iloczyn odpowiada maksymalnemu pokryciu
- ilość podziału wierzchołków grafu odpowiada pokryciu najmniej licznemu
- występuje łańcuch cykliczny prosty


Które zdanie jest prawdziwe:
- kombinacja liniowa funkcji tworzących odpowiada kombinacji liniowej ciągów
- pomnożenie funkcji tworzącej o z^3 powoduje przesuniecie ciągu o trzy miejsca w lewo
- splot funkcji tworzących jest funkcja tworzącą iloczynu ciągów
- pomnożenie funkcji tworzącej o z^3 powoduje przesuniecie ciągu o trzy miejsca w prawo

Które zdanie jest nieprawdziwe?:
- cykl Hamiltona zawiera wszystkie gałęzie grafu
- prosta droga ekstremalna w sieci zawiera powtarzające się elementy
- karkas musi zawierać powtarzające się elementy
- różniczkowanie funkcji tworzących odpowiada różniczkowaniu ciągu

Niestety nie wszystkie jestem w stanie ocenić. Prosze o weryfikację:

W grafie Kőniga:
-wierzchołek x występuje przed wierzchołkiem x w konstruowanym łańcuchu powiększanym i jest on poprzednikiem wierzchołka y
-Wyznaczenie maksymalnego przepływu zero jedynkowego jest niemożliwe (-)
-Rozwidlenie wierzchołka w łańcuchu Eulera jest możliwe <=> gdy jest to cykl nieograniczony
-liczność wierzchołków jest mniejsza niż liczność przydziału


Które zdanie jest prawdziwe:
a) O(f(n))+O(g(n)) jest nieokreślony (-)
b) nieprawdą jest że f(n)=O(g(n)) => O(g(n))=f(n) (+)
c) O(O(f(n)))=O(f(n)) (+)
d) f(n)=O(g(n)) oznacza równość stron (-)
e) O(f(n))+O(g(n))=O(f(n)+g(n)) (-)

W przekształceniu MFA:
- każdy iloczyn odpowiada minimalnemu pokryciu (+)
- każdy iloczyn odpowiada maksymalnemu pokryciu (-)
- ilość podziału wierzchołków grafu odpowiada pokryciu najmniej licznemu
- występuje łańcuch cykliczny prosty


Które zdanie jest prawdziwe:
a) kombinacja liniowa funkcji tworzących odpowiada kombinacji liniowej ciągów (+)
b) pomnożenie funkcji tworzącej o z^3 powoduje przesuniecie ciągu o trzy miejsca w lewo(-)
c) splot funkcji tworzących jest funkcja tworzącą iloczynu ciągów (-)
d) pomnożenie funkcji tworzącej o z^3 powoduje przesuniecie ciągu o trzy miejsca w prawo(+)

Które zdanie jest nieprawdziwe?:
a) cykl Hamiltona zawiera wszystkie gałęzie grafu (+)
b) prosta droga ekstremalna w sieci zawiera powtarzające się elementy (+)
c) karkas musi zawierać powtarzające się elementy(+)
d) różniczkowanie funkcji tworzących odpowiada różniczkowaniu ciągu (-)

Albireo napisał/a:

Które zdanie jest nieprawdziwe?: a) cykl Hamiltona zawiera wszystkie gałęzie grafu (+) b) prosta droga ekstremalna w sieci zawiera powtarzające się elementy (+) c) karkas musi zawierać powtarzające się elementy(+) d) różniczkowanie funkcji tworzących odpowiada różniczkowaniu ciągu (-)

Nieprawdziwe. To chyba jest źle, co? Ja bym właśnie d) zaznaczył. I a), bo wnioskując z innych odpowiedzi a) zachodzi dla ciągu spójnego ;)

<sciana>Masz rację, dzięki za zwrócenie na to uwagi
Już nie mogę na to patrzeć

Przybliżenie asymptotyczne funkcji:
- jest funkcją zbieżną do tej funkcji (T)
- nieskończonym rozwinięciem tej funkcji (N)
- zawiera skończoną liczbę wyrazów tej funkcji (T)

Zdanie (które jest prawdziwe ?):
- małe tw. Fermata 2^(m-1) = 1 (mod m) dla każdego m? (N)
- relacja kongruencji jest przechodnia? (T)
- działanie mnożenia jest jest rozłączne w zbiorze 2p z działaniem *p
n + pm = (nm) mod p wtedy i tylko wtedy, gdy (mn) mod p = m mod p *p n mod p (N)
- podłoga(xy) = podłoga(x)podłoga(y)
- podłoga(x+y) = podłoga(x) + podłoga(y) (N)
- na podstawie algorytmu dzielenia można obliczyć resztę z dzielenia (T)

Graf Berge'a:
- w łańcuchu Hamiltona muszą występować wszystkie łuki i pętle grafu (N)
- w drodze Eulera muszą występować wszystkie łuki i pętle grafu (T)
- wierzchołki grafu pokolorowanego nie są przyległe (N)
- każda permutacja zbioru wierzchołków reprezentowana jest odpowiednim ciągiem krawędzi (N)

Prawdziwe jest zdanie:
- sieć PERT jest siecią acykliczną (T)
- drzewo karkas ekonomiczne zawiera wszystkie te krawędzie które mają największe wartości (N)
- nie można zwiększyć wartości przepływu jeśli w sieci istnieje łańcuch powiększany (N)
- dwie liczby całkowite przystają do siebie <=> ich iloczyn jest podzielny przez odmulnik (N)

Dla grafu zwykłego
- łańcuch Hamiltona zawiera wszystkie krawędzie grafu (N)
- każda baza minimalna odpowiada wektorowi minimalnemu pewnej funkcji boolowskiej (T)
- jądro grafu jest zbiorem wewnętrznie stabilnym (T)
- każdemu łańcuchowi Hamiltona odpowiada kod Gray'a (T)
- graf jest permutacją zbioru wierzchołków (N?)

Zdanie:
- długość drogi w sieci jest równa sumie długości łuków wchodzących w skłąd tej drogi (T)
- wartość przepływu nie może być większa od przepustowości dowolnego łuku w grafie (T)
- jądro grafu jest zbiorem wewnętrznie stabilnym (T)
- w metodzie PERT wyznaczane są drogi najkrótsze (?) N

Zdanie:
- f(n) = O(g(n)) oznacza równość obu stron (N)
- O(f(n)) + O(g(n)) = O(f(n) + g(n)) (N)
- O(O(f(n))) = O(f(n)) (T)
- nie jest prawdziwe f(n) = O(g(n)) => O(g(n)) = f(n) (T)
- O(f(n))+O(g(n)) jest nieokreślony (N)

Zdanie:
- algorytm Euklidesa oblicza NWD wyłącznie dla liczb względnie pierwszych (N)
nie można rozwiązać układu kongruencji rozpatrywanego na wykładzie jeśli modulniki nie są liczbami względnie pierwszymi (T)
- zmodyfikowany algorytm Euklidesa jest jego dostosowaniem do liczb pierwszych (N)

Dla grafu Berge'a:
- metodę minimalizacji monotonicznych funkcji boolowskich stosuje się przy wyznaczaniu zb. maksymalnych (N)
- jądro grafu jest zbiorem zewnętrznie stabilnym (T)
- każda baza jest dopełnieniem zbioru wewnętrznie stabilnego do zbioru wierzchołków (T)
- każdej permutacji zb. wierzchołków odpowiada cykl Hamiltona (N)
- droga Eulera musi być cyklem (N)

Zdanie:
- droga ekstremalna w sieci nie zawiera powtarzających się wierzchołków (N)
- ścieżka krytyczna w układzie PERT jest drogą najkrótszą (?) T
- każdy przydział optymalny w sieci jest przydziałem najliczniejszym (?) T

Zdanie:
- iloczyn funkcji tworzących jest funkcją tworzącą splotu ciągów (T)
- całkowaniu funkcji tworzących odpowiada całkowanie ciągu (N)
- sumie ciągów odpowiada iloczyn ich funkcji tworzących (N)
- podzielenie funkcji tworzącej przez z^3 odpowiada przesunięciu ciągu o 3 w lewo (N)

Zdanie:
- sufit(x + y) = sufit(x) + sufit(y) (N)
- dla każdego n działanie dodawania jest rozłączne w zbiorze z działaniem +p (T?)
- relacja kongruencji jest relacją równoważności (T)
- na podstawie twierdzenia zwanego algorytmem dzielenia można obliczyć ile razy dzielnik mieści się w dzielnej (T)

Zdanie:
- dwie liczby całkowite przystają <=> iloczyn podzielny przez odmulnik (N)
- z twierdzenia zwanego algorytmem dzielenia wynika, że istnieje dokładnie jedno rozwiązanie (q,r) równania diofantycznego 129 = 11q + r spełniające zależność 0<r<=11 (N)

Kiedy dwie liczby są ze sobą w < (to śmiesznie wygięte <):
- mają te same znaki (N)
- granica iloczynu funkcji dąży do zera (N)
- logarytmy funkcji są w hierarchii (T)
- moduł pierwszej rośnie szybciej niż moduł drugiej pomnożonej przez stałą (N)
- odwrotności są w relacji w odwrotnej kolejności (T)


Które zdanie jest prawdziwe:
a) pomnożenie funkcji tworzącej o z^3 powoduje przesuniecie ciągu o trzy miejsca w prawo (T)
b) pomnożenie funkcji tworzącej o z^3 powoduje przesuniecie ciągu o trzy miejsca w lewo (N)
c) splot funkcji tworzących jest funkcja tworzącą iloczynu ciągów (N)
d) kombinacja liniowa funkcji tworzących odpowiada kombinacji liniowej ciągów (T)

Które zdanie jest prawdziwe:
a) z małego twierdzenia Fermata wynika że n^4=~ 1(mod5) dla n?k*5 (T?)
b) chińskie twierdzenie o resztach nie ma zastosowania gdy niektóre odmulniki nie są względnie pierwsze (T)
c) Podstawowe Twierdzenie Arytmetyki podaje przepis na przedstawienie liczby jako iloczynu potęg liczb pierwszych (N)

Dla /*ciągu*/ grafu spójnego prawda jest, że:
a) cykl Hamiltona zawiera wszystkie gałęzie graf (N)
b) zbiór wewnętrznie stabilny nie zawiera wierzchołków przyległych (T)
c) każdemu maksymalnemu zbiorowi zewnętrznie stabilnemu odpowiada wektor minimalny dla określonej funkcji boolowskiej (N)

Dla sieci prawdą jest, że:
a) prosta droga ekstremalna w sieci nie zawiera powtarzających się wierzchołków (T)
b) przydział minimaksowy generuje najliczniejszy przydział w sieci (?)
c) drzewo (karkas) ekonomiczne nie musi zawierać powtarzających się wierzchołków (N)

Które zdanie jest nieprawdziwe?:
a) cykl Hamiltona zawiera wszystkie gałęzie grafu (+)
b) prosta droga ekstremalna w sieci zawiera powtarzające się elementy (+)
c) karkas musi zawierać powtarzające się elementy(+)
d) różniczkowanie funkcji tworzących odpowiada różniczkowaniu ciągu (+)

Zdanie (które jest prawdziwe ?):
- małe tw. Fermata 2^(m-1) = 1 (mod m) dla każdego m? (N)
- relacja kongruencji jest przechodnia? (T)
- działanie mnożenia jest jest rozłączne w zbiorze 2p z działaniem *p
n + pm = (nm) mod p wtedy i tylko wtedy, gdy (mn) mod p = m mod p *p n mod p (N)
- podłoga(xy) = podłoga(x)podłoga(y) (N)
- podłoga(x+y) = podłoga(x) + podłoga(y) (N)
- na podstawie algorytmu dzielenia można obliczyć resztę z dzielenia (T)

Jak jest w końcu z tymi karkasami? (myślę, że tego nie będzie, pytam tak na wszelki wypadek): wydaje mi się, że wierzchołki nie muszą się w nich powtarzać.

I druga wątpliwość - czy mnożenie i dodawnie są rozłączne w zbiorach odpowiednio 2p z działaniem *p i +p ?

plastek85 napisał/a:

zadanie: Przybliżenie asymptotyczne funkcji: - jest funkcją zbieżą do tej funkcji - nieskończonym rozwinięciem tej funkcji - zawiera skończoną liczbę wyrazów tej funkcji

Przybliżenie asymptotyczne funkcji NIE jest funkcją zbieżą do tej funkcji !!!

Dopiero na egzaminie sie dowiedzialem, bo sam zle zaznaczylem

eL_Lechu napisał/a:

Przybliżenie asymptotyczne funkcji: - jest funkcją zbieżną do tej funkcji (T) ...

Wlasnie ze nie jest !!! Tak mi powiedzial pan Chojancki na egzaminie...

Cytat:

Zdanie: - droga ekstremalna w sieci nie zawiera powtarzających się wierzchołków (N) - ścieżka krytyczna w układzie PERT jest drogą najkrótszą (?) T - każdy przydział optymalny w sieci jest przydziałem najliczniejszym (?) T

Tutaj chyba jest błąd - znalazłem odnośnie sieci PERT w "Wprowadzenie do algorytmów" WNT (Thomas H. Cormel i inni) takie zdanie: "Ścieżką krytyczną nazwywamy najdłuższą ścieżkę dagu." str 605 - jak ktoś sam chce sprawdzić... (dag - directed acyclic graph - acykliczny graf skierowany)

mam 2 pytania, bo wcześniej widzę rozbieżne odpowiedzi...
1. czy droga ekstremalna w sieci zawiera powtarzające się elementy ?
2. czy karkas musi zawierać powtarzające się elementy

---