Lista cwiczen

7

Zadania z algorytmow śledzenia wstecznego

Napisac pseudokody do programow pracy z wzorcamy.

• Podejście wsteczne do generowania n bitowych kodów Graya
• Napisz program, który wypisze wszystkie permutacje podanego ciągu znaków

Algorytmow śledzenia wstecznego
Backtracking Algorithms

6

Zadania z algorytmow sortowania

Napisac pseudokody do programow pracy z wzorcamy.

• Znaleźć i skasować te same długie słowo w tekście.
  Przykład:
  Dane -
  Rezultat -
  Slowo -
• Znaleźć ile jest liczb w tekście.
  Przykład:
  Dane -
  Rezultat -
  
• Znaleźć te same litery w dwoch wzorach.
  Przykład:
  Wzor 1 -
  Wzor 2 -
  Rezultat -
  
• Wyprowadzić wszystkie nie powtarzające się słowa.
  Przykład:
  Dane -
  Rezultat -
  
• Sprawdzic czy słowo jest anagram.
  Przykład:
  'ranty' i 'tyran' - tak ,
  'ranty' i 'tyban' - nie.

Jak czytac tekst w C

5

Zadania z algorytmow sortowania

Realizacja algorytmow sortowania z wykorzystaniem plika losowych liczb. Ulepszyc generacja losowych liczb (dodanie ujemnydh). Jak mierzyc czas trwania w C

4

Zadania z twierdzenia rekurencji uniwersalnej

Obliczyć następne rekurencji, w których $T(1) = 1$ i $T(n)$ dla $n >= 2$ wynosi:

• $T(n) = 3T(n/2) + n$?
• $T(n) = 3T(n/2) + n^2$?
• $T(n) = 8T(n/2) + n^3$?
• $T(n) = 4T(n/3) + n$?
• $T(n) = 4T(n/3) + n^2$?
• $T(n) = 9T(n/3) + n^2$?

3

Big-O i Big-Omega

• Mamy funkcja $T(n) = 3n^3 + 2n^2$. Czy jest $Θ(n^3)$? Wiezmiemy $n_0=0$ i $c=5$. Wtedy mamy zauważyć ze przy $n>= 0$, $3n^3 + 2n^2 <= 5n^3$. Tak samo możemy twierdzić ze $T(n)$ jest $Θ(n^4)$, ale to słabsze twierdzenie niż $Θ(n^3)$
• Mamy funckja $T(n) = n^3 + 2n^2$. Czy jest $\Omega(n^3)$? Niech $c = 1$. Wtedy $T(n) >= cn^3$ dla $n = 0,1,...$
• $T(n) = 3n^3 + 2n + 7 ∊ Θ(n3)$
  Gdy $n ≥ 1$, then $T(n) = 3n^3 + 2n + 7 ≤ 3n^3 + 2n^3 + 7n^3 = 12n^3$. Stąd $T(n) ∊ O(n^3)$.
  Z drugiej strony, $T(n) = 3n^3 + 2n + 7 > n^3$ dla wszytkich $n > 0$. W związku z tym $T(n) ∊ Ω(n^3)$.
  I konsekwentnie $T(n) ∊ Θ(n^3)$

Zadania

• Czy jest $ 2n+1 ∊ Θ(2n)$?
• Czy jest $(x + y)^2 ∊ Θ(x^2 + y^2 )$?
• Czy jest $ 17 ∊ Θ(1)$?
• Czy jest $ {2(n-1)}/{2} ∊ Θ(n^2)$?
• Czy jest $ max(n^3, 10n^2) ∊ Θ(n^3)$?
• Czy jest $ \sum_{i=1}^{n}i^k ∊ Θ(n^{k+1})$ i $\Omega(n^{k+1})$ dla calkowitych k?

Uporządkuj następujące funkcje według rosnącej

