11. Egzamin

grupa pierwsza: 1. podaj definicje pesymistycznej i sredniej zlozonosci obliczeniowej 2. wymien i krotko porownaj pod katem zlozonosci podane algorytmy sortowania 3. omow problem wyznaczania najkrotszych sciezek w grafie wazonym. podaj poznane algorytmy i wskaz zakresy ich zastosowan 4. co to jest restrukturyzacja tablic mieszajacych i kiedy sie ja wykonuje? 5. czym sa algorytmy wyczerpujace i kiedy sie je stosuje? 6. przedstaw generowanie permutacji w porzadku minimalnych zmian ze zbioru czteroelementowego {A, B, C, D} 7. przedstaw dzialanie algorytmu sortowania przez proste wstawianie dla tablicy liczb [15, 4, 5, 15, 1, 8, 45, 13, 2] 8. zilustruj proces wyszukiwania NWP ciagow X = i Y = 9. komiwojazer 10. rozwiaz uklad rownan: 2*T(n) - 4 = 3*T(n-1) + T(n) - 4 T(0) = 2

grupa druga: 1. podaj def algorytmu 2. omow idee sortowania przez kopcowanie 3. omow problem przeszukiwania grafu w glab i wszerz, Podaj mozliwe zastosowania i krotko omow poznane algorytmy 4. Podaj metody rozwiazywania kolizji w tablicach mieszajacych. Porownaj je pod katem efektywnosci. 5. Omow poznana metode sprawdzania czy odcinki sie przecinaja 6. Przedstaw proces znajdowania 11 i 21 kombinacji trojelementowej ze zbioru ABCDEFG 7. przedstaw dzialanie algorytmu sortowania przez proste wybieranie dla tablicy liczb 15,4,5,15,1,8,45,13,2 8. zilustruj proces wyszukiwania NWP ciagow X= BABDDBC Y= BCDBBDA 9. tabelka z odleglosciami - komiwojazer 10. rozwiaz ukald rownan 2T(n-1)-4=3T(n)+T(n-1)-4 T(0)=4