Kopia DSC00540

Kierunek: informatyko, studia stacjonarne I stopnia

Wstęp do algorytm izacji, sem.ll    __    .    ■■

4j Rozwiązać równanie rekurencyjne:

(a)    a, = 23b.i ⁺3a*^ z warunkami początkowymi Bo = 1, aj = 1;

(b)    a. “ a», +2a^ z warunkami początkowymi ao = 2, a, = 2

5. Dany jest algorytm dzielenia:

/*Dane: liczby całkowita    i n>0>

Wyniki: liczby całkowi te q i r takie, ta q*» + * ■ a oraz 0 £ r < n) */

<

q - 0 r - »

/» q*n ł x ■ a oraz r2G */ whila (r 2 a) {

« ■ « t ■ r - n >

}

Pokaż, że stwierdzenie q*n + r = m oraz rH) jest niezmiennikiem pętli.

Skorzystaj z twierdzenia o rekurcncji uniwersalnej i podaj dokładne asymptotyczne oszacowanie dla następujących rekurencji;

(a) T(n) - 4T(n/2) + n;

(b) (b) T(n) “ 4T(n/2) + n²;

Zapisz przedstawiony w postaci schematu blokowego algorytm w odpowiadającej mu postaci pscudokodu, (I) z wykorzystaniem iteracji ograniczonej, (2) z wykorzystaniem iteracji nieograniczonej. Czy jest to możliwe w obu przypadkach? Odpowiedź uzasadnij. Co realizuje algorytm? Podaj jego złożoność asymptotyczną O(-).

8. Podaj przykład zbioru nominałów monet fikcyjnej waluty prime, dla której zachłanny algorytm wydawania reszty nie zawsze wydaje resztę w postaci najmniejszej liczby monet.

Wyszukiwarka

Podobne podstrony:
Kopia DSC00539 KJenmelc informatyka, studia stacjonarne l stopnia wstęp do algorytm izucji, sem. //
Kierunek: INFORMATYKA studia stacjonarne I stopnia inżynierskie 3,5-letnie, 7 semestrów specjalności
Wydział Informatyki KIERUNKI STUDIÓW Informatyka -    studia stacjonarne I stopnia -
lista2 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I sto
lista 6 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I st
Kierunek Informatyka, studia stacjonarne Semestr 4: Inżynieria oprogramowania I (6 punktów ECTS) • 3
II ROK PRZEWODNIK DYDAKTYCZNY KIERUNEK PIELĘGNIARSTWO STUDIA STACJONARNE I STOPNIA ROK AKADEMIC
PROJEKT z dnia 22.09.2005 STANDARDY KSZTAŁCENIA kierunek informatyka STUDIA PIERWSZEGO STOPNIA
20855 lista 7 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopn
Wybrane przedmioty kierunkowe - informatyczne Studia pierwszego stopnia (rok II i III) •
WYDZIAŁ ZASTOSOWAŃ INFORMATYKI I MATEMATYKI Kierunki: INFORMATYKA - studia I i II stopnia; INFORMATY
dr inz. Jarosław Forenc 10/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inz. Jarosław Forenc 11/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inz. Jarosław Forenc 12/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inz. Jarosław Forenc 13/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inż. Jarosław Forenc 14/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inż. Jarosław Forenc 15/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki

więcej podobnych podstron