Przeskocz do treści

Delta mi!

  1. Algorytmy

    Kwantowe wyżarzanie „klasycznej” optymalizacji

    Wydaje się, że moc, szybkość obliczeniowa współczesnych komputerów, bazujących na krzemie, osiąga swoje plateau wynikłe z ograniczeń natury materiałowej. Jednocześnie w wielu dziedzinach życia codziennego, poczynając od prób unikania korków w planowanej podróży, poprzez minimalizację kosztochłonności produkcji aż po liczne zaawansowane zagadnienia badawcze z zakresu teorii sterowania, staramy się optymalizować nasze postępowanie. Wobec wspomnianych ograniczeń sprzętowych pozostaje nam poszukiwanie nowych algorytmów dla optymalizacji lub zupełnie nowych paradygmatów obliczeniowych - być może kwantowych?

  2. Algorytmy Co to jest?

    Algorytm faktoryzacji Shora

    W 1994 roku Peter Shor, pracujący wówczas w Bell Labs w New Jersey, pokazał, jak przy użyciu hipotetycznego komputera kwantowego rozłożyć w czasie wielomianowym dowolną liczbę naturalną na czynniki pierwsze. W tamtym czasie algorytmy kwantowe dopiero raczkowały. To właśnie odkrycie Shora spowodowało wielki rozwój tej dziedziny. Społeczność informatyków zrozumiała, że gdyby udało się zbudować komputer kwantowy rozsądnej wielkości, to świat stałby się istotnie inny. Nie jest bowiem znany żaden algorytm dla problemu faktoryzacji, czyli rozkładu na dzielniki pierwsze, który działa w czasie wielomianowym na komputerze klasycznym. Co więcej, nawet nie znaleziono algorytmu losowego, który z dużym prawdopodobieństwem w zazwyczaj niedługim czasie faktoryzuje liczbę: nie jest po prostu znana zupełnie żadna rozsądna heurystyka...

  3. Algorytmy

    Dlaczego problem |P ? NP jest tak trudny?

    24 maja 2000 roku Instytut Matematyczny Claya ogłosił listę siedmiu Problemów Milenijnych, czyli zagadnień, które zostały uznane za najważniejsze otwarte problemy matematyczne opierające się rozwiązaniom od lat. Wśród nich był jeden problem zaliczany do informatyki teoretycznej, o którym wielu Czytelników zapewne słyszało. Chodzi oczywiście o tytułowy problem: "Czy P=NP"? Jest on powszechnie uznawany za najważniejsze pytanie informatyki teoretycznej.

  4. Algorytmy

    Ludziom małej wiary

    Świat informatyki teoretycznej pełen jest hipotez, które badacze przyjmują po prostu na wiarę. Niektórzy wierzą, na przykład, że |P ≠NP; inni wierzą, że istnieje bezpieczna kryptografia klucza publicznego (albo jeszcze konkretniej: wierzą, że szyfrowanie RSA jest bezpieczne). Co ciekawe, najpopularniejsze hipotezy informatyczne bynajmniej nie są równoważne, a relacje między nimi mogą zaskakiwać.

  5. Algorytmy Co to jest?

    Algorytmy strumieniowe

    W dzisiejszym świecie cyfrowym mamy do czynienia z olbrzymią ilością danych, wielu Czytelników słyszało zapewne modne ostatnio hasło "Big Data". I trzeba sobie z tym radzić, a problemy mogą pojawiać się w nieoczekiwanych miejscach. Przyzwyczajeni jesteśmy do myślenia, że programy mają pewne dane na wejściu i te dane są tam na stałe, program może je w dowolnym momencie przeczytać. Czasami jednak nie do końca przystaje to do rzeczywistości...

  6. Algorytmy

    Problem Stopu

    Tak zwany Problem Stopu to problem decyzyjny, którego wejściem jest jakiś program Q i jakieś dane D; a którego rozwiązaniem (wyjściem) jest stwierdzenie, czy program Q uruchomiony na danych D zakończy swoje działania w skończonym czasie.

  7. Algorytmy

    Jak się pozbyć losowości?

    W informatyce losowość jest bardzo przydatna. Często bardzo ułatwia rozumowania, pozwala na piękne i klarowne argumenty używające, na przykład, metody probabilistycznej. Nieraz łatwo znaleźć algorytm używający losowości (randomizowany) i działający szybko, podczas gdy znalezienie szybkiego algorytmu deterministycznego jest trudne lub w ogóle takiego nie znamy. Z losowością jest jednak pewien problem...