Przeskocz do treści

Delta mi!

  1. Informatyka Bestiariusz informatyczny

    Pamięć w komputerze

    Wyobraźmy sobie ucznia, który ma napisać esej na temat gospodarki w południowych rejonach Brazylii. Powiedzmy, że historia ta dzieje się w czasach, gdy dostęp do Internetu nie był tak powszechny jak teraz. Uczeń w celu zgromadzenia potrzebnych materiałów udaje się do biblioteki, z której wypożycza rocznik statystyczny oraz kseruje potrzebne strony z encyklopedii. Następnie wraca do domu i zabiera się do pisania...

  2. Algorytmy Informatyczny kącik olimpijski

    Kolorowanie cyklu

    Zagadnienie kolorowania cyklu niejednokrotnie pojawiało się na konkursach programistycznych, m.in. na Mistrzostwach Europy Środkowej w Programowaniu Zespołowym (zadanie Beijing Guards z roku 2004), czy też Mistrzostwach Polski w Programowaniu Zespołowym (zadanie Słoneczna wyspa z roku 2010).

  3. Algorytmy Informatyczny kącik olimpijski

    Wykładzina

    W zeszłym miesiącu zajmowaliśmy się uogólnieniem następującego zadania: dla danego kwadratu rozmiaru |n n podzielonego na  2 n pól, z których niektóre były zabronione, należało znaleźć prostokąt o największym polu, który nie zawierał żadnego zabronionego pola. W tym numerze rozważymy jeszcze inną wariację tego zadania, a mianowicie będziemy szukać największych prostokątów, które zawierają co najwyżej |K zabronionych pól (nazwiemy je prostokątami prawie pustymi).

  4. obrazek

    Tak wygląda najsilniejszy obecnie superkomputer świata, Tianhe-2 (MilkyWay-2), Chiny:
    33,9 PFLOPS,
    1.024.000 GB RAM
    3.120.000 cores

    Tak wygląda najsilniejszy obecnie superkomputer świata, Tianhe-2 (MilkyWay-2), Chiny:
    33,9 PFLOPS,
    1.024.000 GB RAM
    3.120.000 cores

    Informatyka Bestiariusz informatyczny

    Co siedzi w komputerze?

    Postęp w dziedzinie komputerów dokonuje się niezwykle szybko. Trzydzieści lat temu komputer był w polskich domach nowością, a dziś nie wyobrażamy sobie bez niego życia. Rozwój technologii i oprogramowania powoduje konieczność wymyślania przez producentów coraz to nowych nazw, w których gąszczu użytkownikom komputerów łatwo się zagubić. Często zdarza się też, że pewną nazwę znamy jedynie jako akronim, ale nie bardzo wiemy, co się kryje w jego rozwinięciu. W tej kolumnie spróbujemy przybliżyć Czytelnikom choć część informatycznej terminologii. W pierwszym odcinku powiemy dość ogólnie o tym, co siedzi w naszym komputerze.

  5. Algorytmy Informatyczny kącik olimpijski

    Zliczamy puste prostokąty

    W tym miesiącu zajmiemy się dość klasycznym zadaniem. Dany jest kwadrat rozmiaru |n n podzielony na  2 |n pól, przy czym niektóre pola są zabronione. Dowolny zawarty w tym kwadracie prostokąt, który nie zawiera żadnego pola zabronionego, nazwiemy prostokątem pustym. Należy znaleźć pusty prostokąt o jak największym polu.

  6. Algorytmy

    Zliczamy skojarzenia (II). O planarności i algorytmie FKT

    W pierwszej części tego artykułu pokazaliśmy, że dla szczególnej klasy grafów (kraty i ich podgrafy), istnieje działający w czasie wielomianowym algorytm, który wyznacza liczbę doskonałych skojarzeń dla dowolnego grafu z tej klasy. Ten wynik można uogólnić na szerszą klasę grafów - a konkretnie na grafy planarne, czyli takie, które można narysować na płaszczyźnie tak, by żadne z ich krawędzi się nie przecinały.

  7. Informatyka Informatyczny kącik olimpijski

    Jeszcze dwa zadania do plecaka

    W kąciku kontynuujemy przygodę z zadaniami, do których rozwiązania przydaje się znajomość problemu plecakowego. Tym razem w nieco trudniejszej jego wersji, w której każdy przedmiot ma swój rozmiar m oraz wartość w Standardowe pytanie, które możemy wtedy zadać, to np. jaka jest największa sumaryczna wartość przedmiotów, które możemy zapakować do plecaka, nie przekraczając jego udźwigu M

  8. Informatyka

    Burzliwe początki cyfrowego tysiąclecia

    Rozpoczynając na początku lat 80. XX wieku studia doktoranckie na Uniwersytecie w Erlangen, Karlheinz Brandenburg raczej nie przypuszczał, że wyniki jego pracy przyczynią się do zrewolucjonizowania branży muzycznej na całym świecie. A zaczęło się od tego, że jego promotor, profesor Dieter Seitzer, rozważał zagadnienie przesyłania muzyki liniami telefonicznymi...

  9. Algorytmy Informatyczny kącik olimpijski

    Filary

    W tym kąciku omówimy zadanie Filary, które pojawiło się na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym 2014. Zadanie, pomimo prostej treści i (jak się za chwilę przekonamy) całkiem prostego rozwiązania, sprawiło sporo kłopotów drużynom startującym w zawodach i ostatecznie zostało rozwiązane tylko przez jedną z nich.

  10. obrazek

    Internet

    Turing kontra spamboty

    Czy komputery potrafią myśleć? Ta kwestia nurtuje informatyków od ponad pół wieku. W 1950 roku angielski matematyk Alan Turing zadał podobne, ale bardziej precyzyjne pytanie. A mianowicie, czy komputer (lub program komputerowy) jest w stanie przekonać człowieka, że sam również jest istotą ludzką. Turing zaproponował wtedy następujący test (który dziś, na jego cześć, zwany jest testem Turinga). Jeśli człowiek-sędzia podczas rozmowy prowadzonej w języku naturalnym (ale za pośrednictwem pisma) równocześnie z człowiekiem oraz z programem komputerowym nie będzie w stanie stwierdzić, który z interlokutorów jest który – to taki program zalicza test Turinga.

  11. Algorytmy

    Skojarzenia...

    Ten numer Delty jest zdominowany przez tematykę skojarzeń w grafach. Dla przypomnienia: graf nieskierowany to zbiór wierzchołków połączonych krawędziami, skojarzenie zaś w tym grafie to taki podzbiór krawędzi math  że każdy wierzchołek grafu jest incydentny z co najwyżej jedną krawędzią z  math

  12. Informatyka

    Informatyk gra na giełdzie

    Nasz znajomy informatyk zdecydował się zainwestować część swoich oszczędności na giełdzie papierów wartościowych. Jak na informatyka przystało, do grania na giełdzie postanowił zaprząc komputer. W tym celu, korzystając z najnowszych trendów sztucznej inteligencji, napisał program, który na podstawie przeszłych notowań giełdowych przewiduje, jak kurs akcji będzie się zmieniał w przyszłości, i podejmuje decyzje o kupnie bądź sprzedaży. Nasz znajomy przetestował program, uruchamiając go na dużym zbiorze archiwalnych notowań. Zastanawia się teraz, jak dobrze jego program sobie poradził – stanął zatem przed problemem wyznaczenia najlepszej możliwej gry na giełdzie, jeśli znamy wszystkie notowania.

  13. Informatyka

    Krzaczki na ekranie

    ASCII. Podstawowym sposobem reprezentacji znaków we współczesnych komputerach jest przyjęty w 1967 r. ASCII (czyt. aski, ang. American Standard Code for Information Interchange). Definiuje on 128 znaków, wśród których znajdują się 33 niedrukowalne znaki sterujące, znak odstępu, 52 litery (wielkie i małe litery alfabetu angielskiego), 10 cyfr i 32 znaki interpunkcyjne. ASCII przyporządkowuje każdemu znakowi liczbę z zakresu 0–127 (lub równoważnie szesnastkowo 0–7F).

  14. Algorytmy

    Zawieramy wielokąty

    Na artykule Problemy 3sum-trudne w geometrii autor podał trzy wersje problemu PolygonContainment, które są uważane za trudne – nie umiemy ich rozwiązać w czasie (istotnie) lepszym niż kwadratowy. Uważni Czytelnicy na pewno zauważyli, że nie jest tam wspomniane o wersji, w której wielokąty są wypukłe i dopuszczamy dowolne przesunięcia (ale nie obroty). Ten brak jest w pełni uzasadniony, gdyż tę wersję problemu można rozwiązać w czasie liniowym względem liczby wierzchołków wielokątów, co pokażemy poniżej.

  15. Algorytmy Informatyczny kącik olimpijski

    Czworokąty wypukłe

    W tym kąciku zajmiemy się zadaniem Quadrilaterals z obozu w Petrozawodsku w 2006 roku. Na płaszczyźnie dane jest math punktów w położeniu ogólnym (tzn. żadna trójka punktów nie leży na jednej prostej). Należy wyznaczyć liczbę czworokątów wypukłych, których wierzchołki znajdują się wśród podanych punktów.

  16. Algorytmy

    Kliki

    Dany jest graf nieskierowany math Kliką nazwiemy taki podzbiór wierzchołków math że każde dwa wierzchołki w zbiorze math są połączone krawędzią w grafie math  Problem znalezienia w grafie kliki o jak największej liczbie wierzchołków jest NP-zupełny, a jak wiadomo, dla takich problemów nikt jeszcze nie pokazał algorytmu wielomianowego. Podobne trudności są z algorytmem dla problemu zliczania klik w grafie, choć tutaj stosowną klasę złożoności stanowią tzw. problemy #P-zupełne.

  17. Algorytmy Informatyczny kącik olimpijski

    Odśnieżanie

    Zadanie Odśnieżanie z zeszłorocznego Obozu Naukowo-Treningowego im. A. Kreczmara można sformułować w języku teorii grafów następująco. W nieskierowanym, ważonym, spójnym grafie math  wyróżniono cztery wierzchołki. Należy usunąć część krawędzi z grafu tak, żeby nadal istniały ścieżki pomiędzy każ parą wyróżnionych wierzchołków i żeby suma wag krawędzi, które pozostały w grafie, była jak najmniejsza.

  18. Gry, zagadki, paradoksy Mała Delta

    Numizmatyka dla zachłannych

    Wyobraźmy sobie następującą grę. Na stole w jednym rzędzie leży math monet o różnych nominałach. Dwoje graczy – Ania i Bartek – wykonuje na przemian ruchy, zaczyna Ania. Ruch polega na zabraniu jednej monety z lewego lub prawego końca rzędu. Wynikiem gry jest, oczywiście, suma nominałów monet zgromadzonych przez każdego z graczy. Jak powinna grać Ania, by uzyskać jak największą sumę, jeśli wie ona, że Bartek będzie grał optymalnie (tzn. będzie starał się zmaksymalizować swoją sumę)?