• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm



    Podstrony: 1 [2] [3] [4] [5]
    Przeczytaj także...
    GPGPU (ang. General-Purpose computing on Graphics Processor Units lub General-Purpose computation on Graphics Processing Units – obliczenia ogólnego przeznaczenia na układach GPU, zwany także GPGP, rzadziej GP) – technika, dzięki której GPU, zwykle zajmujący się tylko obliczeniami związanymi z grafiką komputerową, umożliwia wykonywanie obliczeń ogólnego przeznaczenia, tak jak CPU. Dzięki temu wiele obliczeń, głównie obliczenia równoległe, można przeprowadzić znacznie szybciej.Dziel i zwyciężaj (ang. divide and conquer) – jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania.

    Algorytm – skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo „algorytm” pochodzi od staroangielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwy "Algoritmi" - zlatynizowanej wersji nazwiska "al-Chwarizmi" Abu Abdullaha Muhammada ibn Musy al-Chuwarizmiego (arab. ‏أبو عبد الله محمد بن موسى الخوارزمي‎), matematyka perskiego z IX wieku.

    Programista, zwany też potocznie koderem to osoba, która tworzy programy komputerowe w pewnym języku programowania. Termin ten może odnosić się także do specjalisty w jednej dziedzinie programowania. Większość programistów zna co najmniej kilka języków programowania (np. C, C++, Java), lecz specjalizuje się tylko w wybranych z nich. Nazwa głównego języka jest często dodawana do nazwy stanowiska, np. programista C++, aby podkreślić specjalizację.Ronald Linn Rivest (ur. w 1947 w Schenectady, Nowy Jork) – informatyk, kryptograf. Za swój wkład w rozwój kryptografii asymetrycznej otrzymał w 2002 roku nagrodę Turinga. Pracuje na stanowisku profesora informatyki uniwersytetu MIT.

    Zadaniem algorytmu jest przeprowadzenie systemu z pewnego stanu początkowego do pożądanego stanu końcowego. Badaniem algorytmów zajmuje się algorytmika. Algorytm może zostać zaimplementowany w postaci programu komputerowego.

    Jako przykład stosowanego w życiu codziennym algorytmu podaje się często przepis kulinarny. Dla przykładu, aby ugotować bigos należy w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty i innych składników. Może istnieć kilka różnych przepisów dających na końcu bardzo podobną potrawę. Przykład ten ma wyłącznie charakter poglądowy, ponieważ język przepisów kulinarnych nie został jasno zdefiniowany. Algorytmy zwykle formułowane są w sposób ścisły w oparciu o język matematyki.

    Patent – potocznie: dokument wydawany przez urzędy patentowe; właściwie: ograniczone w czasie prawa właściciela rozwiązania technicznego do wyłącznego korzystania z wynalazku bądź wynalazków będących przedmiotem patentu w celach zawodowych lub zarobkowych na terenie państwa, które decyzją administracyjną patentu udzieliło, pod warunkiem wniesienia opłat za co najmniej pierwszy okres ochrony od daty zgłoszenia.Abakus lub abak (łac. abacus, gr. ἄβαξ, ábaks) – deska z wyżłobionymi rowkami, które symbolizowały kolejne potęgi dziesięciu. Ułatwiało liczenie, używane w Rzymie i Grecji od 440 p.n.e. do XVIII wieku - prekursor liczydła i maszyn liczących. Był używany także w innych krajach Europy. Obliczeń dokonywano poprzez wkładanie i przekładanie kamyków w rowkach. Zasada liczenia była taka sama jak na liczydle. Jedną z odmian abaku, stanowiącą poważne udoskonalenie, przypisywali Rzymianie pitagorejczykom i nazwali mensa pythagoreana. Chińczycy używali liczydła zwanego suanpan. Jest ono wytworem własnym pomysłowości chińskiej. Odmiana japońska nosi nazwę soroban (jap. 算盤, soroban).

    W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Przeciwnicy tego podejścia twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików (patrz.GIF). Wiele koncernów komputerowych prowadzi między sobą spory prawne dotyczące praw własności do niektórych patentów. Kontrargumentem zwolenników patentów na oprogramowanie jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu i pracy muzyka) zakładające, że program jest intelektualną własnością twórcy.

    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji. Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny. W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".

    Spis treści

  • 1 Definicja klasyczna
  • 1.1 Przykład
  • 1.2 Inne przykłady
  • 2 Klasyfikacja algorytmów
  • 2.1 Algorytmy równoległe
  • 2.2 Algorytmy sztucznej inteligencji
  • 2.3 Algorytmy genetyczne
  • 2.4 Algorytmy kwantowe
  • 3 Ograniczenia algorytmów
  • 4 Implementacja algorytmów
  • 4.1 Algorytmy komputerowe
  • 4.2 Algorytmy poza komputerami
  • 4.3 Algorytm a opisujący go język
  • 4.4 Błędy w implementacji
  • 5 Historia algorytmów
  • 5.1 Początki
  • 5.2 Rozwój maszyn liczących
  • 5.3 Komputery
  • 6 Przypisy
  • 7 Zobacz też
  • 8 Bibliografia
  • 9 Linki zewnętrzne
  • Algorytm Luhna – jeden z najczęściej wykorzystywanych algorytmów służących do sprawdzania poprawności wpisania danej liczby. Jest on używany m.in. do walidacji numerów kart kredytowych, ciągów liczbowych, itd. Nazwa algorytmu pochodzi od nazwiska Hansa Petera Luhna (1896–1964), niemieckiego naukowca pracującego w IBM.Wszechświat – wszystko, co fizycznie istnieje: cała przestrzeń, czas, wszystkie formy materii i energii oraz prawa fizyki i stałe fizyczne określające ich zachowanie. Słowo „wszechświat” może być też używane w innych kontekstach jako synonim słów „kosmos” (w rozumieniu filozofii), „świat” czy „natura”. W naukach ścisłych słowa „wszechświat” i „kosmos” są równoważne.

    Definicja klasyczna[]

    Algorytm – jednoznaczny przepis obliczenia w skończonym czasie pewnych danych wejściowych do pewnych danych wynikowych.

    Zazwyczaj przy analizowaniu bądź projektowaniu algorytmu zakłada się, że dostarczane dane wejściowe są poprawne, czasem istotną częścią algorytmu jest nie tylko przetwarzanie, ale i weryfikacja danych.

    Zgodnie z założeniem o jednoznaczności – dla identycznego zestawu danych początkowych, algorytm zdefiniowany klasycznie zawsze zwróci identyczny wynik.

    Zero (zapisywane jako 0) – element neutralny dodawania; najmniejsza nieujemna liczba. To, czy zero jest uznawane za liczbę naturalną, jest kwestią umowy – czasem włącza się, a czasem wyklucza się je z tego zbioru. Zero nie jest ani liczbą pierwszą, ani liczbą złożoną.Wielka Brytania, Zjednoczone Królestwo (ang. United Kingdom), Zjednoczone Królestwo Wielkiej Brytanii i Irlandii Północnej (ang. United Kingdom of Great Britain and Northern Ireland) – unitarne państwo wyspiarskie położone w Europie Zachodniej. W skład Wielkiej Brytanii wchodzą: Anglia, Walia i Szkocja położone na wyspie Wielka Brytania oraz Irlandia Północna leżąca w północnej części wyspy Irlandia. Na wyspie tej znajduje się jedyna granica lądowa Zjednoczonego Królestwa z innym państwem – Irlandią. Poza nią, Wielka Brytania otoczona jest przez Ocean Atlantycki na zachodzie i północy, Morze Północne na wschodzie, kanał La Manche na południu i Morze Irlandzkie na zachodzie.

    Przykład[]

    Znalezienie największej wśród niepustej, nieposortowanej listy przypadkowych liczb można przeprowadzić na wiele sposobów; jednym z najszybszych jest przedstawiony poniżej. Niech wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), a oznacza największą dotychczas znalezioną wartość.

    Programowanie liniowe – klasa problemów programowania matematycznego, w której wszystkie warunki ograniczające oraz funkcja celu mają postać liniową. Warunki ograniczające mają postać:Dowód poprawności algorytmu jest rozumowaniem matematycznym prowadzącym do formalnego wykazania, że dany algorytm przy poprawnych danych wejściowych da nam wynik spełniający wymagania, np. że algorytm quicksort po podaniu mu niepustej tablicy elementów porównywalnych na wyjściu da nam tablicę zawierającą te same elementy, ale uporządkowane w kolejności od najmniejszego do największego.
    1. Niech wskazuje na pierwszy element (początek) listy.
    2. Niech zawiera wartość elementu listy wskazywanego przez (tzn. pierwszego).
    3. Jeżeli zawartość elementu listy wskazywanego przez jest większa od zawartości to przypisz wartość elementu wskazywanego przez
    4. Niech wskazuje kolejny element listy; jeśli to niemożliwe (tzn. wskazuje ostatni element listy, czyli jej koniec), przejdź do punktu 6.
    5. Wróć do punktu 3.
    6. Koniec.

    Wykonanie tego algorytmu spowoduje, że największa liczba na wspomnianej liście będzie wartością . Dodatkowym atutem jest fakt, iż algorytm ten działa dla list dowolnej długości, ponieważ nie wykorzystuje on liczby elementów listy, lecz tylko tzw. operację następnika elementu danej listy, tzn. przejścia do następnego jej elementu. Niemożność wskazania kolejnego elementu jest wtedy równoważna temu, iż dany element jest ostatni na liście.

    Konrad Zuse (ur. 22 czerwca 1910 r. w Berlinie - zm. 18 grudnia 1995 r. w Hünfeld) – niemiecki inżynier, konstruktor, pionier informatyki; konstruktor prekursorskiego komputera działającego w systemie binarnym.RSA – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy algorytm, który może być stosowany zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.

    Inne przykłady[]

  • algorytm Euklidesa
  • algorytm Fermata
  • algorytm Luhna
  • algorytmy sortowania
  • algorytmy kompresji
  • algorytmy przeszukiwania drzew: min-max i alpha-beta
  • algorytm unifikacji
  • algorytmy kryptograficzne
  • algorytm mrówkowy


  • Podstrony: 1 [2] [3] [4] [5]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    Rozkład na czynniki lub faktoryzacja – proces, w którym dla danego obiektu znajdują się obiekty, takie że ich iloczyn jest jemu równy, przez co są one w pewnym sensie od niego prostsze.
    Komputer osobisty (ang. personal computer) – mikrokomputer przeznaczony przede wszystkim do użytku osobistego w domu i biurze. Służy głównie do uruchamiania oprogramowania biurowego, dostępu do zasobów Internetu, prezentacji treści multimedialnych (tekst, obrazy, dźwięki, filmy i inne), jak i gier.
    Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie.
    Kompresja danych (ang. data compression) – polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć redundancję i tym samym objętość zbioru. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów.
    Plik (ang. file) – uporządkowany zbiór danych o skończonej długości, posiadający szereg atrybutów i stanowiący dla użytkownika systemu operacyjnego całość. Nazwa pliku nie jest częścią tego pliku, lecz jest przechowywana w systemie plików.
    Spintronika, (elektronika spinowa, magnetronika) jest odmianą elektroniki. Podczas gdy w tradycyjnych układach scalonych nośnikiem informacji są zmiany w przepływie prądu, w spintronice brany jest pod uwagę również spin elektronu.
    Stany Zjednoczone, Stany Zjednoczone Ameryki (ang. United States, US, United States of America, USA) – federacyjne państwo w Ameryce Północnej graniczące z Kanadą od północy, Meksykiem od południa, Oceanem Spokojnym od zachodu, Oceanem Arktycznym od północnego zachodu i Oceanem Atlantyckim od wschodu.

    Reklama