Przeskocz do treści

Delta mi!

  1. Algorytmy

    Zliczamy podciągi

    Zaczniemy od takiego zadania: dla danego |n -literowego słowa s chcemy znaleźć liczbę jego różnych podciągów. Innymi słowy, chcemy odpowiedzieć na pytanie, ile różnych słów możemy uzyskać poprzez wykreślanie niektórych liter ze słowa s: Dla przykładu rozważmy słowo ABAA. Ma ono dokładnie 10 różnych podciągów: słowo puste, A, B, AA, AB, BA, AAA, ABA, BAA oraz ABAA. Dla uproszczenia będziemy rozważać słowa złożone z liter A i B, ale nasze rozwiązania będą działać dla dowolnego A -literowego alfabetu. |ABA;BAA

  2. Algorytmy Informatyczny kącik olimpijski

    Po prostu znajdź wzór

    Wiele zadań konkursowych proponowanych podczas zawodów programistycznych wymaga od uczestników zakodowania zawiłych algorytmów czy skomplikowanych struktur danych. Właśnie takie zadania nie raz i nie dwa, ale wielokrotnie prezentujemy w niniejszej rubryce. Dziś jednak opowiemy o pewnym bardzo specyficznym typie zadań olimpijskich, które zwykle sprowadzają się do znalezienia zwartego wzoru opisującego odpowiedź na pytanie zawarte w zadaniu...

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

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

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

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