Archiwa kategorii: Ciekawostki

Jednorazowe (nie tworzące żadnych serii) na ciekawy lub zabawny temat okołoinformatyczny

Mordercze mikrofalówki, czyli kilka słów o fake science

Fake news, czyli fałszywe wiadomości, to ostatnio gorący temat. Oskarżeniami o ich produkowanie przerzucają się wszystkie frakcje. Rodzinne obiady stały się jeszcze trudniejsze do przetrwania, od kiedy każdy ich uczestnik czerpie informacje o świecie z wybranego przez siebie medium, które filtruje wszelkie doniesienia przez odpowiedni światopogląd. Albo po prostu je wymyśla.

W tym wpisie chcę skoncentrować się na pewnym specyficznym wariancie tego problemu, czyli fake science – fałszywych doniesieniach ze świata nauki.

 

Zacznę od historyjki z życia.

Na początku chciałam nazwać ją „anegdotą”, ale doszłam do wniosku, że temat jest jednak zbyt ponury.

W pewnym momencie, parę lat temu, mąż mojej koleżanki zaczął się gorzej czuć. Doskwierał mu pakiet mało specyficznych dolegliwości – był osłabiony, zmęczony, źle spał, miał szarą cerę. Rozpoczął tułaczkę po gabinetach lekarskich, a w międzyczasie “dokształcał się” na własną rękę, rzecz jasna głównie w Internecie.Przez chwilę na horyzoncie pojawiła się najstraszniejsza z diagnoz, co tylko dodało mu zawziętości. Zanim poznał definitywną odpowiedź – mononukleoza, dość popularny wirus z jakiegoś powodu rzadko diagnozowany w Europie (za to często obecny w amerykańskich serialach, gdzie Hanna Horvath wykręca się od pójścia na imprezę z powodu “mono”) – zdążył przewartościować swoje podejście do życia i zdrowia. Kupuje tylko organiczną żywność. Wytoczył wojnę Big Pharmie. Zabronił rodzinie korzystać z mikrofalówki.

Sądzę, że prawie każdy, kto ma pracę, dzieci i mikrofalówkę (albo przynajmniej jedną z tych rzeczy) zgodzi się, że możliwość szybkiego odgrzania posiłku za pomocą mikrofal jest nieocenioną pomocą. Koleżanka, mając dość kłótni, ostatecznie ustąpiła i pozwoliła wyrzucić maszynę, choć podśmiewa się z poglądów i obsesji męża.

– Poza tym – powiedziała mi – w Internecie są strony, według których mikrofalówki zmieniają strukturę jedzenia w sposób prowadzący do raka. Są także takie, które mówią, że żadnego ryzyka nie ma. Skąd mogę wiedzieć, kto pisze prawdę?

Ta rozmowa dała mi do myślenia. Chodzi o inteligentną i oczytaną osobę. Jeśli ona nie potrafi poradzić sobie z rozpoznaniem, która informacja jest poparta faktami, a która to wymysł i manipulacja, jak ma poradzić sobie ogół społeczeństwa?

 

https://commons.wikimedia.org/wiki/File:MW_on_fire.jpg

Przygotowałam więc krótkie studium przypadku. Jak to jest z tymi mikrofalówkami?

Oto garść materiałów głoszących szkodliwość (zabójczość) spożywania pokarmów podgrzanych w mikrofali:

Jakie są ich istotne cechy wspólne?

  • Brak źródeł (odwołań do literatury lub linków do wiarygodnych badań lub raportów) bądź źródła kuriozalne (inne dzieła tego samego autora, linki do stron z teoriami spiskowymi, linki do artykułów na inny temat lub z odmienną tezą).
  • Sensacyjny, straszący ton.
  • „Wiedza powszechna” i brak konkretów, czyli sformułowania takie jak „opinia pewnego fizyka”, jak powszechnie wiadomo”, „czytałem gdzieś”
  • Opisy absurdalnych „eksperymentów” przeprowadzonych niezgodnie ze sztuką, których wyników nigdy nie opublikowano i nie zweryfikowano. Przykład: podlewanie dwóch (!) roślinek wodą z mikrofalówki i zwykłą wodą przez jedną osobę.
  • W załączonych przeze mnie przykładach autorzy posługują się poprawną polszczyzną, ale w ogólności warto zwracać uwagę także na poziom językowy.
  • Artykuły pochodzą z prywatnych blogów lub stron „lifestyle’owych”.
  • Linki do innych artykułów z dziedziny „alternatywnej medycyny” czy „alternatywnej nauki”.

Tu artykuły zapewniające, że jedzenie z mikrofalówki jest bezpieczne: 

Warte odnotowania cechy wspólne?

  • Linki do źródeł, w tym do prac naukowych opublikowanych w renomowanych czasopisach oraz oficjalnych raportów agencji naukowych.
  • Rzeczowy ton, odwołujący się do zasad działania urządzenia.
  • Niektóre z treści zamieszczono w domenach renomowanych instytucji, jak Centrum Nauki Kopernik.
  • Niestety, więcej takich materiałów można znaleźć w języku angielskim. Wygląda na to, że wyszukiwarka Google lepiej sobie radzi z rozpoznawaniem nierzetelnych stron w języku angielskim – tam sensacje z gatunku fake science są pozycjonowane niżej.

Kilka źródeł naukowych:

Cechy wspólne?

  • Materiały zostały odnalezione w dedykowanych wyszukiwarkach Google Scholar lub w bazach artykułów naukowych (PubMed)
  • Niestety, w przypadku wielu artykułów naukowych, w Internecie znaleźć można jedynie ich abstrakty i streszczenia. O dostęp do pełnej wersji można poprosić autorów, można go wykupić (często za kwoty szokujące w przeliczeniu na złotówki), albo udać się do biblioteki uniwersyteckiej.
  • Materiały są w języku angielskim. To jest dzisiaj język poważnej nauki i trzeba się z tym pogodzić.
  • Artykuły są pisane formalnym językiem, ich treść jest poparta danymi eksperymentalnymi i dalszymi odwołaniami do zweryfikowanych źródeł.
  • Warto odnotować, że nie istnieje zbyt wiele badań na temat szkodliwości mikrofalówki, bo w zasadzie nie bardzo jest tu co badać, podobnie jak nikt nie zajmuje się dowodzeniem, że na Księżycu nie mieszkają krasnoludki. Istnieją badania (w tym jedno z podlinkowanych wyżej), które opisują wpływ podgrzewania w mikrofali na wartości odżywcze i porównują go z wpływem innych rodzajów obróbki termicznej.
https://www.flickr.com/photos/29233640@N07/5170544729

