Matura z informatyki 2005 – maj, poziom rozszerzony

Poniżej podaj zależność pomiędzy wartościami l_n i l_{n-1} dla każdego n=1, 2, ...

Podaj wzór rekurencyjny na różnicę r_n = l_n – l_{n-1} dla n>0.

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

Zależność pomiędzy l_n i l_{n-1}:

l_n = l_{n-1} + \frac{2}{3}·\frac{1}{2n+1}·\frac{1}{9ⁿ}

lub równoważnie:

l_n – l_{n-1} = \frac{2}{3}·\frac{1}{2n+1}·\frac{1}{9ⁿ}

Wzór rekurencyjny na różnicę r_n (z warunkiem początkowym):

r_1 = \frac{2}{81}

r_n = r_{n-1}·\frac{2n-1}{2n+1}·\frac{1}{9}

b) Podaj algorytm ze specyfikacją (w postaci listy kroków, schematu blokowego lub w języku programowania), który dla danej liczby ε (ε > 0) oblicza przybliżoną wartość ln 2, sumując jak najmniej wyrazów we wzorze podanym w treści zadania, aby różnica między dwoma ostatnimi przybliżeniami była mniejsza niż ε.

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

Uwaga: to zadanie otwarte – odpowiedź z klucza CKE jest jedynie przykładowa; istnieją również inne poprawne rozwiązania.

a) Wypisz poniżej wszystkie odróżnialne organizmy trzyletnie, które można uzyskać z organizmu dwuletniego o postaci ADBA.

Poniżej wpisz wszystkie odróżnialne organizmy (po jednym w wierszu) i kliknij Sprawdź.

b) Podaj sposób sprawdzania dla danej liczby naturalnej n ≥ 1, czy mogą istnieć organizmy o długości n. W przypadku odpowiedzi pozytywnej należy również ustalić wiek organizmu o wielkości n. Podaj, ile poprawnych wielkości organizmów występuje w przedziale (n, m] dla liczb naturalnych n i m, gdzie n < m. Odpowiedź uzasadnij.

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

c) Przyjmijmy, że każda litera pojawiająca się w regułach występuje dokładnie raz po lewej stronie reguły, przed „strzałką" (zauważmy, że powyższy przykład nie spełnia tego warunku, ponieważ litery A i D występują każda z lewej strony w dwóch regułach). Ile odróżnialnych organizmów w wieku 1, 2, 3 itd. może wówczas występować? Odpowiedź uzasadnij.

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

d) Poniżej przedstawiona jest funkcja wspomagająca realizację następującego zadania: dla zadanego zbioru reguł, nowo powstałego organizmu start i danego napisu należy ustalić, czy napis ten przedstawia organizm, który można uzyskać przy pomocy reguł zadanych w treści zadania.

Niech: L₁→F₁ S₁, L₂→F₂ S₂, ..., Lₚ→Fₚ Sₚ – dany zbiór reguł

Specyfikacja funkcji sprawdź:

Dane: napis – ..............., start – ...............

Wynik: odpowiedź, czy napis przedstawia organizm, który można uzyskać przy pomocy podanych reguł, gdy nowo powstały organizm jest opisywany przez start.

Treść funkcji sprawdź:

➢ jeśli długość napisu nie jest potęgą liczby 2, to zakończ wykonywanie funkcji z odpowiedzią NIE.
   W przeciwnym razie wykonuj:
   ➢ jeśli napis = start, to zakończ wykonywanie funkcji z odpowiedzią TAK;
   ➢ jeśli długość napisu jest równa 1, to zakończ wykonywanie funkcji z odpowiedzią NIE;
   ➢ podziel napis na dwie równe części: napis1 i napis2;
   ➢ dla i=1, 2, ..., p wykonuj:
      o jeśli Lᵢ = start, to
         ▪ wykonaj funkcję sprawdź rekurencyjnie dla napis = napis1, start = Fᵢ oraz dla napis = napis2 start = Sᵢ;
         ▪ jeśli oba rekurencyjne wywołania funkcji sprawdź zakończyły się odpowiedzią TAK, to zakończ wykonywanie funkcji z odpowiedzią TAK;
   ➢ jeśli w powyższej pętli nie zakończyliśmy działania funkcji, to zakończ jej wykonywanie z odpowiedzią NIE.

Dla podanej powyżej funkcji uzupełnij jej specyfikację. Podaj parametry wszystkich rekurencyjnych wywołań funkcji sprawdź przy uruchomieniu jej dla następującego zbioru reguł:

