Note de curs, clasele 11-12, 5 decembrie 2013: Difference between revisions

From Algopedia
Jump to navigationJump to search
 
(No difference)

Latest revision as of 17:53, 4 December 2013

Arbori de sufixe

Am terminat de predat arborii de sufixe, partea de construcție în O(n). Notele de curs au rămas la lecția trecută, ca să nu se fragmenteze.

Intermezzo: probabilități

La cererea publicului :-) vom prezenta câteva noțiuni de probabilități, suficiente cât să rezolvăm problema Ping-pong. Vom prezenta noțiunile prin intermediul unor probleme drăguțe. Sper să fie o diversiune binevenită.

Problemele de combinatorică vă vor ajuta mult și la informatică

Combinatorică

Permutări și combinări cu repetiție.

  • Se dau 10 bile (5 roșii, 2 galbene, 3 verzi). În câte moduri distincte le putem alinia?
  • Am trei cutii cu dulciuri: fursecuri, pișcoturi și biscuiți. În câte moduri distincte (neordonate) pot extrage 5 dulciuri?
  • Câte soluții întregi are ecuația a + b + c = 11, unde a, b, c ≥ 0?
  • Câte soluții întregi are inecuația a + b + c < 11, unde a, b, c ≥ 0?
  • Câți termeni are expresia (a + b + c)20 după ce desfacem toate parantezele?
  • Care este coeficientul lui a8 b5 c7 din dezvoltarea lui (a + b + c)20?

Variabile aleatoare discrete

Exemple: zaruri, cărți de joc, monede.

  • În câte feluri distincte se pot așeza n copii la o masă circulară?
  • Doi prieteni merg la cafenea și amândoi insistă să facă cinste. Ei pot da cu banul, dar nu au încredere în monedă. Aceasta are o șansă p ≠ 50% de a cădea stemă. Cum procedează ei?
  • Invers, doi prieteni doresc să facă un pariu inechitabil pe care primul să-l câștige cu șansa p ≠ 50%. Ei nu au la dispoziție decât o monedă echitabilă. Cum procedează ei?
  • Arunc cu 5 zaruri. Care este probabilitatea să cadă trei zaruri identice, dar nu mai multe?
  • O cofetărie face tarte cu ciocolată și cu vanilie. Zilnic vin 10 clienți care cer, aleator, una dintre cele două tarte. Câte tarte din fiecare trebuie să facă cofetarul ca să-și poată servi clienții cu 95% probabilitate?

Variabile aleatoare continue

Exemple: stricarea unui aparat electronic, temperatura, distanța față de centru la darts

  • Vrăjitoarele la cafenea: două vrăjitoare ajung la o cafenea, separat și independent, oricând între 12:00 și 1:00 noaptea. Fiecare stă exact 15 minute. Care este probabilitatea să se întâlnească?
  • Stau în afara Pentagonului. Se știe că stau suficient de departe încât să văd mai mult de o latură. Care sunt probabilitățile să văd două, respectiv trei laturi?

Valoarea medie

  • Aruncăm cu două zaruri; notăm suma lor cu X. Să se calculeze distribuția de probabilitate a lui X și valoarea medie E(X)
  • Un borfaș vă propune jocul următor. Biletul costă 3 lei. Apoi, dați cu banul până când pică stema. Primiți atâția lei câte încercări ați făcut. Merită să jucați acest joc? Care este prețul corect al unui bilet?
  • Să se calculeze densitatea de probabilitate și valoarea medie: (1) a sumei; (2) a maximului dintre două numere din intervalul [0, 1].

Probabilități condiționate

Formula: P(B|A) = P(A∩B) / P(A)

Două variabile se numesc independente dacă P(A∩B) = P(A) ∙ P(B) ↔ P(A|B) = P(A) ↔ P(B|A) = P(B)

  • Într-o școală se dau două teste (fără eliminare). 42% au trecut primul test. 28% le-au trecut pe ambele. Ce procent din cei care au trecut primul test l-au trecut și pe al doilea?
  • De ce funcționează tragerea la sorți cu un băț mai scurt? Mai exact, de ce au toți participanții șanse egale?
  • Am studiat 10 din cele 25 de subiecte pentru un examen. Trebuie să trag două subiecte și să tratez unul la alegere. Ce șanse am să trag măcar un subiect cunoscut? (Orice asemănare cu persoane reale este comică)
  • Aruncăm cu 2 zaruri A și B. Care este P(A=2)? Dar dacă se știe că A + B ≤ 5?
  • Aruncăm cu un zar de două ori. Sunt următoarele evenimente independente?
    • A = dau 6 la prima aruncare, B = dau 6 la a doua aruncare;
    • A = dau 6 la prima aruncare, B = suma celor două aruncări este 8;
    • A = dau 6 la prima aruncare, B = suma celor două aruncări este 5;
    • A = dau 6 la prima aruncare, B = suma celor două aruncări este 7.
  • Fie două urne: 3A1N și 3N1A. Extrag o bilă la întâmplare și observ că este neagră. O pun la loc și extrag din nou o bilă din aceeași urnă. Care este probabilitatea să fie neagră?
  • Fie trei urne. AA, NN și AN. Extragem o bilă la întâmplare. Dacă ea este albă, care este șansa ca și cealaltă bilă din aceeași urnă să fie albă?
  • Jucăm un joc cu un zar. Dăm pe rând cu zarul. Cine dă primul 6 câștigă. Eu încep. Care este probabilitatea să câștig?
  • Dau cu o pereche de zaruri până când văd o sumă de 5 sau de 7. Care este șansa să văd 5 înainte de 7?
  • Problema cavalerului De Méré (un punct jucat dintr-o partidă până la 3 puncte).
    • Soluția generală, cu r + s - 1 runde, demonstrația cu triunghiul lui Pascal sau prin inducție
    • Implementarea cu programare dinamică

Acum avem arsenalul necesar pentru a rezolva problema Ping-pong.