Podsumowując, jakie cechy powinien posiadać tekst głoszący szokującą lub przełomową tezę, żeby można było potraktować go poważnie?

  1. Tekst jest najbardziej wiarygodny, jeśli zawiera odwołania do źródeł. “Źródła” nie oznaczają linków do innych artykułów w pokrewnych portalach głoszących przeróżne teorie spiskowe. Źródła to artykuły naukowe opublikowane w uznanych czasopismach, które każdy otrzymany tekst przepuszczają przez kilkuetapowy proces zanonimizowanej recenzji, tzw. peer review. Każdy artykuł jest czytany przez naukowców z tej samej dziedziny, którzy zwracają uwagę na logikę wywodu, odtwarzalność wyników, poprawność analizy statystycznej. Czasami odsyłają tekst do poprawki, często – odrzucają. Na podstawie faktów, nie własnego widzimisię. Inny akceptowalny typ źródeł to materiały informacyjne uznanych, najczęściej państwowych ośrodków badawczych.
  2. Inny typ wartościowego źródła to tekst z oficjalnym stanowiskiem rządowej agencji badawczej.
  3. Podlinkowane źródła potwierdzają tezę z artykułu! Bo wyobraźcie sobie, że nie zawsze tak jest.
  4. Najlepiej, jeśli źródła są w języku angielskim. Ktoś, kto dokonuje przełomowego odkrycia i jest pewien poprawności swoich wyników, nie ograniczy się do publikacji w lokalnej prasie, tylko postara się pokazać swoje badania na forum światowym.
  5. Z reguły im nowszy tekst źródłowy, tym lepiej. Rzadko, ale jednak zdarza się, że renomowane czasopismo naukowe opublikuje tekst, który przeszedł proces peer review, a dopiero na późniejszym etapie zawarte w nim tezy zostały obalone – najczęściej, kiedy kilka innych zespołów naukowców nie jest w stanie odtworzyć wyników opisanych w „przełomowym” artykule. Jednym z niechlubnych i bardzo szkodliwych przykładów jest artykuł Andrew Wakefielda (i kolegów) opisujący związek pomiędzy szczepionką MMR a autyzmem. Artykuł został opublikowany w czasopiśmie Lancet (a później oficjalnie wycofany) i mimo że jego tezy zostały jednoznacznie obalone a autorowi udowodniono fałszowanie wyników, środowiska antyszczepionkowe nadal powołują się na ten tekst. Tu można znaleźć szczegółowy opis tej historii (po angielsku).
  6. Tekst jest napisany poprawnie, bez błędów ortograficznych. Serio! Ktoś, kto dużo czyta (a skoro wypowiada się na tematy naukowe, to powinien dużo i ze zrozumieniem czytać), nie robi głupich błędów ortograficznych. Oczywiście, istnieje dysortografia i parę pokrewnych schorzeń. Na prywatnym blogu dużo publikującej blogerki popkulturalnej błędy są do zaakceptowania. W okołonaukowym tekście – nie. Od tego jest korekta. Jeśli nie ma korekty ortograficznej, tym bardziej nie ma co się łudzić, że ktoś weryfikuje prawdziwość treści!
  7. Nie zawiera błędów logicznych, takich jak dowody anegdotyczne (przydarzyło się mojej cioci – nawet jeśli naprawdę się przydarzyło), mylenie współwystępowania i przyczynowości (dziecko zostało zaszczepione, a dwa miesiące później zmarło – na pewno przez szczepionkę), efekt potwierdzenia (mentalnie odnotowuję tylko te przypadki, które potwierdzają moją tezę – robią to nawet lekarze, jak ten, który twierdzi, że tabletki hormonalne powodują niepłodność, bo przychodzą do niego kobiety, które brały tabletki i nie mogą zajść w ciążę… Ale kobiety, które mogą zajść w ciążę, po prostu do niego nie przychodzą) i wiele, wiele innych.
  8. Omawiane eksperymenty przeprowadzono zgodne z metodą naukową. Najłatwiej potwierdzić to przez publikację w wiarygodnym źródle (punkt 1). Jeśli wyniki dopiero czekają na publikację, co jest istotne? Odpowiednio duża, statystycznie istotna próba, niezaburzona i reprezentatywna (np. badań na temat stosunkowej liczby homoseksualistów w społeczeństwie nie przeprowadzamy w klubach dla gejów – a opinii Szwedów na temat poczynań polskiego rządu nie opieramy na ankiecie w skrajnie prawicowym szwedzkim portalu). Próba jest ślepa (ani pacjent, ani lekarz nie wiedzą, czy badana osoba dostała placebo, czy nie, bo może to wpłynąć na ich zachowanie, interpretację wyników oraz proces zdrowienia).
  9. Autor ostrożnie posługuje się sformułowaniami takimi jak: “oczywiście”, “jak powszechnie wiadomo”, “normalny”. (Prawie) nic nie jest oczywiste, wszystko powinno być poparte badaniami i statystykami.
  10. Nie linkuje do stron o reptilianach, porno i reklam środków na powiększenie penisa.

Czy mikrofalówki zabijają?

Tak. Jeśli komuś uda się włożyć głowę do działającej kuchenki. Ewentualnie jeśli podgrzeje jedzenie w azbestowym pojemniku.

 

A może pominęłam jakieś inne istotne wyznaczniki wiarygodności?

Obrazek w nagłówku pochodzi ze strony SketchPort i jest dostępny na licencji CC-BY.

Ku przestrodze: przygody nadgarstkowe

Przyznaję: w pracy wyśmiewałam się z ludzi, którzy przyczepiali do myszki i klawiatury żelowe podkładki korygujące ustawienie nadgarstka. Mówiłam (i w głębi duszy nadal to podtrzymuję), że wyglądają jak silikonowe wkładki do sztucznych piersi. Nie mam nic do sztucznych piersi, ale same implanty nie wyglądają apetycznie, prawda? Względy estetycznie przez lata skutecznie zniechęcały mnie do przetestowania tego rozwiązania. Kiedy pewnego razu próbowałam zaprezentować coś na komputerze wyposażonym w taki sprzęt, oczom mym ukazał się sposób mocowania: biała gumka. Taka do majtek. Zraziłam się wówczas ostatecznie.

Standardowa żelowa podkładka pod nadgarstek
Standardowa żelowa podkładka pod nadgarstek

Aż wreszcie nadszedł czarny tydzień, w którym klient tuż przed wdrożeniem zrzucił na mój zespół 500 nowych „przypadków testowych”. Przypadki testowe w niektórych gałęziach NLP mają to do siebie, że bardziej niż cokolwiek innego przypominają nowe wymagania funkcjonalne. Zaczęło nam się palić pod pupami.

