objaśnia oraz porównuje podstawowe metody i techniki algorytmiczne oraz struktury danych, wykorzystując przykłady problemów i algorytmów, w szczególności: wyszukiwanie elementów liniowe i przez połowienie (do znajdowania elementów w zbiorze, sortowania przez wstawianie, przybliżonego rozwiązywania równań); rekurencję (do generowania ciągów liczb, potęgowania, sortowania liczb, generowania fraktali); metodę dziel i zwyciężaj (jednoczesne znajdowanie minimum i maksimum, sortowanie przez scalanie i szybkie); podejście zachłanne (do wydawania reszty, szukania najkrótszej drogi); programowanie dynamiczne (do szukania najdłuższego wspólnego podciągu); metodę szyfrowania z kluczem publicznym i jej zastosowanie w podpisie elektronicznym; struktury dynamiczne stos, kolejka, lista (do realizacji algorytmu ONP); grafy (do przedstawiania abstrakcyjnego modelu sytuacji problemowych)
Wyznacz i podaj najmniejszą odległość między dwoma miastami. Podaj także pary numerów miast (każdą parę w oddzielnym wierszu), między którymi jest taka odległość. Uwaga: Każdą parę miast wypisujemy tylko raz, np. 1 2 oraz 2 1 to ta sama para. Pamiętaj, że…
Oceń prawdziwość podanych zdań. Zaznacz P, jeśli zdanie jest prawdziwe, albo F – jeśli jest fałszywe. W każdym zadaniu punkt uzyskasz tylko za komplet poprawnych odpowiedzi. 1. Wynik powyższego zapytania to 3. 2. Wynikiem powyższego zapytania jest zestawienie:…
Dana jest dodatnia liczba całkowita n oraz uporządkowana rosnąco tablica różnych liczb całkowitych T[1..n]. Przeanalizuj następującą funkcję rekurencyjną, której parametrami są liczby całkowite x, p, k, przy czym . Rek(x, p, k) jeżeli…
Podaj, jakie będą wartości parametrów przekazywanych do funkcji Rek w kolejnych jej wywołaniach dla n = 11, tablicy oraz pierwszego wywołania Rek(37, 1, 11).
Rozważmy tablicę T = [3; 5; 7; 8; 9; 13; 33; 37; 40; 43]. A. Podaj wynik funkcji F(T, x) dla liczby x=7. B. Podaj, ile razy nastąpi modyfikacja wartości zmiennej p, a ile razy zmiennej k podczas wykonywania pętli dopóki dla x = 7 oraz dla x = 43. C. Podaj…
Podaj, ile razy dla n = 100 jest spełniony warunek „p <= k
Sprawdź działanie funkcji F(T, x) dla nieuporządkowanej tablicy T = [3; 5; 7; 8; 90; 13; 33; 37; 40; 43]. Podaj wynik działania tej funkcji dla tablicy T oraz liczby x = 43.
Które zdania dotyczące struktury danych zwanej stosem są prawdziwe? 1. Elementy stosu są zdejmowane w odwrotnej kolejności niż kolejność ich wkładania na stos. 2. Tylko pierwszy dodany element jest zawsze dostępny na stosie. 3. Stos może być używany m.in. przy…