1. Dany jest ciąg macierzy: A1(5 ´10), A2(10 ´ 15), A3(15 ´ 8), A4(8 ´ 4), A5(4 ´ 10).

   • Jaka jest minimalna liczba operacji konieczna do obliczenia iloczynu A1 ´ A2 ´ A3 ´ A4 ´ A5?

   • Podaj optymalny porządek mnożenia dopisując odpowiednie nawiasy.

   • Jaka jest minimalna liczba operacji koniecznych do obliczenia produktu macierzy (A1´A2) ´ (A3´A4´A5)?
      

2. Rozważmy następujący problem: w danym grafie zorientowanym znaleźć ścieżkę prostą (tzn. bez pętli!) między dwoma ustalonymi wierzchołkami składającą się z możliwie największej liczby wierzchołków.  Zbadaj, czy problem najdłuższej ścieżki ma własność podstruktury. Uzasadnij swoją odpowiedź.
    

3. Udowodnij, że liczba drzew binarnych, jakie można utworzyć z n wierzchołków, jest co najmniej rzędu 2ⁿ. Porównaj to zadanie z problemem badania liczby nawiasów w ciągu złożonym z n macierzy.
    

4. Napisz rekurencyjny algorytm generowania wszystkich podciągów danego ciągu. Zbadaj jego koszt.

 

« poprzedni punkt

następny punkt »