Po tygodniu maniakalnej pracy zaczął mnie boleć prawy nadgarstek. Mocno. Tak mocno, że nie byłam w stanie, między innymi: używać myszki, zapiąć guzika, umyć zębów. Zdiagnozowałam sobie RSI (Repetitive Strain Injury), a u ortopedy okazało się, że to klasyczny u programistów i pracowników linii produkcyjnych zespół cieśni nadgarstka. Zwał jak zwał, dostałam prawie dwa tygodnie zwolnienia – programista bez sprawnej ręki okazuje się kompletnie bezużyteczny (przynajmniej do czasu, gdy nauczy się programować stopami).

Zanim wróciłam, zdążyłam zainwestować w urządzenia odciążające nadgarstek, które niniejszym polecam każdemu. Po pierwsze, pionowa myszka. Korzystam z myszki Evoluent (zdjęcie poniżej lub w nagłówku bloga). Wygląda nietypowo, ale działa jak każda inna myszka. Wszystkie przyciski są w tym samym miejscu, jedyna różnica to obrót dłoni z nienaturalnej pozycji „płaskiej” do odprężonej „powitalnej”. Potem przyjrzałam się klawiaturom i przyznam, że tu mam problem. Ergonomiczna klawiatura powinna mieć oddzielną część numeryczną, żeby nie zmuszać użytkownika myszki do nienaturalnego wyciągnięcia w prawo całego ramienia (przy okazji zrozumiałam, dlaczego przy bieganiu boli mnie prawy bark). Jednak wszystkie klawiatury bez części numerycznej miały ekstrawaganckie rozwiązania w obszarze klawiszy delete/home…, a ja korzystam z nich bardzo często i nie chcę tam udziwnień. Dlatego skończyło się na wygiętej klawiaturze Microsoftu.

Myszka pionowa
Myszka pionowa oraz kubek kawy (z Bobkiem)

Znam osoby, które – doświadczone tym cholerstwem – przebudowały większość codziennych czynności pod kątem ochrony nadgarstka. W ekstremalnym przypadku oznaczało to na przykład wymianę samochodu na taki z automatyczną skrzynią biegów.

Zespół cieśni nadgarstka wrócił do mnie potem jeszcze raz, kiedy okazało się, że kolejną grupę ryzyka stanowią kobiety w ciąży. Ale wiedziałam już, czego unikać i obyło się bez większego bólu.

Kiedy wróciłam do pracy po swojej nadgarstkowej przygodzie, okazało się, że w międzyczasie w moim zespole zapanowała epidemia cieśni. Skończyło się to tak, że dostałam polecenie zorganizowania prezentacji na temat ergonomii pracy 🙂 Pojawił się w niej następny istotny element, o którym być może nie trzeba przypominać programistom, ale który nie jest oczywisty dla wszystkich osób w biurze: pisanie bezwzrokowe. W skrócie: nieprawidłowe korzystanie z klawiatury (pisanie jednym palcem albo autorskie kombinacje palców) jest kolejnym czynnikiem ryzyka. Skoro już jesteśmy przy firmowych epidemiach, na żywo mogę jeszcze opowiedzieć o epidemii larwy wędrującej (uwaga obleśne zdjęcie).

Poprawny układ palców na klawiaturze. Źródło ilustracji i informacje o autorze: https://pl.wikipedia.org/wiki/Pisanie_bezwzrokowe#/media/File:BezwrokowyMac.png
Poprawny układ palców na klawiaturze. Źródło ilustracji i informacje o autorze: https://pl.wikipedia.org/wiki/Pisanie_bezwzrokowe#/media/File:BezwrokowyMac.png

Kto by pomyślał, że po tych bogatych doświadczeniach, w ciągu trzech głupich minut popsuję sobie lewy nadgarstek tak, że będzie wymagał operacji… Wniosłam (wespół z mężem, który po moich naciskach niechętnie  przystał na taką współpracę) na piętro ciężki stół. Bo drażnił mnie w przejściu, a ciągle nie mieliśmy odpowiednio krzepkich gości do pomocy. W efekcie nadwyrężyłam nadgarstek. Sądziłam, że po dwóch dniach wróci do normy, ale było gorzej i gorzej. Na końcu tak źle, że nie byłam w stanie wyjąć dziecka z łóżeczka. Nawet jak nie wierzgało.

Dalej wydarzenia potoczył się szybko. Diagnoza: zespół de Quervaina. Rozwiązanie: operacja o nazwie „uwolnienie zmienionych zapalnie pochewek ścięgnistych” 🙂 Jakimś cudem objęta firmowym pakietem medycznym.

