Programowanie.pdf

(221 KB) Pobierz

Programowanie

komputerowe

Wykład 3(4)

Podstawy algorytmów

Jerzy Duda, 2010

Algorytmy

Algorytm opisuje krok po kroku rozwiązanie jakiegoś problemu lub

osiągnięcie wyznaczonego celu /Sysło/

Algorytm to skończony, uporządkowany ciąg jasno zdefiniowanych

czynności, koniecznych do wykonania pewnego zadania

Słowo "algorytm" pochodzi od nazwiska Muhammed ibn Musa al-

Choremiego , arabskiego matematyka Ŝyjącego na przełomie VIII i IX w.

Zadanie stanowi problem, czyli pytanie na które szukamy odpowiedzi

Przykład problemu 1:

Posortuj w porządku niemalejącym listę S, zawierającą n liczb.

Odpowiedzią są liczby w postaci posortowanego ciągu.

Przykład problemu 2:

Określ, czy liczba x znajduje się na liście S, zawierającej n liczb.

Odpowiedź jest twierdząca, jeŜeli x występuje w S, w przeciwnym

wypadku jest przecząca.

Jerzy Duda, WZ AGH, 2008-2010

Źródła: wikipedia, Szkolny Leksykon Informatyczny, Neapolitan, Naimipour "Podstawy algorytmów"

1

803183702.130.png

803183702.141.png

803183702.152.png

803183702.163.png

803183702.001.png

803183702.012.png

803183702.023.png

803183702.034.png

803183702.045.png

803183702.056.png

803183702.067.png

803183702.078.png

803183702.088.png

803183702.089.png

803183702.090.png

803183702.091.png

803183702.092.png

803183702.093.png

803183702.094.png

803183702.095.png

Problem – realizacje

Problem moŜe zawierać zmienne, którym przypisane są pewne

wartości w momencie jego postawienia

Takie zmienne noszą nazwę parametrów problemu

KaŜde konkretne przypisanie wartości do parametrów nosi nazwę

realizacji (ang. instance ) problemu

Rozwiązaniem realizacji problemu jest odpowiedź na pytanie

postawione przez problem w danej realizacji

Przykładowa realizacja problemu 1:

S = [10, 7, 11, 5 ,13, 8], n = 6

Rozwiązanie problemu 1:

S = [5, 7, 8, 10, 11 ,13]

Źródło: wikipedia, Szkolny Leksykon Informatyczny, Neapolitan, Naimipour "Podstawy algorytmów..."

Jerzy Duda, WZ AGH, 2008-2010

Algorytmy – rozwiązanie

Algorytm rozwiązuje problem, jeŜeli potrafi znaleźć odpowiedź dla

wszystkich realizacji problemu

Przykładowa realizacja problemu 2:

S = [10, 7, 11, 5 ,13, 8], n = 6, x = 5

Algorytm dla problemu 2:

Rozpoczynając od pierwszego elementu w S porównujemy x z kaŜdym

elementem w S po kolei, aŜ do momentu, gdy znajdziemy w S element x

lub wyczerpiemy wszystkie elementy z S . W razie znalezienia elementu x

odpowiedź jest twierdząca, a w przeciwnym wypadku – przecząca.

Rozwiązanie problemu 2:

tak, x występuje w S

Źródło: Neapolitan, Naimipour "Podstawy algorytmów..."

Jerzy Duda, WZ AGH, 2008-2010

2

803183702.096.png

803183702.097.png

803183702.098.png

803183702.099.png

803183702.100.png

803183702.101.png

803183702.102.png

803183702.103.png

803183702.104.png

803183702.105.png

803183702.106.png

803183702.107.png

803183702.108.png

803183702.109.png

803183702.110.png

803183702.111.png

803183702.112.png

803183702.113.png

803183702.114.png

803183702.115.png

803183702.116.png

Algorytmy

Algorytm to skończony ciąg działań elementarnych, który określa

sposób otrzymania rozwiązania zadania z danych wejściowych

/ Markov /

Algorytm to sekwencja kroków obliczeniowych, która transformuje

wejście w wyjście / Cormen /

D. Knuth – cechy algorytmu:

Skończoność – algorytm musi się zakończyć po wykonaniu określonej

liczby kroków

Poprawne zdefiniowanie – kaŜdy krok musi być precyzyjnie i

jednoznacznie określony

Dane wejściowe – kaŜdy algorytm ma na wejściu 0 lub więcej wartości

wejściowych, znanych przed jego rozpoczęciem

Dane wyjściowe – algorytm tworzy jedną lub więcej wartości wyjściowych,

powiązanych z wartościami wejściowymi

Efektywne zdefiniowane – operacje powinny być jak najprostsze, moŜliwe

do precyzyjnego wykonania "na papierze" w skończonym czasie

Jerzy Duda, WZ AGH, 2008-2010

Źródła: wikipedia, D. Knuth: Art of computer programming, vol. 1

Algorytmy – pseudokod

Algorytm moŜna opisać:

zwykłym językiem

za pomocą tzw. pseudokodu

stosując schematy blokowe

Pseudokod zachowując strukturę charakterystyczną dla kodu

zapisanego w języku programowania, rezygnuje ze ścisłych reguł

składniowych na rzecz prostoty i czytelności

indeks = 1

While indeks<=n

And s(indeks)<>x

indeks=indeks+1

Wend

If indeks>n Then

p=False

Else

p=True

End If

WHILE indeks <=n

AND x nie jest w S

zwiĘksz indeks

IF indeks>n

zwróĆ false

ELSE

zwróĆ true

Jerzy Duda, WZ AGH, 2008-2010