• $n$
• $\sqrt{n}$
• $log{n}$
• $log{log{n}}$
• $log^2{n}$
• ${n}/{log{n}}$
• $\sqrt{n}log^2{n}$
• $(\frac{1}{2})^n$
• $(\frac{3}{2})^n$
• 17

Oblicz złożoność czasową dla każdego fragmentu kodu ćwiczenia.

• 1 function someFunction(n) {
  2       i, j = 0;
  3       for (i; i < n*1000 ; i++) {
  4           for (j; j < n*20; j++) {
  5               printf("%d", i + j);
  6           }
  7       }
  9   }
                      

• 1 function someFunction(n) {
  2       i, j, k, l = 0;
  3       for (i; i < n ; i++) {
  4           for (j; j < n; j++) {
  5               for (k; k < n; j++) {
  6                   for (l; l < 10; j++) {
  7                       printf("%d", i + j + k + l);
  8                   }
  9              }
  10           }
  11       }
  12  }
                      

Notacja Big-O

• 1 function someFunction(n) {
  2       i = 0;
  3       for (i; i < 1000 ; i++) {
  4           printf("%d", i);
  5       }
  6   }
                      

• 1 function someFunction(n) {
  2       i = 0;
  3       for (i; i < n * 10 ; i++) {
  4           printf("%d", i);
  5       }
  6   }
                      

• 1 function someFunction(n) {
  2       i = 0;
  3       for (i; i < n  ; i = i * 2) {
  4           printf("%d", i);
  5       }
  6   }
                      

• 1 function someFunction(n) {
  3       while (true) {
  4           printf("%d", n);
  5       }
  6   }
                      

2

Formatowanie MD / Basic writing and formatting syntax Markdown-Tutorial

Pseudokod i udowodnienie ze jest częściowo poprawny.
Udowodnienia częściowej i całkowitej poprawności algorytmu sumy tablicy c liczbami metoda iteracji pętli
Przykład udowodnienia częściowej i całkowitej poprawności algorytmu sumy ciągu z liczbami metoda matematycznej indukcji.

• Silnia(factorial) wiki
• Iloczyn i reszta. Realizacja z warunkem pocztkawym calkowita liczba - n, wyjsce licby(lista) - q i r wiki wiki
• NWD wiki
• Srednia arytmetyczna wiki
• Wyszukiwanie maksimum (minimum) w tablice liczb naturalnych (dwa odrobnych pseudokoda)

1

• 1 napisac program ktora pyta ilosc dni w miasacu i dzisieszy dzien. Wyprowadza ile zostalo dni do konca miesiaca.
• 2 napisac program ktory obliza jakegu roku urodzenia i jaki teraz jest rok. Wyporwadza ile lat uzytkowniku.
• 3 dana calkowita liczba k (1 <= k <= 180) i ciag lizcb 10111213..9899, do ktorego sa zapisane wszytkie dwoznakowe liczby. Wyznaczyc numer pary liczb, to ktorej wpada liczba k
• 4 liczba naturalna z n cyfr jst liczba Armstronga, jezelu suma jego liczb w pierwaztku n, jest rowna samej liczbie. Naprzyklad, 153 = 1^3 + 5^3 + 3^3. Napisac program otrzymania wszykich liczb Armstronga, z 3 i 4 liczb.
• opisz liste jedno- i dwukierunkow, oraz cykliczne
• 5 podaj pseudokod klas listy jedno- i dwukierunkowej
• napisz pseudokod prostych funkcji operujcych na powyszych (np. dodaj element na komcu listy, zwró¢ liczbe elementów)
• porównaj zalety i wady list dowiazaniowych i tablic
• zaimplementuj kolejka i stos zarówno na liscie dowiazaniowej, jak i na tablicy, dokonaj porównawcznej analizy tych implementacji (inne wady/zalety)
• zaprojektuj i zaimplementuj abstrakcyjne struktur danych bedace kolejk z dodatkowe szybk¡ operacje odwracania kolejnoci.

Na glówna