Nenad Božidarević
Mart 2011.

Računanje broja Pi Monte Karlo metodom

Pre nekoliko dana na predavanju iz Verovatnoće i statistike dotakli smo jednu zanimljivu temu – problem Bifonove igle (Buffon’s needle).

U ravni je dat skup paralelnih pravih, pri čemu je rastojanje između susednih pravih a, a > 0. Na ravan se baca igla dužine l, l < a. Odrediti verovatnoću da igla seče neku od pravih. ("Verovatnoća i statistika za inženjere i studente tehnike", Milan Merkle)

Bacanje igle kod Bifonovog problemaU pitanju je običan zadatak iz verovatnoće, ali ono što ga čini posebno zanimljivim jeste činjenica da se na osnovu baš ovakvog bacanja igle može odrediti broj π. Naime, zbog različitih uglova pod kojima igla može da se nađe u odnosu na pravu (kao na slici), u formuli za verovatnoću figuriše broj π. Ako znamo njegovu vrednost, možemo odrediti verovatnoću — ali ako je ne znamo, možemo baciti iglu veliki broj puta da bismo dobili verovatnoću, a onda preko nje izračunati π.

Naravno, jasno je da “veliki broj bacanja” uopšte nije lako izvesti. Ako želimo iole preciznije rezultate, nekoliko hiljada teško da će biti dovoljno, pa se mora stremiti ka daleko većim brojevima. Italijanski matematičar Mario Lazzarini je početkom 20. veka izveo ovaj eksperiment sa 3408 bacanja i dobio vrednost 355/113, što je 3.14159292. Za poređenje, vrednost broja π je 3.14159265, odnosno razlikuju se tek na sedmoj decimali. Članak na Wikipedii objašanjava zašto je dobijena ovako precizna vrednost sa malim brojem bacanja, ali nas to trenutno interesuje. Zanemarićemo njegove rezultate, i pokušati lično da izračunamo π uz pomoć kompjuterske simulacije koja nam omogućava da izvršimo milione “bacanja” u samo jednoj sekundi.

Pročitaj ostatak teksta

Bubble Cup 4

Bubble Cup 4Bubble Cup je timsko takmičenje u rešavanju algoritamskih problema organizovano po ugledu na ACM-ICPC, odnosno zasnovano na ACM pravilima. Organizator je Microsoft Development Center Serbia, u saradnji sa Društom za informacione sisteme i računarske mreže i Univerzitetom u Beogradu. Ove godine se takmičenje ponovo održava, i to četvrti put za redom.

Na takmičenju mogu da učestvuju učenici osnovnih škola, učenici srednjih škola i studenti, koji formiraju timove od po tri člana. Svi timovi učestvuju u dve kvalifikacione runde u aprilu i maju, koje se rade preko Interneta, nakon čega se sabiraju bodovi i prvih 16 timova biva pozvano na finale u Beogradu koje se održava početkom septembra. Finale traje pet sati tokom kojih timovi treba da reše što više zadataka (ukupno ih ima 7+), i to za što kraće vreme. Svaki tim dobija po jedan računar, i to je jedini resurs koji se može koristiti — Internet, naravno, nije dostupan (ali zato sendviči i piće jesu). Bodovanje zavisi od vremena koje je tim utrošio za rešavanje zadatka, kao i od broja pogrešnih rešenja. Detaljnija pravila i objašnjenja možete naći na sajtu takmičenja.

Zadaci koji dolaze na Bubble Cup su tipični algoritamski problemi (dinamičko programiranje, grafovi, geometrija), uglavnom na nivou Državnog takmičenja iz informatike ili Srpske informatičke olimpijade, mada se neretko provuku i daleko teži problemi.

2008. godine, kada je ovo takmičenje prvi put održano, bilo je nacionalnog karaktera, dok je već sledeće godine pretvoreno u regionalno takmičenje, što je među konkurenciju dovelo i veoma jake timove iz Rumunije i Hrvatske.

Prva runda četvrte iteracije ovog takmičenja počinje 1. aprila, a registracije su već otvorene za zainteresovane programere.

Microsoft Serbia zapošljava

Microsoft Development Center Serbia (MDCS — centar za razvoj softvera). Osnovan 2005. godine.

Microsoft Development Center Serbia

Iako je u pitanju mali razvojni tim od svega 50 ljudi, stvari kojima se MDCS bavi nisu nimalo naivne. Među najbitnijim projektima su svakako prostorna (spatial) komponenta SQL Servera, prepoznavanje rukopisa pri pisanju običnog teksta (podrška za različita pisma), ali i matematičkih formula, i Microsoft Math. U januaru 2011. godine je objavljena četvrta verzija programa Microsoft Mathematics koju je naš tim znatno unapredio otkad su je dobili kao projekat.

Glavna prednost našeg razvojnog tima, koji okuplja ljude i iz okolnih zemalja, jeste jaka matematička osnova na kojoj se svi projekti i baziraju. Zbog ovoga se neretko dešava da zaposleni u MDCSu budu pozvani u Redmond (sedište Microsofta) na kraći, duži ili neoređeni period, što govori o kvalitetu naših programera, a takođe stvara i potrebu da se svake godine zapošljavaju novi ljudi koji bi zamenili ove koji su otišli.

Pročitaj ostatak teksta