Programozás‎ > ‎Feladatok‎ > ‎

Perkoláció

A perkoláció fordítható például átszivárgásnak. Egy rövid jegyzet itt. Például perkolációs modellel írható lehet, ahogy a víz / gőz átszivárog a kávéfőzőben a kávé-szemcsék között. Használják járványterjedés leírására és szociális hálók (információterjedés) modellezésére is.

A következőkben egy lehetséges modellt fogunk programozni, és a program alapján statisztikát készítünk. Opcionális: a perkoláció grafikus megjelenítése.

Egy egyszerű perkolációs modell

Veszünk egy N x N -es rácsot. A rács bizonyos mezői "üresek", más mezői valamilyen anyaggal telítettek. (Például levegő / kávészemcse.) Erre a rácsra felülről valamilyen folyadékot öntünk, ami a szabad mezőkön keresztül tud lefele (néha oldalra vagy felfele is) terjedni. 


Ha a folyadék eléri a legalsó szintet, akkor a rács "perkolált", vagyis átszivárgás történt. Érezhető, hogy minél több szabad/üres mező van a rácsban, annál nagyobb az esélye az átszivárgásnak. Szimulációnk célja ezen intuitíven látható kapcsolat számszerűsítése, vagyis annak kimérése, hogy ha az összes mező p%-a üres, akkor mi a perkoláció valószínűsége.

A modellben azt feltételezzük, hogy a folyadék élszomszédos üres mezőkön keresztül tud terjedni, és a felülről érkező nyomás olyan nagy, hogy felfele is tud terjedni (mint az alábbi ábra jobb szélén látható).


Feladatok

  1. Írjunk programot, ami a p paraméternek megfelelően generál egy N x N -es rácsot, ahol minden mező (egymástól függetlenül) p%-os valószínűséggel üres. Ezután szimulálja a folyadék terjedését, és eldönti, hogy történt-e átszivárgás. (Kirajzolhatjuk grafikus vagy szöveges képernyőre a rács állapotát a szimuláció végén.)
  2. Az előző szimulációt sokszor lefuttatva készítsünk statisztikát arról, hogy p függvényében mekkora az átszivárgás valószínűsége. (Az eredmény meglepő!)

Címkék

A feladat forrása: Coursera, Sedgewick Introduction to Algorithms, http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
Algoritmusok: szimuláció, véletlenszámok, statisztika (Haladó megoldás: "unió-holvan" adatszerkezet).