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



    Podstrony: 1 [2] [3] [4] [5]
    Przeczytaj także...
    Encyklopedia PWN – encyklopedia internetowa, oferowana – bezpłatnie i bez konieczności uprzedniej rejestracji – przez Wydawnictwo Naukowe PWN. Encyklopedia zawiera około 122 tysiące haseł i 5 tysięcy ilustracji.Teleportacja kwantowa (QT z ang. quantum teleportation) – w kwantowej teorii informacji technika pozwalająca na przeniesienie stanu kwantowego na dowolną odległość z wykorzystaniem stanu splątanego.

    Algorytm – skończony ciąg jasno zdefiniowanych czynności koniecznych do wykonania pewnego rodzaju zadań, sposób postępowania prowadzący do rozwiązania problemu.

    Słowo „algorytm” pochodzi od łacińskiego słowa algorithmus, 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, matematyka perskiego z IX wieku.

    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.

    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.

    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.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 (między innymi Stanach Zjednoczonych) 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 na pisanie oprogramowania tworzącego pewne typy plików (jak było to w przypadku 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 prawo własności intelektualnej (którą jest na przykład 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.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.

    Definicja klasyczna

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

    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".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.

    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.

    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 indeks wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), a maksimum 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 indeks wskazuje na pierwszy element (początek) listy.
    2. Niech maksimum zawiera wartość elementu listy wskazywanego przez indeks (tzn. pierwszego).
    3. Jeżeli zawartość elementu listy wskazywanego przez indeks jest większa od zawartości maksimum, to przypisz maksimum wartość elementu wskazywanego przez indeks.
    4. Niech indeks wskazuje kolejny element listy; jeśli to niemożliwe (tzn. indeks 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ą maksimum. 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.Wielomian – wyrażenie algebraiczne złożone ze zmiennych i stałych połączonych działaniami dodawania, odejmowania, mnożenia i podnoszenia do potęgi o stałym wykładniku naturalnym.

    Inne przykłady

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


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




    Warto wiedzieć że... beta

    Intelekt – (łac. intellectus: percepcja, postrzeganie, poznanie), zdolności umysłowe, kultura umysłowa człowieka (potencjalnie również istot pozaziemskich czy sztucznej inteligencji). Odnosi się do zdolności uzyskania i wykorzystania wiedzy, rozumienia myśli, poznania. Również inna nazwa umysłu, rozumu, inteligencji (w odróżnieniu od uczuć, woli, zmysłów). Ogólnie rzecz ujmując jest iloczynem zdolności umysłowych, doświadczenia oraz wiedzy człowieka i możliwości ich wykorzystywania. Termin ten jest ściśle związany z rozsądkiem i rozumieniem.
    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.
    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.
    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.
    Programowanie proceduralne to paradygmat programowania zalecający dzielenie kodu na procedury, czyli fragmenty wykonujące ściśle określone operacje.

    Reklama

    Czas generowania strony: 0.042 sek.