Wielkiego dnia udało mi się przekonać panią anestezjolog i lekarza wykonującego zabieg, że jestem wyjątkowo stabilna psychicznie i w związku z tym nie wyrwę im ręki podczas zabiegu. Dzięki temu obyło się bez narkozy i nocowania w szpitalu (dość kłopotliwa sprawa przy niemowlęciu karmionym piersią), a ja miałam okazję zaobserwować atrakcje takie jak (uwaga, gore!) wyciskanie krwi z ręki poprzez jej owinięcie grubą gumą. Kiedy rozłożono parawan jak przy cesarskim cięciu, nabrałam wielkiej ochoty do ucieczki… Na szczęście w porę przypomniałam sobie o swojej obietnicy. Trochę by jednak było wstyd.

W obecnej chwili wychodzę na dwór w długich rękawiczkach (patrz nagłówek wpisu; kupiłam je dla żartu na Wielkanoc), ponieważ bez nich wyglądam jak niedoszły samobójca.

Mój nadgarstek dziś przy kawie :)
Mój nadgarstek dziś 🙂

Nadgarstek wreszcie działa jak powinien, czego Wam wszystkim życzę 🙂

Bonus. W temacie problemów ze ścięgnami przypomniał mi się wyjątkowo lubiany przez publiczność rysunek mojego wypadku z Achillesem na zakończenie festiwalu Malta w 2011:

Dawno, dawno temu...
Dawno, dawno temu…

Konkursy algorytmiczne a przedwczesna optymalizacja

Z algorytmami mam trochę jak z grą w szachy. Lubię sobie czasem pogłówkować, ale nigdy nie wystarczyło mi wytrwałości, żeby przysiąść, poczytać, zapamiętać i wznieść się na naprawdę wysoki poziom. W przypadku algorytmów, na (moje) szczęście, do potraktowania sprawy poważniej w pewnym stopniu zmusiły mnie uczelnia i życie zawodowe.

Wspominałam już, że mam ostatnio więcej czasu niż zwykle. Mimo że mój tymczasowo zalany prolaktyną mózg ma problemy z obliczeniem należnej reszty przy zakupach, postanowiłam rozerwać się, rozwiązując zadania ze startujących właśnie Potyczek Algorytmicznych. Potyczki to otwarty konkurs programistyczny organizowany przez Uniwersytet Warszawski, w którym przez kilka dni rozwiązuje się zadania online, a na koniec najlepsi uczestnicy zapraszani są do rywalizacji w stacjonarnym finale.

W weekend zapoznałam się z zadaniami z rundy próbnej i przeżyłam nieprzyjemne zaskoczenie. Okazało się, że udostępniana uczestnikom konkursu sprawdzarka nie przeprowadza kompletu testów, ani nawet reprezentatywnego ich podzbioru. Zamiast tego, testuje program jedynie na jednym bądź dwóch prostych przykładach par wejście/wyjście podanych w treści zadania. Dopiero po zamknięciu danej rundy nadesłane przez uczestnika konkursu rozwiązanie jest poddawane całemu pakietowi testów.

Czy umknął mi jakiś nowy trend? Tego typu podejście to norma czy wyjątek?

Takie stawianie sprawy budzi mój głęboki opór, ponieważ, cytując klasyka:

Przedwczesna optymalizacja jest źródłem wszelkiego zła.

– Donald Knuth

Przedwczesna optymalizacja to (u)znany antywzorzec projektowy. Po pierwsze, problemy często leżą zupełnie nie tam, gdzie się ich spodziewamy. Po drugie, optymalizacja często zmniejsza czytelność kodu. Jeśli nie jest potrzebna (program w oryginalnej wersji wykonuje się w czasie w zupełności akceptowalnym dla klienta), prowadzi do samych problemów, jak dodatkowe godziny pracy następnego programisty, który musi utrzymywać nieintuicyjnie napisany kod. Po trzecie wreszcie, jeśli nie zdefiniujemy granicy, optymalizować można właściwie w nieskończoność, lub przynajmniej do poziomu operacji na bitach.

Czy o to powinno chodzić w konkursie algorytmicznym? Rozumiem, że TDD (programowanie sterowane testami) dominuje w „przemyśle”, a konkursy rządzą się swoimi prawami, ale nie wydaje mi się dobrym pomysłem stawianie ich w takiej opozycji do dobrych praktyk.

PS. Smaczku całej sprawie dodaje fakt, że, przynajmniej w przypadku zadań próbnych, nie podano limitu czasowego, który obowiązuje w automatycznych testach…