A → B C
A → C D
B → A D
C → B A
D → A A
D → B B

oraz napis = B C A A A D C D i start = A. Jaką odpowiedź da funkcja w tym przypadku?

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

Uzupełnij poniższą tabelę, wskazując, jakie narzędzia wykorzystasz do realizacji poszczególnych zadań. Podaj również, jakie techniki przetwarzania i reprezentacji danych trzeba zastosować (możliwy jest wybór więcej niż jednego narzędzia oraz techniki). Dla każdego przykładu podaj pod tabelą uzasadnienie, w jaki sposób i dlaczego będą one wykorzystywane?

Dla każdego z przykładów a)–f) podaj pod tabelą uzasadnienie wyboru narzędzia i techniki.

Uwaga: oficjalny klucz CKE do tego zadania zawiera wyłącznie schemat oceniania (punktację za dobór poprawnego narzędzia oraz poprawnej techniki wraz z uzasadnieniem), a nie modelowe odpowiedzi dla poszczególnych przykładów. Pełną treść zadania znajdziesz w arkuszu PDF.

a) Przeprowadź obliczenia, na podstawie których wyznaczysz, dla jakich wartości N ∈ [1, 7 000] należy wybrać firmę D1, a dla jakich firmę D2. Podaj też koszt realizacji projektu przy wyborze D1 i D2 dla N = 100, 1000 i 5000.

Na nośniku WYNIKI oddajesz plik (tu wpisz nazwę pliku) zawierający komputerową realizację Twoich obliczeń dla punktu a).

Do oceny oddajesz w dokumencie Raport4:

• przedział wartości N, dla których należy wybrać firmę D1, oraz przedział wartości N, dla których należy wybrać firmę D2. Każdy przedział umieść w osobnym wierszu. Końce przedziałów wyznacz z dokładnością do jednej setnej,
• tabelę zawierającą w kolejnych wierszach koszt realizacji projektu dla N = 100, 1000 i 5000. Koszty odpowiadające każdej z firm należy umieścić w osobnych kolumnach i zaokrąglić do jednej setnej. Zadbaj o czytelność tabeli.

b) Sporządź zestawienie porównujące koszt opłat licencyjnych w przypadku D2 z kosztem obliczeń, również w przypadku wyboru D2, dla wartości N z zakresu [6000, 9000] (z krokiem 100).

Na nośniku WYNIKI oddajesz plik (tu wpisz nazwę pliku) zawierający komputerową realizację Twoich obliczeń punktu b).

W dokumencie Raport4 należy umieścić:

• zestawienie trzykolumnowe zawierające kolejno w kolumnach: wartości N z zakresu [6000, 9000] (z krokiem 100), koszt opłat licencyjnych dla danego N, koszt obliczeń dla danego N,
• wykres liniowy ilustrujący otrzymane wyniki.

c) Podziel Raport4 na rozdziały o nazwach: Zadanie(4a), Zadanie(4b), Zadanie(4c). Odpowiedzi do poszczególnych podpunktów umieść w odpowiednich rozdziałach. Rozdziały utwórz nawet wówczas, gdy nie rozwiązujesz podpunktów (4a) i (4b). W rozdziale (4c) podaj nazwę systemu operacyjnego wykorzystywanego na komputerze, na którym pracujesz. Ponadto opisz sposób uzyskiwania informacji o rozmiarze dysku systemowego oraz wielkości wolnego miejsca na nim. W nagłówku dokumentu Raport4 wstaw swój kod zdającego.

a) Dany jest następujący ciąg liczb całkowitych: 1, –2, 6, –5, 7, –3. Wyznacz najlepszą sumę dla tego ciągu i wpisz poniżej jej wartość:

Najlepsza suma: (wpisz w arkuszu PDF / dokumencie Raport5)

Czy na podstawie uzyskanego wyniku można podać wartość najlepszej sumy dla ciągu: 1, –2, 2, 2, 2, –5, 3, 3, 1, –3?

Do oceny oddajesz w dokumencie Raport5 wartości najlepszej sumy dla ciągu oraz odpowiedź z uzasadnieniem na powyższe pytanie.

b) Zaproponuj algorytm wyznaczania najlepszej sumy dla dowolnego ciągu liczb całkowitych. Na jego podstawie napisz program do obliczenia najlepszych sum ciągów liczb podanych w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt (znajdującym się na nośniku DANE). Wpisz poniżej najlepsze sumy dla poszczególnych ciągów:

