Lekcja_13 - programowanie dynamiczne1. Programowanie DynamiczneWyjścieProgramowanie dynamiczne1. (1p) Dane są macierze A(10 x 20), B(20 x 100), C(100 x 15), D(15 x 5). Które z ustawień nawiasów gwarantuje minimalny koszt obliczenia iloczynu macierzy A x B x C x D? (A x B) x (C x D) A x (B x (C x D) ) A x ((B x C) x D ( (A x B) x C) x D (A x (B x C)) x D 2.(1p) Na ile możliwych sposobów można umieścić nawiasy w formule, w której występuje jedynie 5 zmiennych zdaniowych i 4 symbole implikacji? 9 20 5^4 4^5 143. (1p) Optymalne nawiasowanie w problemie mnożenia ciągu macierzy można znaleźć z kosztem wielomianowym ze względu na długość ciągu, niezależnie od wymiarów mnożonych macierzy i typu elementów macierzy. tak nie4. (1p) Niech nwp(w,w') oznacza najdłuższy wspólny podciąg ciągów w i w' i niech a, b będą dwoma ustalonymi słowami. Która z wymienionych własności jest prawdziwa, jeżeli wiadomo, że nwp(a,b) = x ? Jeżeli y = nwp(b,c), to nwp(a,c) = xy . Dla dowolnego ciągu c, cx = nwp(ca, cb). 5. (1p) Ile różnych podproblemów można wyróżnić w problemie wyszukiwania najdłuższego wspólnego podciągu ciągów o n i m elementach? min (n, m) O(n+m) Theta(n * m) Theta(n^m) Theta(m^n).6. (1p) Jaki jest koszt znalezienia długości najdłuższego wspólnego podciągu ciągów ababcd i bcd, jeśli zastosowano algorytm podany na wykładzie? 3 porównania 3^2 porównań 12 porównań 18 porównań 36*9 porównańOdpowiedzi do pytań:  Wyniki