PS2. Wykres w nagłówku w oryginalnej wersji był opisany, ale ostatecznie postanowiłam zamienić go na tematyczną zagadkę. Stawiam piwo pierwszej osobie, która poda pełne opisy X, Y, K i E 🙂

Elegancki algorytm miesiąca: Kadane

Mój pracodawca niespodziewanie wpadł na pomysł poddania wszystkich programistów testom algorytmicznym. Plan niepokojący, zwłaszcza dla „seniorów”, wobec których oczekiwania są wysokie, a którzy na co dzień raczej nie implementują własnoręcznie ekstrawaganckich algorytmów sortowania.

Na szczęście (niekoniecznie dla efektów pracy projektowej) w ramach zachęty otrzymaliśmy możliwość uczestnictwa w pięciodniowym kursie algorytmicznym. Mam za sobą dwa takie dni i muszę powiedzieć, że wrócił mi zapał do programowania, jakiego nie czułam od lat!

Urzekł mnie pewien króciutki i bardzo elegancki algorytm rozwiązujący problem znalezienia podciągu o największej sumie.

Problem

Niech dana będzie tablica (ciąg) liczb o długości co najmniej 1.

4 -10 3 29 -3 12 -5 4

Zadanie polega na znalezieniu w tablicy spójnej podtablicy o największej sumie elementów i zwróceniu tej sumy. W naszym przypadku całkowita suma elementów tablicy to 34, natomiast maksymalna suma podciągu elementów to 41. Elementy składające się na tę maksymalną sumę oznaczyłam kolorem czerwonym.

Programujesz?

Poświęć chwilę na rozwiązanie tego problemu. Jaką złożoność obliczeniową ma Twój program?  Brute force to pewnie O(n2). O(nlogn)? Nieźle. Ile masz linii?

Niniejszym przedstawiam przepiękny, pięciolinijkowy algorytm o złożoności liniowej, czyli O(n).

Programowanie dynamiczne

Eleganckie rozwiązanie tego problemu jest oparte na pomyśle określanym mianem „programowania dynamicznego”. Co to znaczy?

Można zauważyć, że niektóre problemy algorytmiczne da się podzielić na mniejsze podzadania.

  • Jeżeli podzadania te są od siebie niezależne, w ramach uproszczenia warto zastosować metodę „dziel i zwyciężaj” – w ten sposób działa wiele dobrych algorytmów sortowania (np. quicksort).
  • Jeśli podzadania w jakiś sposób na siebie nachodzą i jedne wyniki są inkrementacyjnie zależne od drugich, można spróbować użyć programowania dynamicznego.

Programowanie dynamiczne przypomina stosowanie rekurencji, z tą różnicą, że potrzebne nam wyniki cząstkowe wyznaczamy tylko raz. Wynik możemy konstruować wstępująco (najpierw wynik dla najmniejszego podproblemu, potem narastająco dla coraz większych zadań) lub zstępująco (definiujemy „rekurencyjną” zależność pomiędzy wynikiem większego problemu a problemami mniejszymi, tyle że potrzebne nam wyniki zapamiętujemy w jakimś buforze i nie wyznaczamy ich ponownie).

Algorytm Kedane’a

Implementacja w Pythonie dla tablicy A wygląda tak:

I już!!!

Jak to działa?

Najpierw wyznaczamy wynik dla najmniejszej tablicy, o długości jeden. Suma elementów tablicy o tej długości (największa, najmniejsza i każda inna suma) to oczywiście wartość jedynego elementu (A[0]).

Przez cały czas działania algorytmu będziemy utrzymywać dwie zmienne: max_total to nasz najlepszy napotkany do tej pory wynik, natomiast max_local to najlepszy wynik zawierający aktualnie obsługiwany element.

Przechodząc przez kolejne elementy,  za max_local każdorazowo podstawiamy większą z dwóch liczb: aktualny element x lub dotychczasową wartość max_local zwiększoną o x.

Jeśli nowy wynik lokalny jest większy od max_total, zamieniamy wartość max_total.

Ostatnia wartość max_total jest naszą odpowiedzią dla problemu wielkości całej tablicy.

Studium przypadku

Zakresy w tabeli oznaczyłam odpowiednim formatowaniem. Zielone elementy składają się na max_local, a podkreślone na max_total.

Zatem, dla naszej początkowej tablicy, algorytm będzie przebiegał następująco:

Element 0
4
  • max_local = 4
  • max_total = 4
Element 1
4 -10
  • max_local = max(-10,-10+4) = -6
  • max_total = max(4,-6) = 4
Element 2
4 -10 3
  • max_local = max(3,-6+3) = 3
  • max_total = max(4,3) = 4
Element 3
4 -10 3 29
  • max_local = max(29,3+29) = 32
  • max_total = max(4,32) = 32
Element 4
4 -10 3 29 -3
  • max_local = max(-3,32-3) = 29
  • max_total = max(32,29) = 32
Element 5
4 -10 3 29 -3 12
  • max_local = max(12,29+12) = 41
  • max_total = max(32,41) = 41
Element 6
4 -10 3 29 -3 12 -5
  • max_local = max(-5,41-5) = 36
  • max_total = max(41,36) = 41
Element 7
4 -10 3 29 -3 12 -5 4
  • max_local = max(4,36+4) = 40
  • max_total = max(41,40) = 41

Ładny, prawda? 🙂

Posłowia

  1. „Algorytm Kadane’a” piszemy z apostrofem, inaczej niż na przykład „Algorytm Kruskala”. Swego czasu, doprowadzona do ostateczności nadużywaniem apostrofu w polskim Internecie popełniłam wpis na ten temat. W najbliższej przyszłości zamierzam odświeżyć go i opublikować także tutaj, gdyż plaga ta zatacza coraz szersze kręgi.
  2. Pamiętam, że w poprzednim wpisie (Ciągła Integracja: anioł stróż dobrego programisty) obiecałam pokazać, jak stworzyć plan na serwerze Bamboo. Jeszcze chwilka.

Kup swojemu dziecku sobie robota Lego Mindstorms

To prawda, mojej sadze o językach programowania ciągle brakuje zakończenia. Jeszcze chwilka! W międzyczasie dzielę się ciągle aktualnym tekstem z poprzedniego bloga.

Pamiętasz swoje pierwsze spotkanie z klockami Lego?

Pierwsze spotkanie

Mnie od pierwszego wejrzenia zachwyciły czyste kolory, przemyślane projekty oraz możliwości, jakie dawała ta zabawka dziecku chętnemu do używania wyobraźni. Oszczędzałam kieszonkowe i na każde urodziny zamawiałam statki pirackie i zamki na morzu.

Natychmiastową niechęcią zapałałam natomiast do modeli Paradiso, reklamowanych jako „Lego dla dziewczynek”. Na szczęście projektanci z Lego wiele się nauczyli od tego czasu.

Niestety nie mam żyłki inwestora – wyrzucałam pudełka i instrukcje, przez co po latach jestem posiadaczką dwóch koszy mieszanki Lego o wszystkich smakach. Nie uda mi się odsprzedać historycznych zestawów z dziesięciokrotnym przebiciem.

Po latach namiętność (finansowana już w pełni z własnej kieszeni) wróciła ze zdwojoną siłą. Nasz stryszek obecnie wygląda tak:

stryszek
Stryszek

Dla zaawansowanych: Lego Technic

Jeśli masz smykałkę konstruktorską, być może masz doświadczenia z Lego Technic – serią bardziej skomplikowanych zestawów z ruchomymi częściami, a nawet silniczkami. Sama długo ich unikałam – wydawały mi się koszmarnie brzydkie! 🙂

2potwór
Zdalnie sterowany potwór Dawida

Tymczasem na szczycie…

Lego Technic nie jest jeszcze szczytem ewolucyjnej drabiny duńskiej firmy. Już 1998 roku, dzięki współpracy Lego z MIT, narodził się nowatorski pomysł stworzenia i wprowadzenia do (w miarę) masowej produkcji programowalnego robota Lego Mindstorms. Opracowany wtedy zestaw składał się z programowalnej kostki oraz zbioru sensorów i silniczków.

Na zdjęciach w dalszej części wpisu widać robota w wersji NXT 2.0 – takiego mam w domu. Od września 2013 dostępna jest nowsza wersja, EV3. Napiszę o niej, jak tylko ktoś mi takiego robota wypożyczy!

Robot Lego Mindstorms wygląda mniej więcej tak:

Udomowiony Mindstorms (przynosi drinki)

Jak zbudować robota?

