Przeskocz do treści

Delta mi!

  1. Algorytmy Informatyczny kącik olimpijski

    Drogi

    W tej edycji kącika znowu cofniemy się w czasie do 2005 roku, do pierwszej edycji konkursu Potyczki Algorytmiczne, i omówimy zadanie z finału próbnego tego konkursu pt. Drogi (bardzo podobne zadanie pojawiło się zresztą w jeszcze bardziej zamierzchłej przeszłości, na Międzynarodowej Olimpiadzie Informatycznej w 1996 roku).

  2. Algorytmy

    Ucieczka

    Wyobraź sobie, Drogi Czytelniku, że jesteś kapitanem okrętu wojennego i w trakcie jednej z misji znalazłeś się na środku morza leżącego na terytorium wroga. Wiesz, że wróg rozmieścił w tej strefie pewną (skończoną) liczbę radarów. Każdy radar ma określony zasięg, być może różny w przypadku różnych radarów, i jest w stanie wykryć każdy podejrzany obiekt, który znajdzie się w jego zasięgu. Naszym siłom wywiadowczym udało się wykraść plan rozmieszczenia radarów. Na jego podstawie chcesz stwierdzić, czy możesz wydostać się z wrogich wód niezauważony przez radary.

  3. Algorytmy

    Test na liczbę pierwszą

    Chyba wszyscy lubimy liczby pierwsze. Szczególne wrażenie robią te naprawdę duże, wydają się skrywać w sobie jakąś nadzwyczajną tajemnicę: dlaczego akurat one stały się swego rodzaju wybrańcami spośród innych liczb i mają tak niezwykłe właściwości?

  4. Algorytmy

    Kocha, lubi, szyfruje...

    W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są Alicja i Bob, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.

  5. Algorytmy

    Jaskinia

    W tym kąciku omówimy zadanie Jaskinia, które pojawiło się w zeszłym roku na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

  6. Algorytmy

    Jak szybko działa sito?

    Jedną z najlepiej znanych metod wyznaczania liczb pierwszych jest sito Eratostenesa. Opiera się ona na spostrzeżeniu, w zasadzie oczywistym, że jak wyrzucimy wszystkie liczby złożone, to zostaną same liczby pierwsze...

  7. Algorytmy

    Jak złapać terrorystę?

    Któż z nas nie bawił się jako dziecko w chowanego? Zabawa ta sprawia dzieciom wiele radości, mimo że z algorytmicznego punktu widzenia jest bardzo prosta. Jeżeli bowiem wszyscy ukrywający się czekają uczciwie w swoich kryjówkach, to zawsze uda się ich znaleźć – wystarczy, jeżeli szukający przejrzy wszystkie miejsca.

  8. Algorytmy

    Odtwarzanie grafu

    W grafie nieskierowanym możemy obliczyć stopień każdego wierzchołka, czyli liczbę krawędzi incydentnych z tym wierzchołkiem. Przykładowo, dla grafu-koperty otrzymujemy w ten sposób ciąg stopni 4, 4, 3, 3, 2. Wykonanie takiego przekształcenia dla danego grafu jest naprawdę proste. Możemy jednak postawić pytanie odwrotne: czy mając dany ciąg liczb, możemy stwierdzić, czy odpowiada on stopniom wierzchołków jakiegoś grafu nieskierowanego, a jeśli tak, zrekonstruować ten graf?

  9. Algorytmy

    Kolejność ma znaczenie

    Z artykułu Wojciecha Śmietanki wypływa ważny morał: przystosowanie algorytmu do działania na maszynie równoległej wymaga często zupełnie innego spojrzenia na dany problem. Okazuje się jednak, że nawet w przypadku architektury jednoprocesorowej optymalizacja algorytmu może wymagać od nas całkiem pomysłowych przeróbek. W tym artykule podamy dwa przykłady, w których kluczową okaże się kolejność, w jakiej wykonujemy operacje.

  10. Algorytmy Informatyczny kącik olimpijski

    Ploter

    Napisanie programu, który generuje rysunek fraktala, idealnie nadaje się na zadanie dla początkującego programisty. Proste reguły prowadzące do powstania skomplikowanych wzorów powodują, że przy stosunkowo niewielkim wysiłku programistycznym można osiągnąć całkiem ambitne efekty wizualne. Ponadto samopodobieństwo fraktali pozwala ćwiczyć jedną z podstawowych koncepcji programistycznych – rekurencję.

  11. Algorytmy

    Jak wyznaczać wyrazy ciągu EKG?

    Po przeczytaniu artykułu Marcina Pilipczuka trudno nie odnieść wrażenia, że nasz zasób wiedzy o zachowaniu ciągu EKG opiera się przede wszystkim na wynikach eksperymentów komputerowych, natomiast dowody otrzymanych w ten sposób hipotez pojawiają się z pewnym opóźnieniem.

  12. Algorytmy

    Pokrycie wierzchołkowe kontratakuje

    W  Delcie 7/2009 Marek Cygan opisał pewien sposób radzenia sobie z tym, że dla niektórych trudnych problemów nie potrafimy znaleźć szybkiego algorytmu. Autor rozważał klasę problemów NP-trudnych – czyli takich, których prawdopodobnie nie można rozwiązać w czasie wielomianowym – i pokazywał, że dla wielu z nich można w efektywny sposób skonstruować nie dokładne, lecz przybliżone rozwiązanie.