profil

Algorytmy - podstawy

drukuj
satysfakcja 39 % 235 głosów

Treść
Obrazy
Wideo
Opinie

Algorytm jest to sformalizowany ciąg logicznie powiązanych instrukcji (poleceń, rozkazów), których wykonanie pozwoli na przetworzenie informacji wejściowych (danych) w informacje wyjściowe (wyniki).
Przetwarzanie informacji to zadanie problemowe, które możemy nazwać "rozwiązywaniem zadań".
Szerzej algorytmem możemy nazwać sformalizowane rozwiązywanie krok po kroku dowolnego problemu.

Na całościowe rozwiązanie problemu składają się :
• wybór metody rozwiązania problemu
• plan zastosowania tej metody do rozwiązania problemu
• opis czynności wykonywanych podczas realizacji tego planu wraz z opisem ich skutków
• ostateczny wynik wykonywanych czynności
Czynności służące do rozwiązania zadania (kroki) to :
• analiza treści zadania
• wykaz danych wejściowych; wiadomych i niewiadomych oraz relacji między nimi
• sprawdzenie czy zadanie posiada jednoznaczne rozwiązanie
• wybór metody rozwiązania zadania
• opis czynności, które należy wykonać z danymi wejściowymi przy zastosowaniu
• wybranej metody rozwiązania
• sporządzenie i przedstawienie wyników rozwiązania zadania
• Urządzenie techniczne, które może realizować algorytm nosi nazwę automatu (żelazko z termoregulatorem, lodówka, pralka automatyczna). Uniwersalnym automatem do realizacji algorytmów z zakresu przetwarzania danych jest komputer.

Składowe algorytmu to :
• nazwa algorytmu,
• opis obiektów
• deklaracja stałych i zmiennych tekstowych i liczbowych
• deklaracja funkcji użytkownika
• opis czynności jakie należy wykonać z obiektami, co realizujemy za pomocą instrukcji, które opisują nie tylko sposób działania i kolejność ich wykonywania ale również ewentualne warunki jakie muszą być spełnione w celu uzyskania prawidłowego rozwiązania
• opis wyników - zawiera sposób udostępnienia wyników rozwiązanego zadania


Przykłady algorytmów to :
• Algorytm Euklidesa
• Algorytmy sortowania
• Algorytmy kompresji
• Algorytmy sztucznej inteligencji
• Algorytmy przeszukiwania drzew: min-max i alpha-beta

Algorytmy sortowania
W życiu codziennym często spotykamy się z faktem porządkowania np., aby łatwiej było znaleźć hasło w słowniku są one uporządkowane wg określonych zasad.

Sortowanie - proces ustawienia zbioru obiektów w określonym porządku

Metody sortowania:
1. przez zamianę (sortowanie bąbelkowe)
2. przez wybieranie
3. przez wstawianie


Ad.1 Jedną z popularnych metod sortowania jest sortowanie przez prostą zamianę (sortowanie bąbelkowe). W metodzie tej porównujemy sąsiednie elementy. W celu uporządkowania elementów od najmniejszego do największego, jeśli drugi element jest mniejszy od poprzedniego, to zamieniamy go miejscami. Następnie element, który stał się drugim, porównujemy z trzecim i przestawiamy, jeśli jest mniejszy itd.
Przykład:
7 6 1 9 5 - porównujemy 7 i 6 ( przestawiamy, bo 6 < 7)
6 7 1 9 5 - porównujemy 7 i 1 ( przestawiamy, bo 1 < 7)
6 1 7 9 5 - porównujemy 7 i 9 ( nie przestawiamy, bo 10 > 7)
6 1 7 9 5 - porównujemy 9 i 5 ( przestawiamy, bo 5 < 10)
6 1 7 5 9 - 9 na właściwym miejscu
….
Aż do uzyskania odpowiedniego porządku