W skład zestawu wchodzą następujące elementy:

  • Programowalna kostka: na zdjęciu to duży biały element z ekranem.
  • Cztery sensory:
    1. Czujnik ultradźwięków. To „oczy” robota na zdjęciu. Używa ultradźwięków do określenia odległości (w centymetrach lub calach) do przedmiotu znajdującego się przed nim.
    2. Czujnik dźwięku. Mikrofon określający (za pomocą decybeli lub procentów) natężenie dźwięku w otoczeniu. Na zdjęciu widać go po lewej stronie ekranu.
    3. Czujnik dotyku. Na zdjęciu nie widać go zbyt dobrze – to „ogonek” z tyłu robota. Jest wyposażony w pomarańczowy przycisk. Czujnik ma tylko dwa stany: wciśnięty i zwolniony.
    4. Czujnik światła bądź koloru. Na zdjęciu niewidoczny, ponieważ znajduje się na spodzie robota. W zależności od wersji  jest to albo czujnik światła (określa natężenie światła) lub kolorów. Czujnik światła pozwala odróżnić od siebie podstawowe kolory (np. czerwony od niebieskiego), ale może to wymagać kalibracji w zależności np. od pory dnia.
  • Trzy silniczki krokowe. Robot na zdjęciu ma dwa niezależnie działające koła, z których każde „zużywa” jeden silnik, oraz łapę, która otwiera się i zamyka dzięki pracy trzeciego silnika i kilku zębatek.
  • Pewien podzbiór tradycyjnych elementów Lego i Lego Technic – różny w zależności od wydania.

Co można zrobić z zestawem Mindstorms? Po pierwsze, można zbudować robota: według własnego projektu, projektu znalezionego w Internecie (np. tutaj), lub dowolnego projektu Lego Technic, w którym będzie upchnąć niezbyt poręczną kostkę.

A potem… Potem robota można zaprogramować.

Programowanie zabawki, czyli co dokładnie?

Istnieją trzy sposoby programowania robotów Mindstorms. Najprostsze, ale też dające najmniejsze możliwości, jest programowanie z użyciem samej kostki. W menu można znaleźć opcje takie jak „idź do przodu”, „poczekaj na wciśnięcie przycisku”, „powtórz”. Nawet małe dziecko zdoła w ten sposób wpłynąć na zachowanie robota. Warunkiem sukcesu jest podłączenie czujników i silniczków do odpowiednich portów, by „do przodu” powodowało ruch obu kół, a nie, na przykład, jednego z kół i chwytnej łapki.

4kostka
Programowalna kostka i jej menu

Kolejny poziom wtajemniczenia to programowanie z użyciem interfejsu graficznego. Jest intuicyjne i przyjemne. Oferuje przy tym większe możliwości, niż początkowo mogłoby się wydawać (przynajmniej ja byłam zaskoczona). Jeśli chcesz zaprogramować coś w tym środowisku, musisz przeciągnąć wybrane elementy z menu i upuścić je na planszę, a następnie połączyć je w odpowiedniej kolejności. Dostępne są ikonki reprezentujące odczyty sensorów i ruch silników, a także instrukcje sterujące, takie jak pętle czy warunki.

„Kod” widoczny na rysunku poniżej to prosty program robota jadącego po linii zamkniętej w okrąg. Łatwo zauważyć zewnętrzną pętlę i wewnętrzną instrukcję „jeśli – to”, sprawdzającą odczyt z czujnika koloru.

5bloki
Programowanie przy użyciu interfejsu graficznego („bloków”)

Wreszcie, można programować robota „normalnie”, czyli pisząc kod. Programy napisane w niektórych językach (np. NXC: Not eXactly C) można uruchamiać w fabrycznie instalowanym środowisku kostki Mindstorms, inne natomiast (np. oparty o Javę leJOS NXJ) wymagają wymiany tzw. firmware.

Zabawa procentuje

Że Mindstorms to świetna zabawa – o tym nikogo chyba nie trzeba przekonywać? Nie sposób także przecenić walorów edukacyjnych tej zabawki (u dzieci i nie tylko). Wrócę na chwilę do tematu poruszonego już w pierwszym wpisie na tym blogu. To, co jeszcze 10 lat temu było uznawane za biegłość w obsłudze komputera, dzisiaj stanowi absolutną podstawę. Znajomość podstaw programowania ułatwia życie.

Na najbardziej elementarnym poziomie programowanie = logiczne myślenie. Programowanie zmusza twórcę kodu do planowania swoich działań i przewidywania ich wyników. Programowanie to konieczność poświęcenia czasu i cierpliwości na znalezienie poprawnego (lub wystarczająco dobrego!) rozwiązania praktycznego problemu.

Na pewno chciałabym, żeby moje dziecko wcześnie posiadło taki zestaw umiejętności.

Film!

Na zakończenie polecam filmik przedstawiający robota, który dzięki żyroskopowi (niestandardowy sensor, spoza zestawu) potrafi balansować kubkiem pełnym kawy… No prawie.