AlgorytmyCw1.pdf

(107 KB) Pobierz
Algorytmy_Cw1
Algorytmy
Klasyfikacja wg zadaı algorytmizowalnych
Pojħcie algorytmu
« ńrdþosþw:
Î w Ļredniowieczu: abacist / algorist
Î od nazwiska arabskiego autora traktatu o algebrze (arytmetyce) i nazwy geograficznej rejonu
Jeziora Aralskiego
« Znaczenie:
Î mechaniczna procedura obliczeniowa, tzn.:
¤ dane + reguþy ich przetwarzania
¤ informacja o modelu maszyny Turinga
Î taĻma (dane)
Î gþowica (jednostka czytajĢco/zapisujĢca)
Î program sterujĢcy gþowicĢ (automat skoıczony)
Podstawowe definicje informatyczne
1. Algorytm
¤ Sposb rozwiĢzania okreĻlonego problemu (zadania);
¤ Skoıczony ciĢg ĻciĻle okreĻlonych krokw, ktrych wykonanie rozwiĢzuje postawiony
problem (zadanie);
¤ Sposb przeksztaþcenia danych wejĻciowych
w dane wyjĻciowe.
2. Program
¤ Forma przedstawienia (zapisu) algorytmu
w konkretnym jħzyku programowania.
Algorytmy i ich wþaĻciwoĻci
Przykþadowe algorytmy
Î Algorytm Euklidesa (gcd(a, b) = gcd (b, a mod b))
Î Sortowanie przez prosty wybr
Wsplna cecha algorytmw uŇytecznych:
Î iteracyjnoĻę prowadzĢca do osiĢgniħcia spodziewanego wyniku, a czasem jest to rekurencja
= rekursja => rekursywnoĻę
Spodziewany wynik: warunki wstħpne => warunki koıcowe
Porwnywanie algorytmw
Î czas wykonania Î zþoŇonoĻę obliczeniowa
1
8694514.008.png
Î pamiħę potrzebna do dziaþania algorytmu (objħtoĻę struktur danych, na ktrych dziaþa
algorytm)
Zadanie: odnalezienie najwiħkszego wsplnego dzielnika (NWD) dwch liczb naturalnych a i b
Algorytm Euklidesa:
1. JeĻli a = b, to
NWD:= a;
Koniec obliczeı.
2. JeĻli a > b, to
zamieı a z b.
3. Oblicz (b-a). RŇnice zachowaj
w zmiennej b.
4. Wrę do p.1.
Przykþady algorytmw klasycznych
Zadanie: wĻrd 25 jednakowych (na zewnĢtrz) monet odnaleŅę monetħ faþszywĢ.
(Moneta faþszywa jest ciħŇsza od pozostaþych)
RozwiĢzanie:
1. 12 12 (1)
2. 6 6 (0)
3. 3 3 (0)
4. 1 1 (1)
Podstawowe etapy opracowania algorytmw i programw
1. Analiza postawionego problemu (zadania) - Co jest zadane? Co trzeba odnaleŅę?
2. Opracowanie modelu matematyczno-logicznego postawionego problemu Î Zamiana obiektw
problemu obiektami matematycznymi (struktury danych); zamiana relacji miħdzy obiektami na
operacje matematyczne i/lub logiczne.
3. Opracowanie algorytmu rozwiĢzujĢcego postawiony problem.
4. Udowodnienie poprawnoĻci opracowanego algorytmu.
5. Analiza efektywnoĻci opracowanego algorytmu (zþoŇonoĻci obliczeniowa, tj. liczba krokw;
liczba operacji wykonywanych podczas realizacji algorytmu);
6. Przeksztaþcenie opracowanego algorytmu w odpowiedni program.
7. Przetestowanie opracowanego programu na rŇnych przykþadach. Opracowanie dokumentacji
technicznej.
Zadania Projektowania algorytmw
Zadania na ęwiczenia
1. Wyznacz maksymalnĢ liczbħ spoĻrd wczytanych, podaj wartoĻę i pozycjħ w tablicy
2. Wyznacz medianħ zbioru liczb, gdzie mediana to jest wartoĻę Ļrodkowa w ciĢgu
uporzĢdkowanym wg. wartoĻci
Zadania indywidualne na ocenħ wedþug wariantw:
x
2
x
4
x
6
x
8
1.
y
=
1
−
+
−
+
−
K
=
cos
x
2
4
6
8
x
3
x
5
x
7
x
9
2.
y
=
x
−
+
−
+
−
K
=
sin
x
3
5
7
9
x
2
x
3
x
4
x
5
y
=
x
−
+
−
+
−
K
=
ln(
1
+
x
)
2
3
4
5
2
8694514.009.png 8694514.010.png
Metody projektowania algorytmw
Metoda opracowania od koıca (working backward)
Podstawowe typy blokw
Opracowanie schematw blokowych algorytmw
Zadanie Rwnanie kwadratowe: ax2+bx+c=0
To po uzupeþnieniu:
Start
//Deklaracja zmiennych
read (a); read(b); read(c);
Tak
Nie a = = 0;
Tak
D = b*b - 4*a*c;
Nie b = = 0;
Tak
Tak
Nie
D < 0;
x = -c/b;
Nie c = = 0;
x1=(-b+sqrt(D))/(2*a);
write(x);
write
x2=(-b- sqrt(D))/(2*a);
(Ñx-liczba dowolnaÑ);
write(x1);
write (Ñbrak
write(Ñbþħdne dane
write (x2);
pierwiastkwÑ);
wejĻcioweÑ);
Koniec
3
8694514.011.png 8694514.001.png 8694514.002.png 8694514.003.png
Kryteria jakoĻci algorytmw
1. PoprawnoĻę algorytmu (dokþadnoĻę otrzymywanych wynikw);
np. Ograniczenie systemu dwjkowego:
1. Przeksztaþcenie liczb caþkowitych i uþamkw
2. Bþħdy zaokrĢgleı
13 : 2 = 6 r 1
6 : 2 = 3 r 0
x
2
x
3
x
4
e x
sin
=
1
+
x
+
+
+
+
K
3 : 2 = 1 r 1
2
3
4
3
5
7
9
x
x
x
x
x
1 : 2 = 0 r 1
(0,2)10 (0,0011001100110011...)2
=
x
−
+
−
+
−
K
3
5
7
9
2. ZþoŇonoĻę obliczeniowa algorytmu (liczba krokw; liczba operacji wykonywanych podczas
realizacji algorytmu);
Przykþad. Problem komiwojaŇera.
ZþoŇonoĻę obliczeniowa: (n-1)!
Czas realizacji algorytmu wyczerpujĢcego na
Pentium IV 2GHz dla n=20 miast Î okoþo 2 lat!
3. Wymagana objħtoĻę pamiħci komputerowej (dla przechowywania wynikw poĻrednich).
Algorytmy:
1. Iteracyjne
2. Rekurencyjne
Inteligencji komputerowej
3. Z bazami wiedzy , gþwnie systemy wnioskowania w systemach ekspertowych
4. Heurystyczne (genetyczne)
5. Sieci neuronowe
Podprogramy rekurencyjne.
np. silnie: n!= n*(n-1)!
Definicja Program P jest czħĻciowo poprawny ze wzglħdu na specyfikacjħ <a, b> w strukturze
danych M wttw dla kaŇdych danych w strukturze M, jeŇeli warunek poczĢtkowy a specyfikacji jest
speþniony przez dane i program zatrzymuje siħ po skoıczonej liczbie krokw, to warunek koıcowy
b jest speþniony przez wyniki programu, tzn.
Dla kaŇdego wartoĻciowania v w strukturze M,
M,v |= (a and Ptrue ) => Pb
Definicja SpecyfikacjĢ algorytmu programu bħdziemy nazywali parħ warunkw(formuþ)
<wp, wk>.
Intuicyjnie odpowiadajĢ one warunkowi, ktre powinny speþniaę dane (warunkowi poczĢtkowemu)
i warunkowi, ktry powinien byę speþniony po zakoıczeniu algorytmu (warunkowi koıcowemu).
Zadanie
Zapoznaj siħ z programem SBWIN32Pro, wczytujĢc z folderu examples:
najmniejszawspolnawielokrotnoscalgorytmy
EUKLIDES lub inne,
Omw ich dziaþanie i zakoduj w pseudokodzie
Literatura uzupeþniajĢca
[1] Wrblewski P.:Algorytmy, struktury danych i techniki programowania, Helion, 1997
[2]. Knuth D.: Sztuka programowania, t. I Î III (w serii klasyka informatyki)
[3]. Cormen T. H. i in.: Wprowadzenie do algorytmw, WNT
[4] Wirth N.: Algorytmy + Struktury Danych = Programy; WNT, Warszawa 1989
4
8694514.004.png 8694514.005.png 8694514.006.png 8694514.007.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin