Delta mi!

Niemal każdy wykład wprowadzający w zagadnienie sztucznych sieci neuronowych zaczyna się anegdotą o zaczerpnięciu tego pojęcia z anatomii mózgu...

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 czy były do zaakceptowania.

Tym razem omówimy zadanie z XII OIG.

Problem szyfrowania przesyłanych wiadomości sięga jeszcze czasów starożytnych, więc naszego nowego deltowego cyklu artykułów o kryptologii prezentowanego w rubryce "A jednak się da!" nie możemy nie zacząć od przypomnienia najstarszego znanego systemu szyfrowania, mianowicie szyfru Cezara. Szyfr ten nie jest specjalnie wyrafinowany...

Tym razem wyjątkowo nie omówimy żadnego nowego zadania. Wrócimy za to do problemu przedstawionego w w artykule Złośliwy problem i kubełkowe struktury danych...

W piątym odcinku bestiariusza przybliżymy kilka bardziej technicznych akronimów związanych ze sprzętem komputerowym (ang. hardware). Wspominaliśmy już o ENIAC-u, jednym z pierwszych komputerów, którego nazwa też była akronimem. Przykłady innych komputerów z tamtych czasów to EDVAC (Electronic Discrete Variable Automatic Computer), PDP (Programmed Data Processor) i pierwszy komputer wykorzystany w biznesie LEO (Lyons Electronic Office).

Dziś modeluje się prawie wszystko. Przykładowo prognozę pogody tworzy się na podstawie modelu atmosfery. Przestrzeń nad ziemią dzieli się na prostopadłościany szerokości kilku kilometrów, wysokości kilkudziesięciu, może kilkuset metrów; w każdym z nich ustala się, jaka jest temperatura, wilgotność, ciśnienie, prędkość wiatru, jego kierunek i jeszcze wiele innych parametrów. Taki opis sytuacji to stan modelu. Ponadto opierając się na prawach fizyki, ustala się, jak ten stan będzie ewoluował w czasie. To, oczywiście, będzie przybliżenie sytuacji rzeczywistej. Na przykład, liczymy, w jakim stanie model będzie za 12 godzin, dobę, dwie. Często takie obliczenia wymagają wielkiej mocy obliczeniowej, szczególnie jeśli chcemy zrobić to dokładnie, jak np. w przypadku prognozy ICM (meteo.pl).

W 1970 roku jeden z pionierów sztucznej inteligencji, Marvin Minsky, napisał na łamach Life Magazine, że w ciągu 8 lat pojawią się maszyny o inteligencji porównywalnej z ludzką lub ją przewyższające. Jednak takie maszyny nie pojawiły się ani do roku 1978, ani przez kolejne 40 lat. A jednak w ciągu ostatnich lat można zobaczyć znaczne przyspieszenie w dziedzinie sztucznej inteligencji: autonomiczne samochody, programy wygrywające z ludzkimi arcymistrzami w Go - ostatnią grę, w którą człowiek dotychczas był lepszy, czy roboty humanoidalne śmiało przemierzające gruzowiska. Być może prognoza Minskiego, choć znacznie opóźniona, ziści się na naszych oczach?

Tym razem omówimy dwa zadania z zawodów drużynowych X Olimpiady Informatycznej Gimnazjalistów.

W dniach 10-13 kwietnia 2018 r. w Warszawie odbyły się zawody finałowe jubileuszowej, XXV Olimpiady Informatycznej. Zostało do nich zakwalifikowanych 97 zawodników. W ciągu dwóch dni zawodów zawodnicy mieli do rozwiązania w sumie sześć zadań programistycznych ocenianych od 0 do 100 punktów.

Tym razem omówimy zadanie Bajtockie kółeczko z pierwszego etapu zawodów drużynowych X Olimpiady Informatycznej Gimnazjalistów.

Zawodowo zajmuję się kryptologią, czyli dziedziną nauki badającą różne aspekty bezpieczeństwa cyfrowego świata. Jest to nauka ścisła, czyli taka, w której królują stricte matematyczne rozumowania. Solą matematyki są, oczywiście, dowody. Również główne wyniki kryptologiczne to właśnie twierdzenia i ich dowody. A twierdzenie to para: założenie i teza. W kryptologii teza zwykle jest podobna: proponowany system jest bezpieczny. Ciekawym i ważnym pytaniem jest jednak wątpliwość: ale przy jakich założeniach?!

Tym razem omówimy dwa zadania z IX International Autumn Tournament in Informatics, który odbył się w listopadzie 2017 roku w Szumem w Bułgarii.

Dawno, dawno temu żył sobie w Polsce smok. Chciałbym dopisać - pod Wawelem - jak donosił Jan Długosz, ale my wiemy od kilku lat, że smokiem wawelskim zostały nazwane drapieżne dinozaury żyjące około 200 milionów lat temu. W tych czasach żyły też małe prassaki, więc nawiązując do legendy, można z pewnością powiedzieć, że smoki wawelskie czasem połykały (pra)barana, a właściwie wspólnego przodka króla Kraka i owcy, którą szewczyk nafaszerował siarką. Z upływem czasu smok wawelski zmieniał się, a za te zmiany były odpowiedzialne niewidzialne cegiełki nazywane genami, które przekazywał swoim potomkom...

W latach czterdziestych ubiegłego wieku rząd w Londynie doszedł do wniosku, że do zaspokojenia potrzeb obliczeniowych całego Zjednoczonego Królestwa wystarczą jedynie dwa lub trzy komputery. Nieco ponad trzy dekady później, po niespełna pięciu latach oficjalnej działalności, firma z jabłuszkiem w logo zanotowała sprzedaż dwustutysięcznego komputera osobistego, co stanowiło jedynie kilkanaście procent ówczesnego rynku. Innymi słowy, postęp technologiczny sprawił, że w relatywnie krótkim czasie komputery zajmujące całe hale i ważące kilkadziesiąt ton uległy miniaturyzacji do skali pudełka na buty, przy jednoczesnym spadku ich ceny o kilka rzędów wielkości i wzroście mocy obliczeniowej. Tym samym urządzenia obliczeniowe zaczęły szturmem wdzierać się w różne aspekty naszego życia.

Tym razem omówimy dwa zadania, które na pierwszy rzut oka wyglądają podobnie, jednak w istocie są różne. Pierwsze z nich pochodzi z II etapu IX Olimpiady Informatycznej Gimnazjalistów, zaś drugie z Bałkańskiej Olimpiady Informatycznej Juniorów w 2015 roku.

• Raj na Ziemi jednak istnieje. Znalazła go sztuczna inteligencja.
• Sztuczna inteligencja pomoże w walce z bioterroryzmem. Nauczyła się rozpoznawać bakterie wąglika.
• Potężna kasta zawodowa może zniknąć bez śladu. Sztuczna inteligencja bez trudu pokonała setkę ekspertów.
• Zaleje nas spam. Sztuczna inteligencja złamała system weryfikacji CAPTCHA.

Takie i podobne tytuły pojawiają się codziennie, zarówno w czasopismach, na stronach internetowych, jak i usłyszeć można je w telewizji czy w radiu. A to nie wszystko...

W czwartym odcinku przyjrzymy się kilku akronimom o specyficznej budowie lub historii...

Tym razem omówimy zadanie z pierwszego dnia Pierwszej Olimpiady Informatycznej Juniorów (EJOI), która odbyła się w Sofii we wrześniu 2017 roku.

Za siedmioma górami, za siedmioma rzekami - gdzieś pod Warszawą - znajduje się niewielka miejscowość. W tej miejscowości stoi mały domek. A tak się składa, że w domku tym mieszkają Bartek i Agatka wraz z rodzicami.

3 stycznia 1994 roku rozpoczęły się zawody I stopnia I Olimpiady Informatycznej, w których wystartowało 528 uczniów z całej Polski. Uczniowie mieli trzy tygodnie na rozwiązanie trzech zadań. 64 uczniów z najlepszymi rozwiązaniami awansowało do zawodów II stopnia, które odbyły się 18-20 marca 1994 roku w Ośrodku Edukacji Informatycznej i Zastosowań Komputerów w Warszawie. Finały I Olimpiady Informatycznej miały miejsce w dniach 18-22 kwietnia 1994 roku, także w gościnnych murach Ośrodka Edukacji Informatycznej i Zastosowań Komputerów. W gronie finalistów znalazło się 33 uczniów. Pierwszym zwycięzcą Olimpiady Informatycznej został Michał Wala z I LO im. J. Kasprowicza z Raciborza.

W ciągu ostatnich kilku lat świat naukowo-techniczny nauczył się uczyć tzw. głębokie sieci neuronowe rozpoznawania treści obrazów. Rezultaty są spektakularne: dobrze nauczony model potrafi znaleźć na obrazku wszystkie zwierzęta i rozróżnić ich gatunki, przerobić zwykłe zdjęcie tak, żeby wyglądało na namalowane przez Picassa, czy domalować brakujący kawałek przedmiotu, którego nigdy wcześniej "nie widział". A wszystko opiera się na prostym przepisie: weź model matematyczny (nieskomplikowany pojęciowo, ale o wielkiej liczbie parametrów), dodaj jak najwięcej mocy obliczeniowej (w praktyce kart graficznych), poczekaj.

Dzisiejsze zadanie pochodzi z VIII. Olimpiady Informatycznej Gimnazjalistów w roku szkolnym 2013/2014.

Naturalnie, wszystko się zaczyna od tabula rasa. Toteż załóżmy, że dysponujemy wielką niezapisaną tablicą. Po tej tablicy pisać będzie mógł absolutnie każdy, kto tylko chce. Pisać wolno wszystko, należy się jedynie podpisywać. Komunikaty nigdy nie znikają, a budowa tablicy jest taka, że łatwo się zorientować, w jakiej kolejności pojawiały się obecne na niej napisy...

W tym artykule zmierzymy się z problemem pokrycia wierzchołkowego (Vertex Cover). Poruszymy kilka kwestii na pograniczu optymalizacji liniowej, złożoności obliczeniowej oraz algorytmów parametryzowanych...