-
Anonim
Mam pytanko zdawal ktos moze egzamin z ASD w sesji letniej(to chyba byly wieczorowe)?? Trudne bylo??Duzo ludzi uwalilo?? A moze ktos ma zadania to niech wrzuci. Musze podejsc do poprawki zanim sie obronie i ccialbym wiedziec jak to w tym roku wygladalo, w tamtym na poprawce u wieczorowych podobno robilo sie co sie chcialo lacznie z przepisywaniem z wielkich ksiazek na beszczela.
pozdro -
#21 Maliniak
Tez mnie to czeka :))))) Ktory to juz raz hehehe; PPP
Ostatnio byly zadania z trescia, czy testy? -
Anonim
no w sesji zimowej byly same z trescia i byl sajgon straszny w pierwszym terminie chyab 90%uwalilo ja pisalem poprawke i tez byly same tekstowki niby nie takie tragiczne ale i tak uwalilem bo sie nie uczylem nic do tego shitu;-) a wlasnie zeby ktos napisal jak bylo na wieczorowce teraz.
pozdro -
Anonim
Ja zdawałem, kupa piszących była i cały batalion pilnujących :/
a teraz taa-daa treści zadań:
1.(2+2+1)
(a) Koszt pewnego algorytmu A można oszacować przez funkcję T(n), gdzie n jest rozmiarem danych. Jeśli n
jest potęga 2, np.n=2k(lub T), to funkcję T można przedstawić następującym równaniem rekurencyjnym:
T(2)=1, T(2k+1)=2*T(2k)+1
Jaki jest koszt tego algorytmu: liniowy, kwadratowy, liniowo logarytmiczny czy wykładniczy
(b)Jeżeli algorytm B, którego koszt T(a) wyraża się funkcją kwadratową 2n2 wykonuje na pewnym komputerze
zadanie o rozmiarze 10 w czasie 10s, to w jakim czasie ten algorytm wykona 100 razy większe?
(c)Jeżeli wykonamy algorytm B na komputerze 100 razy szybszym, to ile czasu zajmie wykonanie zadania o
rozmiarze 100?
2.Rozważmy następujący algorymt:
int COTO (int y, int n) {
if (n=0) then return 0 fi; if (n=1) then return y fil
if (n mod 2 = 0) then return COTO(y+y, n/2) else return COTO (y+y, n/2)+y; fi
}
(a)Jak zwracany wynik funkcji COTO zależy do n i y?
(b)Oszacuj, możliwie najdokładniej koszt czasowy tego algorytmu stosując notacjąO.
(c) Ile razy zostanie rekurencyjnie wywołana funkcja COTO dla n=512 i y=100?
3. Dla dowolnego n i k, n>=k, współczynnik dwumianowy Newtona (n//k) wyraża się wzorem (n//k)=n!/(k!(n-
k)!). Wiedząc, że (n//k)=(n-1//k-1), możemy zdefiniować następującą funkcję rekurencyjną P(i,j)
pozwalający obliczyć dowolny współczynnik Newtona:
P(n,n)=1, P(n,0)=1, dla dowolnego n naturalnego, P(n,k)=P(n-1,k) + P(n-1,k-1) dla n>=k
Zadanie właściwe:
(a)Napisz algorytm, który dla dowolnie danych n i k odpowiada na pytania, czy liczba P(n,k) jest parzysta czy
nieparzysta
(b)Wyjaśnij ideę działania Twojego algorytmu.
(c)Oszacuj jego koszt
-
-
Anonim
4.Przedstaw kolejne etapy tworzenia drzewa BST w wyniku kolejnego wstawienia elementów: 4,6,1,5,7,8 do
początkowo pustego drzewa BST (zakładamy, ze zastosowano algorytm insert)
(b)Czy jest to drzewo wyważone? Odpowiedź uzasadnij.
(c) Przedstaw kolejne etapy tworzenia drzewa AVL przez kolejne wstawianie (algorytm insert dla AVL)
elementów 6,4,1,5,7,8 do początkowow pustego drzewa
(d)Porównaj koszt wstawienia jednego elementu do drzewa BST o n elementach i koszt wstawienia jednego
elementu do drzewa AVL o n elementach
5.Dany jest graf niezorientowany G, którego wierzchołkami są liczby naturalne 1,2,3,4,5,6,7, a krawędzie, to zbiór
par (x,y) takich, że (x+y_ mod 3 >0.
(a)Przedstaw ten graf w postaci macierzowej wiedząc, żę waga krawędzi (x,y) wynosi w(x,y)=(x+y)mod3.
(b)Ile miejsca zajmie zakodowanie macierzy tego grafu, jeśli użyjemy kodu ASCII?
(c)Znajdź drzewo kodu prefiksowego Huffmana. Przedstaw etapy tworzenia drzewa kodowego.
(d)Ile miejsca zajmie zakodowanie tej macierzy, jeśli do zakodowania użyjemy znaleziony kod Huffmana
6.Niech będzie dany graf G przedstawiający sieć dróg między miastami A,B,C,D,E,F. Na każdej krawędzi
zaznaczono długość odpowiadającej jej drogi.
(a)Zapisz graf G w postaci tablicy list incydencji.
(b)Znajdź najkrótszą drogę z miasta A do miasta D (Przez jakie wierzchołki przechodzi i jaki jest jej
koszt). Opisz zastosowaną metodę postępowania i przedstaw kolejne kroki działania algorytmu.
(c)Jeśli wykonano polecenie w punkcie (b), to jaki będzie koszt znalezienia najkrótszej drogi z A do C?
7.Pewnien zbiór miast, oznaczonych literami 1,2,3,4,5,6,7 chcemy połączyć autostradami w taki sposób aby z
dowolnego miasta można było przejechać korzystając tylko z autostrad, do dowolnego innego. Dla każdej pary
miejscowości x,y, koszt wykonania autostrady, która by je połączyła bezpośrednio wynosi (x+y)mod 5+1.
Przedsiębiorstwo AUTOSTRADA, wykonuje całość zadania, chce wybudować autostrady w taki sposób, by
koszt całego przedsięwzięcia był jak najmniejszy. Problem polega na tym jak wybrać miejscowości, które
powinny być bezpośrednio połączone.
Zadanie właściwe:
(a)Zaproponuj metodę postępowania, która pozwoli rozwiązać ten problem.
(b)Przedstaw kolejne etapy działania zaproponowanego algorytmu.
(c)Narysuj otrzymaną sieć autostrad i oblicz koszt jej budowy.
8.Pewnien zbiór X złożony z n elementów zapisano w tablicy.
(a)Oszacuj możliwie najlepiej koszt sekwencyjnego wyszukiwania dowolnego elementu w tym zbiorze
(b)Załóżmy, że elementy zbioru zostały wpisane do tablicy w porządku rosnącym. Opisz ideę optymalnego
algorytmu wyszukiwania dowolnie wskazanego elementu. Jaki jest jego koszt?
-
Anonim
wiem, wiem, jestem wielki :P:P:P
ale tam gdzieś jest rysunek, którego Wam nie wkleje z wiadomych przyczyn -
zxc
A ma ktoś może rozwiązania do tych zadań?
Malin => kiedy w końcu się spotkamy by się tego z Łukaszem pouczyć??? -
#21 Maliniak
-
Anonim
-
Anonim
@Maruś jestes wielki, niech ci Bozia w dzieciach za to wynagrodzi, a powiedz jak wyniki?duzo ludzi uwalilo??moze w sieci gdzies sa to bym zerknal chetnie.
pozdro
kaczy -
Anonim
Sporo osób uwaliło, z mojej grupy to z 60-70% ale ogólnie to nie wiem jaki odsetek.
Też nie wiem czy wyniki są w sieci.
Bóg z Tobą. -
zxc
-
Anonim
mArIkA - to co wkleiłem to treści zadań z egzaminu który pisałem dwa miesiące temu - jestem świeżo po ASD i też mam poprawkę :(
-
L
Qrwa tez mnie to czeka, ale chyba znowu to odloze do przyszlej sesji:) -
#21 Maliniak
-
zxc
Malin -> ja chyba nie przejde przez ta sesje... jestem wolna od dzis do poniedzialku.. w tygodniu od 17:00 .. zdzwon sie z Łukaszem niech z ustawi z nami bo bedzie ciezko... i znowu sie okaze ze nam 1,5 pkt zabraknie! -
L
-
zxc
-
zxc
-
#21 Maliniak
- Przeglądaj grona w kategorii Szkoły i Edukacja
- Przeglądaj grona w okolicy Warszawa - Śródmieście
- Załóż własne grono tematyczne
|
|
Grono studentow, milosnikow, absolwentow, wykladowcow, cwiczeniowcow, rektorow, ochrony, sprzataczek...
Polsko -Japońska Wyższa Szkoła Technik Komputerowych
Grona tematyczne:
Fotki
Miejsca grona (5)
-
Lucid Klub Aleje jerozolimskie 179 (Piętro 4), Warszawa
-
Opium Club Wierzbowa 9/11, Warszawa
-
RETRO Kolejowa 8/10, Warszawa
-
The Shot Polna, Warsaw
-
PJWSTK Koszykowa, Warszawa
- Dodaj miejsce