algorytmy-kopia.pdf

Programowanie to proces projektowania, tworzenia i

poprawiania kodu źródłowego programów

komputerowych lub urządzeń mikroprocesorowych

Kod źródłowy pisze się z użyciem reguł określanych

przez wybrany język programowania. Programowanie

wymaga dużej wiedzy i doświadczenia w wielu różnych

dziedzinach, jak projektowanie aplikacji, algorytmika

czy działanie komputerów. W inżynierii

oprogramowania, programowanie (implementacja) jest

tylko jednym z etapów powstawania programu.

Implementacja jest to proces pisania programu (kodu źródłowego)

Sposób na rozwiązanie jakiegoś problemu

Algorytm – w matematyce oraz informatyce to skończony,

uporządkowany ciąg jasno zdeﬁniowanych czynności,

koniecznych do wykonania pewnego zadania.

Algorytm ma przeprowadzić system z pewnego stanu

początkowego do pożądanego stanu końcowego.

Algorytm to jednoznaczny przepis przetworzenia w

skończonym czasie pewnych danych wejściowych

do pewnych danych wynikowych.

Np. obliczenie pola prostokąta

dane wejściowe to boki a wynikowe to

rozmiar pola

Metody algorytmiczne

• dziel i zwyciężaj, czyli dzielimy problem na małe

• wędruj i sprawdzaj (np. w celu znalezienia max) lub

dokonuje zachłannego, tj. najlepiej rokującego w danym

momencie wyboru rozwiązania częściowego. Innymi słowy algorytm

zachłanny nie patrzy czy w kolejnych krokach jest sens wykonywać dane działanie,

dokonuje decyzji lokalnie optymalnej (np. podróż z Gdańska do Krakowa, jak

najszybciej lub proble wydawania reszty [6zł mając monety 2 i 5 w pierwszym

kroku 5 bo bliżej 6, a co dalej?] lub przyklad 13zł min monet przy nominałach

1,2,5)

• Algorytm probabilistyczny albo randomizowany to algorytm który do swojego działania używa

losowości . Powiedzmy, że w jakiejś tablicy musimy znaleść “a”. Tablica jest wypełniona tylko

“a” i “b”. Istnieje ryzyko, że litery są ułożone tak że po zbadaniu połowy tab. traﬁmy na “a” bo

na samym początku jest tylko “b”, to samo od końca, ale jeśli będziemy strzelać na oślep to

istnieje 50% prawdopodobieństwo że traﬁmy.

• heurystyka – człowiek na podstawie swojego doświadczenia tworzy zupełnie nowy algorytm, który działa

w najbardziej prawdopodobnych warunkach, rozwiązanie zawsze jest przybliżone .

heurestyka - umiejętność wykrywania nowych faktów oraz znajdywania związków między faktami,

Metodę używa się też często do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny wynik innym algorytmem.

części (podobne do siebie), rozwiązujem je i

łączymy w całość (szybie sortowanie)

metoda siłowa

• algorytm, który w celu wyznaczenia rozwiązania w każdym kroku

# a) Blok graniczny - oznacza on początek, koniec, przerwanie lub wstrzymanie

wykonywania działania, np. blok startu programu.

# b) Blok wejścia-wyjścia - przedstawia czynność wprowadzania danych do

programu i przyporządkowania ich zmiennym dla późniejszego wykorzystania,

jak i wyprowadzenia wyników obliczeń, np. czytaj z, pisz z+10.

# c) Blok obliczeniowy - oznacza wykonanie operacji, w efekcie której zmienią

się wartości, postać lub miejsce zapisu danych, np. z = z + 1.

# d) Blok decyzyjny - przedstawia wybór jednego z dwóch wariantów

wykonywania programu na podstawie sprawdzenia warunku wpisanego w ów

blok, np. a = b.

# e) Blok wywołania podprogramu - oznacza zmianę wykonywanej czynności

na skutek wywołania podprogramu, np. MAX(x,y,z).

# f) Blok fragmentu - przedstawia część programu zdeﬁniowanego odrębnie,

np. sortowanie.

# g)Blok komentarza - pozwala wprowadzać komentarze wyjaśniające

poszczególne części schematu, co ułatwia zrozumienie go czytającemu, np.

wprowadzenie danych.

# h)Łącznik wewnętrzny - służy do łączenia odrębnych części schematu

znajdujących się na tej samej stronie, powiązane ze sobą łączniki oznaczone są

tym samym napisem, np. A1, 7.

# i) Łącznik zewnętrzny - służy do łączenia odrębnych części schematu

znajdujących się na odrębnych stronach, powinien być opisany jak łącznik

wewnętrzny, poza tym powinien zawierać numer strony, do której się odwołuje,

np. 4.3, 2,B2.

•

Sprawność algorytmów - poszukujemy w

nieuporządkowanej liście np. nr tel. Zwykły algorytm

jest pętlą, w której są dwa sprawdzenia 1) czy znalazł 2)

czy dotarliśmy do końca. Twierdząca odpowiedz na

którekolwiek pytanie to koniec. Załóżmy że te dwa

sprawdzenia są dominujące jeśli chodzi o czas

wykonywania algorytmu. Drugie sprawdzenie można

wynieść poza pętlę używając sztuczki, otóż przed

rozpoczęciem wyszukiwania ﬁkcyjnie dodajemy żądany

element X na koniec listy

•

USUWAĆ ZBĘDNE SPRAWDZENIA Z PĘTLI!!!

•

POPRAWNOŚĆ, np. algorytm, który dzieli a:b i nie

sprawdza, czy b<>0.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: