• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Złożoność Kołmogorowa

    Przeczytaj także...
    Liczba π (czytaj: liczba pi), ludolfina – stała matematyczna, która pojawia się w wielu dziedzinach matematyki i fizyki. W geometrii euklidesowej π jest równe stosunkowi długości obwodu koła do długości jego średnicy. Można też zdefiniować π na inne sposoby, na przykład jako pole koła o promieniu równym 1 albo jako najmniejszą dodatnią wartość x, dla której funkcja sinus przyjmuje wartość 0.Definicja intuicyjna: Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej „głowicy”, wykonującej proste operacje na zapisanych na taśmie wartościach.
    Andriej Nikołajewicz Kołmogorow, ros. Андре́й Никола́евич Колмого́ров (ur. 25 kwietnia 1903, zm. 20 października 1987) – rosyjski matematyk, twórca współczesnej teorii prawdopodobieństwa. Pracował nad rozwojem topologii, logiki i teorii złożoności obliczeniowej, znany jest również z wyników w analizie harmonicznej i mechanice klasycznej - w szczególności w badaniach turbulencji. Laureat wielu nagród, m.in. Nagrody Wolfa w matematyce w 1980.

    Złożoność Kołmogorowa – długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa.

    Tekstowy typ danych (ang. String) – typ danych służący do przechowywania ciągu znaków (zmiennych łańcuchowych).Izomorfizm (gr. isos – równy, morphe – kształt) − funkcja wzajemnie jednoznaczna z jednego obiektu matematycznego w drugi, która zachowuje funkcje, relacje i wyróżnione elementy.

    Rozwinięcie dziesiętne liczby pi, choć nieskończone, ma bardzo niską złożoność Kołmogorowa, ponieważ istnieje bardzo prosty program, który generuje dowolną liczbę jej cyfr. Złożoność Kołmogorowa jest różna dla różnych komputerów (ściślej – maszyn Turinga lub obiektów izomorficznych z nimi). Ze względu na nierozstrzygalność problemu stopu nie może istnieć algorytm obliczający złożoność Kołmogorowa z gwarancją sukcesu.

    Problem stopu – zagadnienie algorytmiczne odpowiadające dla danego algorytmu na pytanie, czy realizujący go program zatrzyma się (w skończonym czasie); pytanie może dotyczyć konkretnych danych wejściowych albo wszystkich możliwych. O programie, który zatrzymuje się dla wszystkich możliwych danych mówi się, że ma własność stopu.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego 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 nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
    Oprogramowanie (ang. software) – całość informacji w postaci zestawu instrukcji, zaimplementowanych interfejsów i zintegrowanych danych przeznaczonych dla komputera do realizacji wyznaczonych celów. Celem oprogramowania jest przetwarzanie danych w określonym przez twórcę zakresie. Oprogramowanie to dział informatyki. Oprogramowanie jest synonimem terminów program komputerowy oraz aplikacja, przy czym stosuje się go zazwyczaj do określania większych programów oraz ich zbiorów.



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

    Reklama