Lekcja_10 - metoda zachłanna1. Algorytmy ZachłanneWyjścieAlgorytmy Zachłanne1. (1p) Ile wierzchołków ma drzewo kodowe optymalnego kodu prefiksowego Huffmana dla tekstu składającego się z 3000 znaków, w którym użyto tylko 26 różnych znaków. 26 51 3000 3000* 26 26 + 272. (1p) Pewien tekst wykorzystuje tylko 7 znaków, a ich częstości występowania tworzą pierwsze siedem wyrazów ciągu Fibonacciego. Jaka jest długość tekstu po zakodowaniu optymalnym kodemu prefiksowym Huffmana ? 5 *33 bitów 78 bitów 7* 8 bitów 7* 33 bitów nie można ustalić odpowiedzi, bo nie wiadomo ile jest znaków w tym tekście.Pytanie: Czy drzewo kodu prefiksowego Huffmana jest drzewem lokalnie pełnym?Nie, kształt drzewa zależy od liczby znaków kodowanych.Tak, każdy wierzcholek wewnętrzny tworzonego drzewa ma dwa następniki.3.(1p) Ile miejsca zajmie, w najlepszym razie, zakodowanie tego zdania kodem stałej długości? 512 bitów 4*26 bitów 86*6 bitów 5*86 bitów 4.(1p) Załóżmy, że problem polega na znalezieniu najkrótszych ścieżek z dowolnego wierzchołka do dowolnego innego w grafie o n wierzchołkach i m krawędziach. Jaki byłby koszt algorytmu, który wykorzystuje n krotnie algorytm Dijkstry znajdowania najkrótszych ścieżek z ustalonego źródła? O(n) O(lg m * n) O(n^3) O(n^2) O(m)5.(1p) Algorytm Dijkstry w każdym kroku wybiera krawędź o najmniejszym koszcie. Prawda czy fałsz? prawda fałszOdpowiedzi do pytań:  Wyniki