Źródło: wikipedia, Neapolitan, Naimipour "Podstawy algorytmów..."

3

803183702.117.png

803183702.118.png

803183702.119.png

803183702.120.png

803183702.121.png

803183702.122.png

803183702.123.png

803183702.124.png

803183702.125.png

803183702.126.png

803183702.127.png

803183702.128.png

803183702.129.png

803183702.131.png

803183702.132.png

803183702.133.png

803183702.134.png

803183702.135.png

803183702.136.png

803183702.137.png

Algorytmy – schemat blokowy (1)

Norma ISO 5807:1985 definiuje 3 podstawowe symbole dla

schematów blokowych (ang. flowcharts )

IBM ( IBM Flowcharting Templates ) określił kilkanaście dodatkowych

symboli, np.

Pełna lista symboli: http://www.fh-jena.de/~kleine/history/software/IBM-FlowchartingTechniques-GC20-8152-1.pdf

Jerzy Duda, WZ AGH, 2008-2010

Algorytmy – schemat blokowy (2)

Jerzy Duda, WZ AGH, 2008-2010

4

803183702.138.png

803183702.139.png

803183702.140.png

803183702.142.png

803183702.143.png

803183702.144.png

803183702.145.png

803183702.146.png

803183702.147.png

803183702.148.png

803183702.149.png

803183702.150.png

803183702.151.png

803183702.153.png

803183702.154.png

803183702.155.png

803183702.156.png

803183702.157.png

803183702.158.png

803183702.159.png

803183702.160.png

803183702.161.png

803183702.162.png

803183702.164.png

803183702.165.png

803183702.166.png

803183702.167.png

803183702.168.png

803183702.169.png

803183702.170.png

803183702.171.png

803183702.172.png

803183702.173.png

803183702.002.png

803183702.003.png

803183702.004.png

803183702.005.png

803183702.006.png

803183702.007.png

803183702.008.png

803183702.009.png

803183702.010.png

803183702.011.png

803183702.013.png

803183702.014.png

803183702.015.png

803183702.016.png

803183702.017.png

803183702.018.png

803183702.019.png

803183702.020.png

803183702.021.png

803183702.022.png

803183702.024.png

803183702.025.png

803183702.026.png

803183702.027.png

803183702.028.png

803183702.029.png

803183702.030.png

803183702.031.png

803183702.032.png

803183702.033.png

803183702.035.png

803183702.036.png

803183702.037.png

803183702.038.png

803183702.039.png

803183702.040.png

803183702.041.png

803183702.042.png

803183702.043.png

803183702.044.png

803183702.046.png

803183702.047.png

803183702.048.png

803183702.049.png

803183702.050.png

803183702.051.png

803183702.052.png

803183702.053.png

803183702.054.png

803183702.055.png

803183702.057.png

803183702.058.png

803183702.059.png

803183702.060.png

803183702.061.png

803183702.062.png

Algorytmy sortowania – podstawianie

Proste (naiwne)

Zaawansowane (logarytmiczne)

Jednym z najprostszych algorytmów sortowania jest sortowanie przez

podstawianie

Polega na porównywaniu kolejnych elementów tablicy i zamianie

elementu o mniejszej wartości z elementem o wartości większej.

Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy

dla kolejnych elementów na pozycji i :

dla kolejnych elementów na pozycji j , większej od i :

jeŜeli element na pozycji j jest mniejszy od elementu na pozycji i , zamień je miejscami

For i=1 To n-1

For j=i+1 To n

If s(j)<s(i) Then

zamien s(i) z s(j)

End If

Next j

Next i

[10, 7, 11, 5 ,13, 8]

[ 7 , 10 , 11, 5 ,13, 8]

[ 7 , 10, 11 , 5 ,13, 8]

[ 5 , 10, 11, 7 , 13, 8]

[ 5 , 10, 11, 7 , 13 , 8]

[ 5 , 10, 11, 7 ,13, 8 ]

i=1

Jerzy Duda, WZ AGH, 2008-2010

Źródło: Neapolitan, Naimipour "Podstawy algorytmów"

Algorytmy sortowania – bąbelkowe

Innym wariantem jest tzw. sortowanie bąbelkowe

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich

kolejności, jeŜeli zaburza ona porządek, w jakim sortuje się tablicę.

[ 10 , 7 , 11, 5 ,13, 8]

[7, 10 , 11 , 5 ,13, 8]

[7, 10, 11 , 5 ,13, 8]

[7, 10, 5, 11 , 13 , 8]

[7, 10, 5, 11 , 13 , 8 ]

[7, 10, 5, 11, 8, 13]

For i=1 to n

For j=1 To n-i

If s(j)>s(j+1)

zamien s(j) z s(j+1)

Next j

Next i

[ 7 , 10 , 5, 11, 8, 13]

[7, 10 , 5 , 11, 8, 13]

[7, 5, 10 , 11 , 8, 13]

[7, 5, 10, 11 , 8 , 13]

[7, 5, 10, 8, 11 , 13 ]

[7, 5, 10, 8, 11, 13]

Jerzy Duda, WZ AGH, 2008-2010

Źródło: wikipedia

5

803183702.063.png

803183702.064.png

803183702.065.png

803183702.066.png

803183702.068.png

803183702.069.png

803183702.070.png

803183702.071.png

803183702.072.png

803183702.073.png

803183702.074.png

803183702.075.png

803183702.076.png

803183702.077.png

803183702.079.png

803183702.080.png

803183702.081.png

803183702.082.png

803183702.083.png

803183702.084.png

803183702.085.png

803183702.086.png

803183702.087.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin