www.szkolnictwo.pl

Konspekt ten dotyczy wykorzystania schematu Hornera do obliczania wartości wielomianu oraz obliczania dziesiętnej wartości liczb zapisanych w różnych systemach pozycyjnych.

Czas trwania zajęć: 2 godz.

Cel ogólny: uczeń zna schemat Hornera i potrafi obliczyć wartość wielomianu iteracyjnie i rekurencyjnie.

Cele operacyjne:
a) wiadomości:
- umie podać różnice między iteracją a rekurencją
- wie, jak wygląda postać ogólna wielomianu
- rozumie znaczenie optymalizacji algorytmu
b) umiejętności
- potrafi zastosować schemat Hornera do obliczeń
- potrafi napisać program obliczający wartość dowolnego wielomianu iteracyjnie i rekurencyjnie
- potrafi prawidłowo interpretować znaczenie komunikatów oprogramowania
- potrafi ocenić złożoność algorytmu

Środki dydaktyczne: stanowiska komputerowe, środowisko FreePascal, kalkulator, tablica

Metoda pracy: problemowa, dyskusji, ćwiczeń

Forma pracy: częściowo praca zbiorowa jednolita oraz praca samodzielna przy komputerze


Przebieg zajęć:

I. Część wprowadzająca

Nauczyciel przedstawia uczniom zagadnienie omawiane na lekcji.

Przypomina postać ogólną wielomianu:
w(x) = a0xn + a1xn-1 + a2xn-2 + ... + an-1x + an

Nauczyciel pyta uczniów, jak obliczamy wartość wielomianu.

Zapis działań, jakie należy wykonać w celu obliczenia wartości wielomianu:
w = 3x4 + 2x3 + x2 - 4x + 2, dla x= 3

Nauczyciel podaje przykłady zastosowania umiejętności obliczania wartości wielomianu:

1) Wielomiany to podstawowe funkcje w informatyce, gdyż wartości większości innych funkcji są obliczane jako wartości odpowiednich wielomianów.

2) Zapis liczby dziesiętnej w dowolnym systemie pozycyjnym przy ustalonej podstawie np. 2.
Jest to wielomian, w którym współczynniki mogą przyjmować tylko określone wartości (np. 0, 1), a w miejscu zmiennej xwystępuje podstawa systemu.

Przykład:
(1011011)2 = 1*26+ 0*25 + 1*24 + 1*23 + 0*22+ 1*21 + 1*20

Nauczyciel prosi o określenie złożoności tego sposobu obliczania wartości wielomianu.

Uczniowie podają, ile mnożeń i dodawań należy wykonać wykorzystując ten sposób obliczeń dla przykładu wielomianu w - 10 i 4).

Nauczyciel podaje wzór ogólny mnożeń i n dodawań.

Nauczyciel wskazuje na inny sposób obliczania wartości wielomianu (wyprowadzając wzór):
dla wielomianu w z przykładu:
w = (((3x + 2)x + 1)x - 4)x + 2
dla postaci ogólnej wielomianu:
w(x) = (...((a0x + a1)x + a2)x + ... + an-1)x + an

Nauczyciel zwraca uwagę uczniów na prostotę obliczania wartości wielomianu tym sposobem (np. na kalkulatorze bez wykorzystywania pamięci).

Nauczyciel prosi uczniów o określenie złożoności tego sposobu na przykładzie wielomianu w, i ogólnie - n mnożeń i n dodawań.

Nauczyciel i uczniowie wspólnie formułują wniosek: Obliczając wartość wielomianu tym sposobem zmniejszymy ilość mnożeń - jest to sposób efektywniejszy i okazuje się, że jest on najbardziej
efektywny.

Uczniowie odpowiadają na pytanie: Dlaczego to jest tak ważne?

Mnożenie zajmuje procesorowi bardzo dużo czasu, więc wszelkie ograniczanie tego działania w jakimkolwiek algorytmie zwiększa jego szybkość w znacznym stopniu (mnożenie jest operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów).


Interpretacja schematu Hornera w sposób iteracyjny.

Uczniowie wskazują na operacje, które się powtarzają (można je
wykorzystać do zbudowania pętli - jako działanie
wi = wi-1*x+ ai, dla i = 1, ..., n
- w przypadku programowania można ten wzór zapisać, wykorzystując operator podstawiania, jako
w = w*x + ai, dla i = 1, ..., n).

Wspólne zapisanie schematu Hornera w postaci schematu blokowego.

Dane:
n - liczba naturalna - stopień wielomianu,
a0, a1, ..., an - liczby rzeczywiste - współczynniki wielomianu,
x - liczba rzeczywista - argument, dla którego będzie obliczana wartość wielomianu

Użyte zmienne:

i - liczba naturalna - licznik kontrolujący kolejne współczynniki,
w - liczba rzeczywista - wartość kolejnych obliczeń wykonywanych w pętlach

Wynik:
wartość wielomianu (ostatnia wartość zmiennej w) obliczona według schematu Hornera


Zapisanie schematu Hornera w postaci funkcji w języku Pascal (przypomnienie, że współczynniki wielomianu najłatwiej zapisać w pamięci komputera w postaci tablicy):

function wartosc:real;
var i:byte;
w:real;
begin
w:=a[0];
for i:=1 to n do
w:=w*x+a[i];
wartosc:=w;
end;

Nauczyciel prosi o dokończenie programu i sprawdzenie poprawności działania.


Interpretacja schematu Hornera w sposób rekurencyjny.

Nauczyciel przypomina, że algorytmy iteracyjne da się przedstawić w sposób rekurencyjny, i odwrotnie.

Zapisanie kolejnych iteracji w postaci wzorów:
w0 = a0
w1 = w0*x + a1
w2 = w1*x + a2
...
wn = wn-1*x + an

oraz wzoru rekurencyjnego:
w0 = a0
wn = wn-1*x + an

Na podstawie wzoru tworzymy funkcję rekurencyjną w języku Pascal.

function wartoscrek(k:byte):real;
begin
if k=0 then
wartoscrek:=t[0]
else
wartoscrek:=wartoscrek(k-1)*x+a[k];
end;

B. Zastosowanie schematu Hornera

Obliczanie wartości wielomianu.

Nauczyciel poleca uczniom uruchomienie programu Kalkulator (widok podstawowy) i obliczenie wartości przykładowego wielomianu, wykorzystując schemat Hornera oraz działania mnożenia i dodawania/odejmowania.

Dziesiętna reprezentacja liczb zapisanych w różnych systemach pozycyjnych.

Nauczyciel prosi o obliczenie wartości dziesiętnej liczby zapisanej w systemie dwójkowym, wykorzystując schemat Hornera (kolejne cyfry - współczynniki wielomianu, argument - liczba 2 - podstawa systemu).
(((((1*2 + 0)*2 + 1)*2 + 1)*2 + 0)*2 + 1)*2 + 1 =

Tak można obliczyć dziesiętną wartość liczby w dowolnym systemie (przy podstawach
większych od 10 problemem może być zamiana współczynników).

Nauczyciel zauważa, że w przypadku systemu dwójkowego, można jeszcze bardziej
zoptymalizować ten program – mnożenie współczynnika przez 2 można zastąpić dodawaniem.


III. Część podsumowująca

Uczniowie odpowiadają na pytania:
Co to jest schemat Hornera?
Dlaczego jest tak ważny?
Do czego można go wykorzystać?

Nauczyciel zadaje uczniom pracę domową:
Odnaleźć w książce do matematyki schemat Hornera, dotyczący dzielenia wielomianu przez
dwumian i przeanalizować go.
Zastanowić się, jak napisać program dotyczący schematu Hornera bez użycia tablic.

Opracował: Maciej Milczarek