Ad.2 Polega na wyszukaniu najmniejszej liczby, przestawieniu jej na początek ciągu elementów (czyli zamienieniu jej z pierwszą liczbą ciągu) i takim samym postępowaniu dalszym z pominięciem pierwszego elementu.
Przykład:
7 6 1 9 5 - 1 na pierwszą pozycję, 7 w miejsce 1
1 6 7 9 5 - 5 na drugą pozycję, 6 w miejsce 5
1 5 7 9 6 - 6 na trzecią pozycję, 7 w miejsce 6
1 5 6 9 7 - 7 na czwartą pozycję, 9 w miejsce 7
1 5 6 7 9 - 9 na właściwym miejscu (piątym)

Ad.3 Sortowanie przez wstawianie
Metoda porządkowania przez wybór polega na wstawianiu elementu we właściwe miejsce, jest ona powszechnie stosowana przez osoby grające w karty.

7| 6 1 9 5
6 7| 1 9 5
1 6 7| 9 5
1 6 7 9| 5
1 6 7 5 9|

Na schemacie kreska oddziela posortowaną lewą część liczb od nieposortowanej prawej części. Jeśli pragniemy ustawić liczby w kolejności od najmniejszego do największego, to bierzemy element drugi i jeśli jest on mniejszy od pierwszego to wstawiamy przed nim. Następnie bierzemy element trzeci i wstawiamy również w odpowiednie miejsce, a więc jeśli jest mniejszy od pierwszego to przed pierwszy, jeśli mniejszy od drugiego to przed drugi.

Kompresja - ogólnie działanie mające na celu zmniejszenie wielkości czegoś (czyli zwiększenia gęstości). Np. wody (fizyka). Działaniem przeciwnym do kompresji jest dekompresja.
W informatyce chodzi o działania mające na celu zmniejszenie objętości informacyjnej danych, czyli wyrażenie zestawu danych za pomocą mniejszej ilości bitów.

Sztuczna Inteligencja (ang. [Artificial Intelligence]) (AI) to technologia i kierunek badań informatycznych, którego zadaniem jest "Konstruowanie maszyn, o których działaniu dałoby się powiedzieć, że są podobne do ludzkich przejawów inteligencji",

Istnieją dwa różne podejścia do pracy nad AI. Pierwsze, to tworzenie całościowych modeli matematycznych analizowanych problemów i implementowanie ich w formie programów komputerowych mających realizować konkretne cele. Drugie to próby tworzenia struktur i programów "samouczących się", takich jak modele [sieci neuronowych]? oraz opracowywania procedur rozwiązywania problemów poprzez "uczenie" takich programów a następnie uzyskiwanie od nich odpowiedzi na "pytania".

Algorytm min-max to najprostszy algorytm przeszukiwania drzew mający zastosowanie w komputerowych nielosowych algorytmach gry w dwie osoby, np. szachów.
Wybieramy ten ruch który po ruchu przeciwnika ma "największą najmniejszą" wartość (stąd nazwa). Czyli dla każdego ruchu symulujemy wszystkie możliwe ruchy przeciwnika i za wartość danego naszego ruchu uznajemy wartość najlepszego z punktu przeciwnika ruchu który może on wykonać jeśli my wykonamy dany ruch (część min). Potem wybieramy ruch o najwyższej wartości (część max).

Wartość sytuacji można szacować rekurencyjnie algorytmem min-max, jednak po kilku poziomach konieczne jest użycie jakiejś innej funkcji, np. przyjmującej 1 dla wygranej, 0 dla przegranej i inną wartość dla pozostałych sytuacji.

Algorytm alpha-beta to zoptymalizowana postać algorytmu min-max. Podczas przeszukiwania zachowane są dwie wartości: α - najlepszy jak na razie nasz ruch i β - najlepszy jak na razie dla przeciwnika ruch w przypadku danego naszego ruchu. Przeszukiwanie ruchów przeciwnika możemy zakończyć kiedy β spadnie poniżej α, czyli w przypadku wykonania przez nas danego ruchu przeciwnik potrafi wykonać taki ruch, że nasz wynik będzie niższy niż dla jakiegoś innego naszego ruchu.

