Programowanie i książki matematyczne

Korzystając z okazji dzisiejszej promocji na książki matematyczne w Helionie, chciałbym zaproponować cztery pozycje dla każdego:

Od matematyki do programowania ogólnego

Jak napisał w swojej recenzji Marek Sawerwain z magazynu Programista: „Książka, autorstwa Alexandera A. Stepanova oraz Daniela E. Rosego, może stać się ważnym elementem kanonu lektur obowiązkowych dla programistów, do których zaliczamy takie pozycje jak „Wprowadzenie do algorytmów” autorstwa Rivesta Clifforda, Thomasa H. Cormena, Charlesa E. Leisersona, „Język ANSI C” Bria-na W. Kernighana oraz Dennisa M. Ritchiego, a także „Sztuka Programowania” Donalda E. Knu-tha, czy „Recz o istocie informatyki” Davida Harela.
Nie jest to typowa książka pośród licznych opracowań z obszaru programowania, ale przez nietypowe połączenie matematyki i praktyki programistycznej należy upatrywać główną zaletę tej pozycji. Każdy kto zajmuje się programowaniem w dowolnym języku (nie tylko w C++) powinien poświęcić trochę czasu na lekturę tej książki, a z pewnością zdobędzie kilka nowych cennych umiejętności.

Czytaj dalej

Permutacje, cz. 2 – algorytmy

W poprzednim wpisie programistyczne rozwiązanie zagadki polegało na wygenerowaniu wszystkich permutacji zbioru i sprawdzeniu każdej z nich pod względem spełnienia warunku poprawności. Takie podejście może okazać się najrozsądniejsze w przypadku pracy nad problemami NP-trudnymi (poprzez wygenerowanie wszystkich możliwych rozwiązań i wybranie spośród nich najlepszej).

W dalszej części umieszczam przykłady implementacji w Javie różnych algorytmów generowania permutacji.

Czytaj dalej

Idź na całość – paradoks Monty’ego Halla

zonkPod koniec lat dziewięćdziesiątych TV Polsat emitował popularny teleturniej Idź na całość. Główna zasada gry była oparta na paradoksie Monty Halla, a polegała na podjęciu decyzji czy pozostać przy swoim pierwotnym wyborze, czy niewiadomą wymienić na inną.

 

Zagraj ze mną

Poniżej masz do wyboru trzy bramki. Możesz wybrać jedną z nich. Gdy już to zrobisz, ja wskażę w której z nich znajdował się jeden z Zonków. Teraz decyzja należy do Ciebie: zostajesz przy swoim wyborze, czy zmieniasz bramkę. Z pozoru podjęta decyzja wydaje się być bez znaczenia – w końcu zostają dwie bramki więc prawdopodobieństwo wygranej powinno być takie samo. Tak jednak nie jest. Mało tego, jedna z tych dwóch strategi daje dwukrotnie większe prawdopodobieństwo wygrania w stosunku do drugiej.

Spróbuj zagrać kilka razy stosując dwie strategie: pozostając przy swoim pierwszym wyborze oraz zmieniając decyzję po wskazaniu Zonka. Zwróć uwagę jak wygląda prawdopodobieństwo wygrania w zależności od strategii.
Symulację napisałem w Javascript, dlatego ktoś bardziej dociekliwy może wygrać w 100% przypadków. Ale nie o to tu chodzi. Dzięki temu każdy ma możliwość zweryfikowania tego czy program przypadkiem nie oszukuje.

Czytaj dalej