Przeskocz do treści

Delta mi!

Loading
  1. 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.

  2. Gry, zagadki, paradoksy Co to jest?

    Paradoks Russella

    W miejscowości |M jest fryzjer, nazwijmy go superfryzjerem, który strzyże tych i tylko tych mieszkańców miejscowości, którzy nie strzygą siebie samych. Czy superfryzjer strzyże siebie samego? Chwila namysłu pokazuje, że obie możliwości są wykluczone: nie może on strzyc siebie samego, bo strzyże tylko tych, którzy siebie sami nie strzygą; gdyby zaś sam się nie strzygł, to musiałby się strzyc, bo strzyże wszystkich tych, którzy sami się nie strzygą. A zatem, superfryzjer nie może istnieć! Pokażemy jak z powyższego faktu otrzymać różne twierdzenia matematyczne, odpowiednio definiując mieszkańców miejscowości M oraz to, kto kogo strzyże.

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

  4. Internet Migawki informatyczne

    Ciemna strona Internetu

    Internet to bez wątpienia jedno z najważniejszych osiągnięć ludzkości w XX wieku. Jest to ogromna sieć komputerów z całego świata, która umożliwia szybką komunikację. Co więcej, jest tak zaprojektowana, aby uzyskać bardzo dużą niezawodność. To znaczy, jeśli jakiś węzeł w sieci, jakiś kabel łączący pewne węzły, czy nawet spora część wszystkich węzłów i kabli, ulegnie awarii, to i tak reszta sieci będzie potrafiła się komunikować, znajdując ad hoc nowe ścieżki między nieuszkodzonymi węzłami.

  5. Informatyka

    Dlaczego niektóre łamigłówki są tak trudne?

    Inspiracją do napisania tego artykułu jest znana, popularna i - do czego chcę Czytelnika przekonać - całkiem niełatwa łamigłówka zwana Sudoku. Problem polega na uzupełnieniu częściowo wypełnionej planszy 9 × 9 w taki sposób, żeby każdy wiersz i każda kolumna oraz każdy z 9 tzw. regionów |3× 3 zawierał wszystkie cyfry od 1 do 9. Czy nie przypomina to pewnego innego równie znanego problemu natury kombinatorycznej? Tak, to problem Uzupełniania Kwadratów Łacińskich, których wynalazcą był Leonhard Euler. Być może zainspirował innych, by w przyszłości stworzyli Sudoku...

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

  7. obrazek

    Informatyka Co to jest?

    Superkomputery

    Superkomputery pomagają w badaniach przyrody, projektowaniu urządzeń i leków. Czym są, jak działają, jakich używają procesorów, jak szybko liczą? Odpowiedzi na te pytania zilustrujemy przykładami kilku superkomputerów, w tym czterech najszybszych na świecie oraz największego w Polsce.

  8. Informatyka

    Język Scratch

    Programowanie, czyli tworzenie programów i gier, to świetny sposób na rozwijanie kreatywnego, a zarazem logicznego myślenia. Wielu wydaje się ono skomplikowane, ale wcale nie musi być trudne! Jednym z narzędzi, które pozwala w prosty i ciekawy sposób nauczyć się podstaw, jest Scratch - środowisko stworzone przez naukowców z MIT, dzięki któremu bez znajomości specjalistycznego języka każdy może spróbować swoich sił w tworzeniu gier czy animacji.

  9. Informatyka

    Wiszące referencje. Czy można wyeliminować to zagrożenie?

    W tej pracy przedstawimy groźne zjawisko - błąd wiszących referencji - jakie występuje w programowaniu obiektowym, np. w C++, Pascalu, C. W kolejnym artykule omówimy rozwiązanie pozwalające wyeliminować ten błąd. Zacznijmy od krótkiej ekspozycji problemów, jakie napotykamy podczas zarządzania pamięcią obiektów w każdym języku programowania obiektowego.

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

  11. Informatyka

    Twierdzenie o niepustym barze, czyli zmechanizowana naturalna dedukcja

    Sprawdzanie poprawności dowodów matematycznych często wymaga sporej wiedzy i ogromu nużącej pracy. O ile dochodzenie do zrozumienia istoty dowodu, czyli dlaczego dane twierdzenie matematyczne zachodzi, może sprawiać Czytelnikowi dużo satysfakcji, o tyle weryfikowanie wszystkich szczegółów dowodu jest zajęciem dość niewdzięcznym. Z tego powodu od wielu już lat trwają badania nad zaprzęgnięciem komputerów do tej żmudnej części pracy...

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