{"id":"informatyka-2018-maj-matura-rozszerzona/zad/1.3","paper_id":"informatyka-2018-maj-matura-rozszerzona","number":"1.3","points":1,"ptype":"closed","subject":"informatyka","category":"matura","year":2018,"month":"maj","level":"rozszerzona","text":"Zadanie 1.3. (0-1)\nDokończ zdanie. Wybierz i zaznacz właściwą odpowiedź spośród podanych.\nDla każdej liczby całkowitej n > 1 instrukcja oznaczona w algorytmie symbolem (*)\nwykona się\nA. mniej niż 2·݈݋݃\nଶ݊ razy.\nB. więcej niż n/2, ale mniej niż n razy.\nC. więcej niż n+1, ale mniej niż 2n razy.\nD. więcej niż n2 razy.\nWypełnia\negzaminator\nNr zadania\n1.1.\n1.2.\n1.3.\nMaks. liczba pkt.\n3\n2\n1\nUzyskana liczba pkt.\nMIN_1R","answer":"A","answer_text":"Zadanie 1.3. (0-1)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […] z zastosowaniem\npodejścia algorytmicznego.\n5. Rozwiązywanie problemów\ni podejmowanie decyzji […], stosowanie\npodejścia algorytmicznego.\nZdający:\n11) opisuje podstawowe algorytmy\ni stosuje:\na) algorytmy na liczbach całkowitych,\n16) opisuje własności algorytmów na\npodstawie ich analizy;\n17) ocenia zgodność algorytmu ze\nspecyfikacją problemu;\n18) oblicza liczbę operacji wykonywanych\nprzez algorytm.\nSchemat punktowania\n1 p. - za poprawną odpowiedź.\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPoprawna odpowiedź:\nA","solution":"## Poprawna odpowiedź\n\n**A** - mniej niż 2·log₂n razy.\n\n## Sposób 1 - analiza algorytmu jako wyszukiwanie binarne\n\nAlgorytm z zadania 1.1 to **wyszukiwanie binarne** (binary search). Instrukcja (*) wykonuje się w każdej iteracji pętli `while p < q`.\n\n**Kluczowa obserwacja:** W każdej iteracji długość przedziału `[p, q]` zmniejsza się co najmniej o połowę:\n- Jeśli `s³ < n`: `p := s+1`, więc nowy przedział = `[s+1, q]`, długość ≤ q - s ≤ (q-p)/2.\n- Jeśli `s³ ≥ n`: `q := s`, więc nowy przedział = `[p, s]`, długość = s - p ≤ (q-p)/2.\n\nPoczątkowa długość przedziału = n - 1 ≈ n. Liczba iteracji potrzebnych do zmniejszenia z n do 1: **log₂(n)** iteracji.\n\n## Sposób 2 - empirycznie\n\n**Z symulacji w 1.1:**\n- n = 28: 5 iteracji. log₂(28) ≈ 4.81. 2·log₂(28) ≈ 9.6. **5 < 9.6** ✓\n- n = 64: 6 iteracji. log₂(64) = 6. 2·log₂(64) = 12. **6 < 12** ✓\n- n = 80: 6 iteracji. log₂(80) ≈ 6.32. 2·log₂(80) ≈ 12.6. **6 < 12.6** ✓\n\nLiczba iteracji jest **bliska log₂(n)**, więc na pewno mniejsza niż 2·log₂(n). Odpowiedź A.\n\n## Sposób 3 - eliminacja błędnych opcji\n\n### Opcja B: więcej niż n/2, mniej niż n razy\nDla n = 28: n/2 = 14, n = 28. Liczba iteracji = 5. 5 NIE jest > 14 → **B błędna**.\n\n### Opcja C: więcej niż n+1, mniej niż 2n razy\nDla n = 28: n+1 = 29. Liczba iteracji = 5. 5 NIE jest > 29 → **C błędna**.\n\n### Opcja D: więcej niż n² razy\nDla n = 28: n² = 784. Liczba iteracji = 5. 5 NIE jest > 784 → **D błędna**.\n\n### Opcja A: mniej niż 2·log₂n razy\nDla n = 28: 2·log₂(28) ≈ 9.6. Iteracji 5 < 9.6 → **A poprawna** ✓.\n\n## Reference informatyczny - złożoność wyszukiwania binarnego\n\n> Reference - Wyszukiwanie binarne:\n> - **Klasyczna złożoność**: O(log n).\n> - **Dokładna liczba iteracji**: ⌈log₂(n)⌉ + O(1).\n> - Każda iteracja zmniejsza długość przedziału co najmniej o połowę.\n> - Dla n = 1024: ~10 iteracji. Dla n = 10⁶: ~20 iteracji.\n>\n> Reference - Klasy złożoności:\n> | Klasa | Notacja | Przykład |\n> |-------|---------|----------|\n> | logarytmiczna | O(log n) | binary search, drzewo BST |\n> | liniowa | O(n) | wyszukiwanie liniowe |\n> | n log n | O(n log n) | mergesort, heapsort |\n> | kwadratowa | O(n²) | bubble sort, naiwne porównanie par |\n> | wykładnicza | O(2ⁿ) | brute-force kombinacji |\n>\n> Reference - Konwersja log:\n> - log₂(n) = ln(n) / ln(2) = log₁₀(n) / log₁₀(2) ≈ log₁₀(n) · 3.32\n> - log₂(1000) ≈ 10\n> - log₂(10⁶) ≈ 20\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 1.3, max 1 pkt):\n> - **1 pkt** - odpowiedź **A**\n> - **0 pkt** - błędna lub brak\n\n## Typowe pułapki\n\n- **Pomylenie z O(n)** - naiwna analiza \"pętla się powtarza\" sugeruje O(n), ale dzięki halving to O(log n).\n- **Niezrozumienie struktury binary search** - jeśli ktoś nie widzi, że to wyszukiwanie binarne, może pomyśleć, że (*) wykonuje się n razy (B).\n- **Mylenie 2·log₂n z log₂n²** - log₂(n²) = 2·log₂(n), więc obie formy są równoważne.\n- **Pomylenie podstawy logarytmu** - log₂ (binarny) vs log₁₀ (dziesiętny). Różnica stała, ale w wartości liczbowej ważne.\n\n## Złożoność obliczeniowa\n\n- Liczba iteracji pętli `while`: O(log n).\n- Instrukcja (*) wykonuje się raz na iterację: **O(log n)** razy.\n- Każda iteracja: stały koszt (mnożenie + porównanie + przypisanie).\n- **Łączna złożoność algorytmu: O(log n)** czas, O(1) pamięć.","image":"img/informatyka-2018-maj-matura-rozszerzona/zad-1.3.webp","solution_image":null,"topics":null,"page_from":3,"source":"ocr","answer_source":"ocr","answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2018 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"<p>Zadanie 1.3. (0-1)<br>Dokończ zdanie. Wybierz i zaznacz właściwą odpowiedź spośród podanych.<br>Dla każdej liczby całkowitej n &gt; 1 instrukcja oznaczona w algorytmie symbolem (*)<br>wykona się<br>A. mniej niż 2·݈݋݃<br>ଶ݊ razy.<br>B. więcej niż n/2, ale mniej niż n razy.<br>C. więcej niż n+1, ale mniej niż 2n razy.<br>D. więcej niż n2 razy.<br>Wypełnia<br>egzaminator<br>Nr zadania<br>1.1.<br>1.2.<br>1.3.<br>Maks. liczba pkt.<br>3<br>2<br>1<br>Uzyskana liczba pkt.<br>MIN_1R</p>","answer_text_html":"<p>Zadanie 1.3. (0-1)<br>Wymagania ogólne<br>Wymagania szczegółowe<br>III. Rozwiązywanie problemów<br>i podejmowanie decyzji […] z zastosowaniem<br>podejścia algorytmicznego.</p>\n<ol><li>Rozwiązywanie problemów</li></ol>\n<p>i podejmowanie decyzji […], stosowanie<br>podejścia algorytmicznego.<br>Zdający:</p>\n<ol><li>opisuje podstawowe algorytmy</li></ol>\n<p>i stosuje:<br>a) algorytmy na liczbach całkowitych,</p>\n<ol><li>opisuje własności algorytmów na</li></ol>\n<p>podstawie ich analizy;</p>\n<ol><li>ocenia zgodność algorytmu ze</li></ol>\n<p>specyfikacją problemu;</p>\n<ol><li>oblicza liczbę operacji wykonywanych</li></ol>\n<p>przez algorytm.<br>Schemat punktowania<br>1 p. - za poprawną odpowiedź.<br>0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.<br>Poprawna odpowiedź:<br>A</p>","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"<h4>Poprawna odpowiedź</h4>\n<p><strong>A</strong> - mniej niż 2·log₂n razy.</p>\n<h4>Sposób 1 - analiza algorytmu jako wyszukiwanie binarne</h4>\n<p>Algorytm z zadania 1.1 to <strong>wyszukiwanie binarne</strong> (binary search). Instrukcja (*) wykonuje się w każdej iteracji pętli <code>while p &lt; q</code>.</p>\n<p><strong>Kluczowa obserwacja:</strong> W każdej iteracji długość przedziału <code>[p, q]</code> zmniejsza się co najmniej o połowę:</p>\n<ul><li>Jeśli <code>s³ &lt; n</code>: <code>p := s+1</code>, więc nowy przedział = <code>[s+1, q]</code>, długość ≤ q - s ≤ (q-p)/2.</li><li>Jeśli <code>s³ ≥ n</code>: <code>q := s</code>, więc nowy przedział = <code>[p, s]</code>, długość = s - p ≤ (q-p)/2.</li></ul>\n<p>Początkowa długość przedziału = n - 1 ≈ n. Liczba iteracji potrzebnych do zmniejszenia z n do 1: <strong>log₂(n)</strong> iteracji.</p>\n<h4>Sposób 2 - empirycznie</h4>\n<p><strong>Z symulacji w 1.1:</strong></p>\n<ul><li>n = 28: 5 iteracji. log₂(28) ≈ 4.81. 2·log₂(28) ≈ 9.6. <strong>5 &lt; 9.6</strong> ✓</li><li>n = 64: 6 iteracji. log₂(64) = 6. 2·log₂(64) = 12. <strong>6 &lt; 12</strong> ✓</li><li>n = 80: 6 iteracji. log₂(80) ≈ 6.32. 2·log₂(80) ≈ 12.6. <strong>6 &lt; 12.6</strong> ✓</li></ul>\n<p>Liczba iteracji jest <strong>bliska log₂(n)</strong>, więc na pewno mniejsza niż 2·log₂(n). Odpowiedź A.</p>\n<h4>Sposób 3 - eliminacja błędnych opcji</h4>\n<h5>Opcja B: więcej niż n/2, mniej niż n razy</h5>\n<p>Dla n = 28: n/2 = 14, n = 28. Liczba iteracji = 5. 5 NIE jest &gt; 14 → <strong>B błędna</strong>.</p>\n<h5>Opcja C: więcej niż n+1, mniej niż 2n razy</h5>\n<p>Dla n = 28: n+1 = 29. Liczba iteracji = 5. 5 NIE jest &gt; 29 → <strong>C błędna</strong>.</p>\n<h5>Opcja D: więcej niż n² razy</h5>\n<p>Dla n = 28: n² = 784. Liczba iteracji = 5. 5 NIE jest &gt; 784 → <strong>D błędna</strong>.</p>\n<h5>Opcja A: mniej niż 2·log₂n razy</h5>\n<p>Dla n = 28: 2·log₂(28) ≈ 9.6. Iteracji 5 &lt; 9.6 → <strong>A poprawna</strong> ✓.</p>\n<h4>Reference informatyczny - złożoność wyszukiwania binarnego</h4>\n<blockquote>Reference - Wyszukiwanie binarne:<br>- <strong>Klasyczna złożoność</strong>: O(log n).<br>- <strong>Dokładna liczba iteracji</strong>: ⌈log₂(n)⌉ + O(1).<br>- Każda iteracja zmniejsza długość przedziału co najmniej o połowę.<br>- Dla n = 1024: ~10 iteracji. Dla n = 10⁶: ~20 iteracji.<br><br>Reference - Klasy złożoności:<br>| Klasa | Notacja | Przykład |<br>|-------|---------|----------|<br>| logarytmiczna | O(log n) | binary search, drzewo BST |<br>| liniowa | O(n) | wyszukiwanie liniowe |<br>| n log n | O(n log n) | mergesort, heapsort |<br>| kwadratowa | O(n²) | bubble sort, naiwne porównanie par |<br>| wykładnicza | O(2ⁿ) | brute-force kombinacji |<br><br>Reference - Konwersja log:<br>- log₂(n) = ln(n) / ln(2) = log₁₀(n) / log₁₀(2) ≈ log₁₀(n) · 3.32<br>- log₂(1000) ≈ 10<br>- log₂(10⁶) ≈ 20</blockquote>\n<h4>Schemat oceniania CKE</h4>\n<blockquote>Klucz CKE (zadanie 1.3, max 1 pkt):<br>- <strong>1 pkt</strong> - odpowiedź <strong>A</strong><br>- <strong>0 pkt</strong> - błędna lub brak</blockquote>\n<h4>Typowe pułapki</h4>\n<ul><li><strong>Pomylenie z O(n)</strong> - naiwna analiza &quot;pętla się powtarza&quot; sugeruje O(n), ale dzięki halving to O(log n).</li><li><strong>Niezrozumienie struktury binary search</strong> - jeśli ktoś nie widzi, że to wyszukiwanie binarne, może pomyśleć, że (*) wykonuje się n razy (B).</li><li><strong>Mylenie 2·log₂n z log₂n²</strong> - log₂(n²) = 2·log₂(n), więc obie formy są równoważne.</li><li><strong>Pomylenie podstawy logarytmu</strong> - log₂ (binarny) vs log₁₀ (dziesiętny). Różnica stała, ale w wartości liczbowej ważne.</li></ul>\n<h4>Złożoność obliczeniowa</h4>\n<ul><li>Liczba iteracji pętli <code>while</code>: O(log n).</li><li>Instrukcja (*) wykonuje się raz na iterację: <strong>O(log n)</strong> razy.</li><li>Każda iteracja: stały koszt (mnożenie + porównanie + przypisanie).</li><li><strong>Łączna złożoność algorytmu: O(log n)</strong> czas, O(1) pamięć.</li></ul>"}]}