====== AISD - Lista 1. ======
{{:aisd:10.lista01.pdf|Lista 1}}.

===== Zadanie 1. =====
===== Zadanie 2. =====
===== Zadanie 3. =====
Dowód poprawności:
  *$a_1 = a, a_k = 1, a_{i+1} = floor(a_i/2)$. Niech $a = \sum_{i=1}^{k}2^{i-1}\overline a_i, \overline a_k \in \{0,1\}$, czyli zapis $a$ w postaci binarnej. Wtedy $a_n = \sum_{i=1}^{n}2^{i-1}\overline a_{i+(k-n)}$, czyli $a_n = \overline a_k \overline a_{k-1} ... \overline a_{n}$.
  *$b_1 = b, b_{i+1} = 2b_i \Rightarrow b_i = 2^ib$
  *Dowod: $\sum_{i=1, nieparzyste(a_i)}^kb_i = \sum_{i=1}^k \overline a_i 2^i b = b \sum_{i=1}^k 2^i \overline a_i = ab$.

  * kryterium jednorodne - koszt każdej operacji maszyny RAM jest jednostkowy.
  * kryterium logarytmicznym - koszt operacji maszyny RAM jest równy sumie długości operandów.

Mnożymy: $a*b$:
  *Kryterium jednorodne: Tyle dodawań, ile jedynek w zapisie binarnym liczby $b$: $O(ceil(log_2(b)))$
  *Kryterium logarytmiczne: Tyle samo dodawań. Długość operandów: conajmniej $ceil(log_2(a))$, conajwyżej: $ceil(log_2(a*b))$. $O(ceil(log_2(b)) * ceil(log_2(a*b))$.

===== Zadanie 4. =====
Liniowa kombinacja skończonej liczby poprzednich (liczba = $b$). Niech $f_n = a_bf_{n-b} + a_{b-1}f_{n-b+1} + ... + a_1f_{n-1}$. $a_i$ mogą być zerowe lub ujemne. Mając ciąg $(f_{n-1}, f_{n-2}, ..., f_{n-b})$, chcąc otrzymać element $f_n$ oraz móc obliczać kolejne elementy musimy wyliczyć $f_n$ ze wzoru i przeshiftować nasz ciąg.

Macierz:
  * $m_{yx} = 1$ if $ x == y + 1$ else
  * $m_{yx} = 0$ if $ y < n $ else
  * $m_{nx} = a_{n-x+1}$ indeksy jakos tak

Przykład dla $b == 3$:
$\left[\begin{array}{ccc}0&1&0\\0&0&1\\a_3&a_2&a_1\end{array}\right]$

===== Zadanie 5. =====
Macierz jest rozmiaru (n+m) na (n+m), n - ilosc poprzednich wyrazow ciagu rekurencyjnego, m - stopien wielomianu. Podzielmy macierz na cztery prostokaty. Lewy gorny jest taki sam jak w poprzednim zadaniu. Prawy gorny jest zerami, oprocz ostatniego wiersza, ktory jest wspolczynnikami wielomianu. Lewy dolny to zera. Prawy dolny to glowna trudnosc zadania.

Argument i wynik to macierz $(f_1, f_2, \dots, f_n, n^m, n^{m-1}, \dots, 1)^T$ - $f_i$ - wspolczynnik przy wyrazie w wyrazeniu rekurencyjnym (to co w poprzednim zadaniu). Jak uzyskac $(n+1)^i$? Przyklad dla $i = 2$:

$(n+1)^2 = n^2 + 2n + 1$. Czym sa 1, 2 i 1? Kolejnymi wartosciami dwumianu newtona. Dolna prawa czesc macierzy ma takie wiersze:

$\left[\begin{array}{ccc}{n \choose n}&{n \choose n-1}&{n \choose n-2}&\dots&{n \choose 0}\\0&{n-1 \choose n-1}&{n-1 \choose n-2}&\dots&{n-1 \choose 0}\\\dots\\0&0&\dots&0&1 \end{array}\right]$

===== Zadanie 6. =====
===== Zadanie 7. =====
FIXME pesymistyczny koszt dodania to O(n) - uwaga iksa  --- //[[all3@eww.pl|Alistra]] 2010/03/09 22:00//\\
  *Pesymistyczny koszt dodania to O(2*sqrt(n)), i ewentualnie przesuniecie kilku wskaznikow o jeden w przod, +jakies obliczenia +O(sqrt(n)). To jest lista, nie tablica

Mamy liste L. Wizualizujemy w glowie liste jako kwadrat, o boku sqrt(n). Wtedy mozemy zrobic dodatkowa liste o dlugosci sqrt(n) ze wskaznikami na pierwsze elementy kazdej kolumny tego kwadratu. Przy insertowaniu nowego elementu najpierw przechodzimy liste ze wzkaznikami, a potem liste L od wskazywanego miejsca. Maksymalna ilosc przejsc to 2*sqrt(n), jesli insertujemy na koniec. Po wstawieniu nowego elementu musimy odswiezyc liste wskaznikow, co ma koszt sqrt(n).
===== Zadanie 8. =====
[[http://en.wikipedia.org/wiki/Longest_path_problem|http://en.wikipedia.org/wiki/Longest_path_problem]]
<code>
algorithm dag-longest-path is
    input: 
         Directed acyclic graph G
    output: 
         Length of the longest path

    length_to = array with |V(G)| elements of type int with default value 0

    for each vertex v in topOrder(G) do
        for each edge (v, w) in E(G) do
            if length_to[w] <= length_to[v] + weight(G,(v,w)) then
                length_to[w] = length_to[v] + weight(G, (v,w))
 
    return max(length_to[v] for v in V(G))
</code>
{{tag>[listy_zadan]}}