Rodzaje zapisu algorytmów
Opis słowny - polega na logicznym i zrozumiałym dla odbiorcy przedstawieniu kolejnych czynności (akcji), jakie należy wykonać, aby osiągnąć zamierzony efekt. Przykładami takiego opisu algorytmu mogą być: przepis kulinarny,
Schemat blokowy - jest jedną z najpopularniejszych form przedstawiania algorytmu.
Rodzaje sieci działań:
Proste (sekwencyjne) - nie używa się w nich bloków warunkowych. W takiej sieci działań kolejność realizacji poszczególnych operacji jest ściśle określona i żadna z nich nie może być pominięta ani powtórzona.
Z rozwidleniem - zawiera w sobie wybór jednej z kilku możliwych dróg realizacji danego zadania. Istnieje w nim przynajmniej jeden blok warunkowy.
Z pętlą, często w trakcie realizacji danego zadania konieczne jest powtórzenie niektórych operacji różniących się jedynie zestawem danych. Pętla obejmuje tą część bloków, która ma być powtarzana.
Złożone - będące kombinacją powyższych sieci.

ZASADY BUDOWY SCHEMATU BLOKOWEGO
1) Każda operacja jest umieszczona w skrzynce
2) Schemat ma tylko jedną skrzynkę "początek" i przynajmniej jedną skrzynkę "koniec"
3) Skrzynki są ze sobą połączone.
4) Ze skrzynki wychodzi jedno połączenie; wyjątek stanowią skrzynki: "koniec" (z której nie wychodzą już żądne połączenia) oraz "warunkowa"
(z której wychodzą dwa połączenia opisane TAK i NIE - w zależności od tego, czy warunek jest spełniony czy nie, można wyjść jedną z dwóch dróg)
5) W skrzynce "operacyjnej" zamiast znaku "=" pojawia się oznaczenie ":="




Załączniki:
Przydatna praca? Tak Nie
Podobne prace:
Wersja ściąga: algorytmy_-_podstawy.doc
Komentarze (8) Brak komentarzy zobacz wszystkie
22.8.2011 (18:23)

trochę tu misz-masz - jakby za dużo wrzucone do jednego krótkiego artykułu - np. Przykłady algorytmów to :
• Algorytmy sztucznej inteligencji
akurat nie algorytmy sztucznej intelig. nie przytaczałbym przy podawaniu przykładów algorytmów :) przecież to artykuł dla początkujących

15.2.2011 (11:11)

i Ja tez ale znalezlem cos czego nie szukalem ;p

30.9.2009 (14:00)

To nie ma żadnego związku z tym co szukam

26.5.2009 (11:33)

Jop to wql jest bez sensu nie wiem w czym mi to pomorze...

Zal...

22.11.2008 (18:59)

Moze i praca ładna ale dla mni w niczym nie pomogła...



xpitux0 rozwiązanych zadań
Informatyka 10 pkt 21.11.2014 (19:23)

dam konto na world of tanks za konto na pandoramt2

Rozwiązań 1 z 2
punktów za rozwiązanie do 8 rozwiązań 1 z 2
Rozwiązuj

angelika00990 rozwiązanych zadań
Informatyka 12 pkt 19.11.2014 (20:54)

Napisz w punktach jak sie robi trąbke prosze

Rozwiązań 1 z 2
punktów za rozwiązanie do 9 rozwiązań 1 z 2
Rozwiązuj

angelika199128010 rozwiązanych zadań
punktów za rozwiązanie do 38 rozwiązań 0 z 2
Rozwiązuj

Masz problem z zadaniem?

Tu znajdziesz pomoc!
Wyjaśnimy Ci krok po kroku jak
rozwiązać zadanie.

Zaloguj się lub załóż konto

Serwis stosuje pliki cookies w celu świadczenia usług. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w urządzeniu końcowym. Możesz dokonać w każdym czasie zmiany ustawień dotyczących cookies. Więcej szczegółów w Serwis stosuje pliki cookies w celu świadczenia usług. Więcej szczegółów w polityce prywatności.