# Informatyka — zadanie 1.2

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2015-05/zad/1.2
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2015 (rozszerzona)
- rok: 2015
- poziom: rozszerzona
- typ: open
- punkty: 3
- działy: Programowanie i algorytmika, algorytmy

## Treść

Zadanie 1.2. (0-3)
Zastosowana strategia S w algorytmie jest optymalna, jeśli dla każdego programu
telewizyjnego wynik algorytmu (zbiór P) zawiera największą możliwą liczbę filmów, które
może obejrzeć telewidz.
Uwaga:
Strategia A nie jest optymalna, ponieważ telewidz może obejrzeć trzy filmy: film 1,
film 4 oraz film 2.
Dla strategii A, B i C podaj w przygotowanych tabelach przykłady programów telewizyjnych,
z emisją czterech filmów w dwóch stacjach, będące dowodami, że żadna z tych strategii nie
jest optymalna.
Dla każdej strategii i podanego dla niej programu telewizyjnego podaj wynik działania
algorytmu oraz przykład ilustrujący, że telewidz może obejrzeć więcej filmów, jeżeli nie
używa tej strategii.
Wskazówka. Podaj takie godziny emisji czterech filmów, aby telewidz był w stanie obejrzeć
np. trzy lub więcej filmów, podczas gdy zastosowanie algorytmu z odpowiednią strategią
daje rozwiązanie zawierające co najwyżej dwa filmy.
Dowód dla strategii A:
Telewizja
/ stacja
Film i godziny jego emisji
Czas trwania
emisji filmu
TV1
film 1 (od do ),
film 2 (od do )
TV2
film 3 (od do ),
film 4 (od do )
Wynik działania algorytmu przy zastosowaniu strategii A:
P
Liczniejszy zbiór filmów, które może obejrzeć widz:
Dowód dla strategii B:
Telewizja
/ stacja
Film i godziny jego emisji
Czas trwania
emisji filmu
TV1
film 1 (od do ),
film 2 (od do )
TV2
film 3 (od do ),
film 4 (od do )
Wynik działania algorytmu przy zastosowaniu strategii B:
P
Liczniejszy zbiór filmów, które może obejrzeć widz:
MIN_1R
Dowód dla strategii C:
Telewizja
/ stacja
Film i godziny jego emisji
Czas trwania
emisji filmu
TV1
film 1 (od do ),
film 2 (od do )
TV2
film 3 (od do ),
film 4 (od do )
Wynik działania algorytmu przy zastosowaniu strategii C:
P
Liczniejszy zbiór filmów, które może obejrzeć widz:

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

Kontrprzykłady (po jednym dla A, B, C):

**Strategia A (najdłuższy, w razie remisu najwcześniej kończący) - nieoptymalna:**

| Telewizja | Filmy |
| TV1 | film 1: 10:00-12:00; film 2: 12:00-14:00 |
| TV2 | film 3: 10:00-11:00; film 4: 11:00-12:00 |

- Wynik strategii A: P = **{film 1, film 2}** (2 filmy - film 1 najdłuższy 2h, koliduje z 3 i 4; potem film 2).
- Większy zbiór: **{film 3, film 4, film 2}** (3 filmy).

**Strategia B (najkrótszy, w razie remisu najwcześniej kończący) - nieoptymalna:**

| Telewizja | Filmy |
| TV1 | film 1: 11:30-12:30; film 2: 15:00-16:00 |
| TV2 | film 3: 10:00-12:00; film 4: 12:00-14:00 |

- Wynik strategii B: P = **{film 1, film 2}** (film 1 najkrótszy 1h, koliduje z 3 i 4; potem film 2 też 1h).
- Większy zbiór: **{film 3, film 4, film 2}** (3 filmy).

**Strategia C (najwcześniej zaczynający, w razie remisu najwcześniej kończący) - nieoptymalna:**

| Telewizja | Filmy |
| TV1 | film 1: 09:00-14:00; film 2: 15:00-16:00 |
| TV2 | film 3: 10:00-12:00; film 4: 12:00-14:00 |

- Wynik strategii C: P = **{film 1, film 2}** (film 1 zaczyna najwcześniej 9:00, koliduje z 3 i 4; potem film 2).
- Większy zbiór: **{film 3, film 4, film 2}** (3 filmy).

## Sposób 1 - analiza dlaczego dana strategia zawodzi

**Strategia A (najdłuższy):** wybiera długi film, który blokuje wiele krótkich. Kontrprzykład: 1 długi film przeciw 2 krótkim, które się nie nakładają.

**Strategia B (najkrótszy):** krótki film znajdujący się "w środku" innego długiego blokuje konfigurację z większej liczby krótkich. Film 1 jest najkrótszy (1h) i wyklucza film 3 i film 4.

**Strategia C (najwcześniej zaczynający):** wybiera film startujący najwcześniej, nawet jeśli długo trwa. Film 1 startuje o 9:00 i blokuje wszystko między 9 a 14.

## Sposób 2 - uzasadnienie optymalności strategii D

Strategia D (najwcześniej kończący, w razie remisu najpóźniej zaczynający) to klasyczny **algorytm zachłanny dla problemu wyboru aktywności** - twierdzenie z teorii algorytmów mówi, że ZAWSZE daje optymalną liczbę niekolidujących przedziałów.

**Dowód intuicyjny:** Wybierając film kończący się najwcześniej, zostawiamy MAKSIMUM czasu pozostałego dla kolejnych filmów. Twierdzenie wymiany (exchange argument) pokazuje, że dowolne rozwiązanie optymalne można "przekształcić" na rozwiązanie zaczynające się od najwcześniej kończącego filmu, bez utraty liczebności.

## Reference informatyczny - twierdzenie o optymalności greedy

> Reference - Activity Selection Theorem:
> - Strategia "earliest deadline first" (najwcześniej kończący) jest optymalna dla problemu wyboru najliczniejszego zbioru niekolidujących aktywności.
> - Dowód: indukcja po liczbie aktywności + exchange argument.
> - Strategie inne (najdłuższy / najkrótszy / najwcześniej zaczynający) są w ogólności NIEOPTYMALNE.

## Schemat oceniania CKE

> Klucz CKE (zadanie 1.2, max 3 pkt):
> - **3 pkt** - kontrprzykłady dla 3 strategii (program TV + wynik algorytmu + większy zbiór)
> - **2 pkt** - dla 2 strategii
> - **1 pkt** - dla 1 strategii
> - **0 pkt** - niepełna albo brak

## Typowe pułapki

- Podanie tylko programu TV bez wyniku działania algorytmu - nieuznaje się.
- Podanie programu, w którym strategia daje 3 filmy - to NIE jest kontrprzykład (musi dać <3).
- Pominięcie warunku "4 filmy w 2 stacjach".
- Mylenie czasu zakończenia / czasu zaczęcia.

## Złożoność obliczeniowa

- Sprawdzenie kontrprzykładu: O(1) (mała liczba filmów).
- Algorytm wyboru aktywności (greedy z sortowaniem): O(n log n).

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2015-05/zad/1.2)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2015-05%2Fzad%2F1.2)

## Podobne zadania

- [Zadanie 1.2](https://matura.lol/question/informatyka-2015-maj-matura-rozszerzona/zad/1.2) — Zadanie 1.2. (0-3) Zastosowana strategia S w algorytmie jest optymalna, jeśli dla każdego programu telewizyjnego wynik algorytmu (zbiór P) zawiera największą mo

_Ostatnia aktualizacja danych: 2026-10-03_