Przeskocz do treści

Delta mi!

  1. Algorytmy

    Problem komiwojażera w praktyce

    Korzystając z popularnych serwisów internetowych, błyskawicznie znajdziemy najkrótszą trasę między dwoma miastami. A co, gdybyśmy chcieli znaleźć najkrótszą trasę, która pozwoli po wyruszeniu z domu odwiedzić wszystkie interesujące nas miasta i wrócić do punktu wyjścia?

  2. obrazek

    David Hilbert (1862-1943)

    David Hilbert (1862-1943)

    Algorytmy

    O dziesiątym problemie Hilberta

    Podczas odbywającego się w 1900 roku w Paryżu Drugiego Międzynarodowego Kongresu Matematyków jeden z referatów wygłosił wybitny niemiecki matematyk David Hilbert. W swoim wystąpieniu zawarł on listę dwudziestu trzech zagadnień matematycznych stanowiących, jego zdaniem, szczególne wyzwanie dla matematyków w rozpoczynającym się XX wieku. Większość z nich doczekała się rozwiązania. Inne, jak słynna hipoteza Riemanna, pozostają otwarte, inspirując kolejne pokolenia naukowców.

  3. Algorytmy

    Historia pewnego trenera

    Czy pokazując poprawność algorytmu, warto sięgnąć po matematyczne twierdzenia? Jak najbardziej! Przekonamy się o tym, rozważając problem zbalansowanego rozwoju w 2-wymiarowych systemach dodawania wektorów ( Vector Addition Systems - VAS), ubrany w historyjkę o zawodniku i trenerze.

  4. Algorytmy Co to jest?

    Złożoność obliczeniowa

    Jak mierzyć trudność problemów? Trudność albo, inaczej mówiąc, ich skomplikowanie, złożoność. To nie jest łatwe pytanie. Aby móc na nie chociaż nieco sensownie odpowiedzieć, skupimy się tu na tzw. problemach decyzyjnych, czyli takich, na które odpowiedź zawsze brzmi "tak" lub "nie". Żeby określić, jak złożone są te problemy, przyjmuje się zasadę, że problem jest tak trudny, jak jego najlepsze rozwiązanie. Innymi słowy mówimy, że złożoność problemu jest równa złożoności najlepszego algorytmu, który go rozwiązuje.

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

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