Przeskocz do treści

Delta mi!

  1. obrazek

    Algorytmy

    Dawno temu był sobie algorytm

    Autor w sposób popularnonaukowy przybliża kluczowe pojęcia informatyki teoretycznej związane z teorią obliczeń i algorytmiką. Książka jest napisana w formie opowieści; autor ilustruje omawiane pojęcia przykładami zaczerpniętymi z życia codziennego oraz z popularnych książek czy filmów.

  2. Algorytmy

    Jak proste problemy stały się trudne

    Dawno, dawno temu, wierzono, że fundamentalne zasady rządzące światem są proste. Kiedy dziedzina nauki, zwana obecnie informatyką, dopiero raczkowała, naukowcy byli przekonani, że dla każdego problemu obliczeniowego można znaleźć efektywny algorytm, o ile poświęci się na to wystarczająco dużo czasu, kredy oraz kawy. Pojęcie "efektywnego algorytmu" oznaczało początkowo algorytm o czasie działania proporcjonalnym do rozmiaru danych wejściowych, ale i algorytmy o złożoności obliczeniowej  2 𝒪(n ) czy  3 𝒪(n ) były do zaakceptowania.

  3. 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?

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

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