Do oceny oddajesz także w dokumencie Raport5:

• opis algorytmu zawierającego odpowiednie fragmenty kodu Twojego programu,
• wartości najlepszych sum dla poszczególnych plików, które wpisałeś do powyższej tabeli.

c) Wyznacz „najpopularniejszy" element w ciągu, czyli element występujący największą liczbę razy. Zaprojektuj jak najszybszy algorytm wyznaczania najpopularniejszego elementu ciągu oraz oszacuj liczbę wykonywanych przez niego operacji (czas działania) jako funkcję od liczby elementów w ciągu. Zaprogramuj swój algorytm i zastosuj go do ciągów znajdujących się w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt. W przypadku, gdy w ciągu jest więcej niż jeden najpopularniejszy element, jako wynik podajemy dowolny z nich. Na przykład dla ciągu 1, 3, 5, 1, 3 poprawną odpowiedzią jest zarówno 1, jak i 3 (oba elementy występują dwa razy). Wpisz poniżej najpopularniejsze elementy dla poszczególnych ciągów:

Do oceny oddajesz w dokumencie Raport5:

• najpopularniejsze elementy w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt umieszczone w tabeli czytelnie prezentującej te wyniki,
• opis algorytmu zawierającego odpowiednie fragmenty kodu Twojego programu oraz oszacowanie czasu jego działania.

a) Określ schemat wszystkich tabel (atrybuty i klucze główne) oraz związki między tabelami dla relacyjnej bazy danych zawierającej tabele: państw, zawodników, miast i wyników wszystkich zawodów Pucharu Świata. Wyniki w poszczególnych zawodach muszą być rozróżnialne. Przyjmij, że poszczególne zawody określone są jednoznacznie przez datę i miasto, w którym się one odbywają. Tabela miast zawiera nazwy miast, w których odbywają się zawody i skróty nazw państw, w których one leżą. Określając pozostałe tabele, wykorzystaj opis zawartości plików Panstwa.txt, Zawodnicy.txt, Kuusamo28.txt, Trondheim06.txt, Zakopane17.txt przedstawiony w tym zadaniu.

Do oceny oddajesz w pliku Raport6:

• opis każdej tabeli (nazwa tabeli, atrybuty, klucz główny) w osobnym wierszu,
• opis każdego związku w osobnym wierszu. Na opis związku składają się: nazwy tabel wchodzących w skład związku, typ związku oraz klucz główny/obcy.

b) Utwórz czytelne zestawienie zawierające następujące informacje: dla każdego państwa liczbę zawodników zanotowanych na punktowanych miejscach (miejsca od 1 do 30) w poszczególnych zawodach, dla których dysponujesz danymi.

Do oceny oddajesz tabelę umieszczoną w dokumencie Raport6.

c) Sporządź zestawienie 30 pierwszych zawodników w kolejności zajętych miejsc na zawodach w Zakopanem. Takie samo zestawienie sporządź również dla zawodów w Kuusamo. O miejscu zawodnika decyduje łączna nota uzyskana za dwa skoki. Wynikowe zestawienie ma zawierać dla każdego zawodnika: zajęte miejsce (numer miejsca), imię i nazwisko zawodnika, skrót nazwy państwa, które reprezentuje, długość pierwszego i drugiego skoku oraz łączną notę za oba skoki.

Do oceny oddajesz:

• pliki tekstowe punkt6a-z.txt i punkt6a-k.txt na nośniku WYNIKI zawierające odpowiednio zestawienie dla zawodów w Zakopanem i Kuusamo (w jednym wierszu umieszczamy informacje dotyczące jednego zawodnika, oddzielone średnikami),
• w dokumencie Raport6: opis metody otrzymania wyniku, a także pierwszy wiersz zestawienia dla Zakopanego i pierwszy wiersz zestawienia dla Kuusamo.

d) Utwórz informację o wynikach Adama Małysza na zawodach w Zakopanem, Kuusamo i Trondheim. Odpowiedź dla jednych zawodów składa się z: nazwy miasta w którym odbyły się zawody, odległości uzyskanej w pierwszej i drugiej serii skoków, uzyskanej noty, zajętego miejsca. Rezultaty wpisz do poniższej tabeli:

Do oceny oddajesz w dokumencie Raport6 zapytanie użyte do otrzymania wyniku.