Clasele 9-12 lecția 1 - 17 sep 2014

From Algopedia
Jump to navigationJump to search

Date de contact și adrese utile

  • Mă numesc Cătălin Frâncu, sunt fost olimpic și absolvent al colegiului Tudor Vianu. Acesta este al treilea an în care țin cercul de informatică pentru liceu.
  • Toate notele de curs sunt publicate pe Algopedia (inclusiv cele din anii trecuți).
  • O bună parte din notele de curs sunt adaptate după Introduction to Algorithms de Cormen, Leiserson, Rivest și Stein (alintată și Cormen, CLR sau CLRS).
  • Pentru probleme, vom lucra cu Varena, o instalare de Infoarena. Aici veți găsi temele și, ocazional, concursurile locale.
  • Desigur, vom folosi și probleme de pe Infoarena, Campion și altele.
  • Pentru a comunica în afara cercului, folosim lista de discuții liceu@varena.ro. Înscrierea este obligatorie. Pentru a vă înscrie, trimiteți un mesaj gol la liceu-subscribe@varena.ro.
    • Vă rog să folosiți numele real în adresa de e-mail sau, cel puțin, să-mi trimiteți un mesaj separat în care să-mi spuneți cine sunteți. Nu intrăm acum în detalii despre „netichetă”, dar vă cer aceasta din motive logistice. Dacă primesc un mesaj fără cap și coadă de la „jmekeru17”, vreau să știu la cine să mă rățoiesc când ne vedem în clasă.

Generalități despre cerc

În primul rând, cercul este opțional. Ne întâlnim timp de două ore pe săptămână numai dacă ne face plăcere. Veniți doar dacă sunteți siguri că asta vreți să faceți cu acele două ore. Dar dacă veniți, puneți suflet în asta.

  • Avem nevoie de atenție și de liniște; fără distrageri, fără jocuri, fără Facebook.
  • Contribuiți! Nimeni nu le știe pe toate, în special eu. Propuneți probleme și rezolvări, propuneți subiecte noi de discuție.
  • Curiozitatea și dorința voastră de învățare sunt fundamentale. Dacă puteți trece cu seninătate peste o problemă pe care nu știți să o faceți, dacă nu vă ține treji dorința de a-i da de cap, acesta este un semn al unui creier leneș. Se poate trăi bine-mersi cu un creier leneș, dar trebuie să vă puneți întrebări mari dacă ați ales bine calea informaticii.
  • Discuție despre neurogeneza adultă. De ce nu putem lua pauză de la învățat.
  • Prezența la cerc este obligatorie. În situații speciale, evident, facem excepție, dar tema rămâne obligatorie.

Cercul pornește de la nivelul programei, dar în timp o depășește. Dacă, după o vreme, simțiți că nu mai puteți ține pasul, nu vă descurajați. Poate este un semn că trebuie să urmăriți, mai întâi lecțiile de la clasă. Programa de algoritmică este bine făcută, iar profesorii din Tudor Vianu sunt fantastici. În plus, veți avea întotdeauna acces la temele și la notele de curs ale cercului.

Teme săptămânale

Începând de anul acesta, mă voi strădui să compun teme săptămânale. Temele sunt obligatorii, dar ușoare (se vor baza pe noțiunile predate la cerc).

Primele probleme vor valora 100p, exact scorul de pe Varena. După ce vom discuta despre bunele practici de codare (cândva în 2014), problemele vor valora 120p: 100p de pe Varena și 20p pentru stilul de codare. Da, îmi voi arunca privirea peste sursele trimise la teme.

Mă voi gândi la un premiu atrăgător pentru cele mai bune scoruri la teme, la sfârșitul anului. Dar, desigur, nu de aceea facem temele. :-) Le facem pentru că:

  • Implementarea este parte integrantă din algoritmică, nu doar o mică extensie a ceea ce predăm în clasă.
  • Un creier cu deprinderi proaste va reuși să implementeze încâlcit un algoritm simplu.
  • Îmi place să cred că pot contribui la calitatea și claritatea codului pe care îl scrieți.
  • Fiecare algoritm are particularitățile lui la implementare; nu așteptați să vă poticniți de ele tocmai la concurs!

Facem informatică, nu doar pregătire pentru olimpiadă

Olimpiada este importantă. Vă doresc tuturor să luați maxim de punctaj! Dar olimpiada este doar o măsurătoare ocazională a unui lucru mult mai profund: valoarea voastră reală. Pe aceea vrem noi să o creștem.

  • Să lucrăm doar pentru olimpiadă înseamnă să inversăm cauza cu efectul.
  • Axarea exclusiv pe olimpiade duce la un stil în care orice este permis, oricât de urât ar fi codul.
  • Discuție despre câinele lui Pavlov, stimuli și reflexe condiționate
    • Reflexul lui Pavlov invers: să pui salivă în gura unui câine ca să antrenezi un bec să se aprindă
    • Despre cargo cults, WWII, căști din nuci de cocos și avioane de paie
    • Morala? Nu există scurtături, chiar dacă trăim într-o țară care numai asta visează.
  • Olimpiada ține până într-a 12-a. Dar apoi? Veți începe să scrie programe tot mai mari, veți merge la companii mari, poate veți deveni profesori. Dacă vă permiteți să acumulați tot felul de carențe în numele unor concursuri efemere, veți pierde pe termen lung.

Cu toții ne oprim undeva la olimpiadă (la sector sau la lot), ceea ce ne dă un sentiment de inutilitate și de relaxare „până la anul”. Dacă înțelegeți că ce contează cu adevărat este învățătura, atunci nu veți mai simți nevoia să luați pauză.

Despre codare

Dincolo de teme, vă încurajez să cereți opinii despre codul vostru, mie sau colegilor voștri, oricând nu sunteți mulțumiți și simțiți că implementarea voastră este greoaie.

Iată de ce consider că este bine să citiți codul altora și reciproc.

  • Baza perfecționării este schimbul de idei între oameni.
  • Este foarte posibil să vi se fi predat un stil prost. Sunt convins că, la vârsta voastră, nu aveți un stil foarte curat.
  • Mai ales de când cu site-urile automate, nimeni nu prea mai știe ce codați voi.
  • De vină suntem și noi, profesorii, care ne bucurăm că elevii știu mulți algoritmi, dar nu ne interesăm cum îi implementează.
  • Reflexele se dezvață greu, iar reflexele proaste trebuie dezvățate cu multă insistență.
  • Un program încâlcit este de obicei rezultatul unei gândiri încâlcite.
  • La concursuri, totul este permis, dar aici suntem la antrenamente. Fiți ordonați!
  • Sunteți destul de mari ca să programați nesupravegheați; totuși, mulți din oamenii pe care îi cunosc sunt destul de mari ca să conducă o mașină, dar nu m-aș sui în mașină cu ei.
  • Nu în ultimul rând, nu vă simțiți lezați! Codul-sursă este făcut ca să fie văzut. Nu ascultați propaganda firmelor producătoare de software neliber, care ne învață că programatorii au drept de viață și de moarte asupra programelor lor (și, dacă s-ar putea, și asupra utilizatorilor).

Vom detalia, într-o lecție separată, lucruri ca programarea (ne)structurată, spațierea, abuzul de STL și multe altele.

Probleme de logică

Începem anul lejer, cu probleme de logică, dar care bat spre algoritmică.

Ghicirea unui număr #1

Ana alege un număr între 1 și 10.000. Bogdan trebuie să ghicească numărul din cât mai puține încercări. La fiecare încercare, Ana îi spune lui Bogdan dacă numărul ghicit este mai mare, mai mic sau egal cu numărul ascuns. Bogdan pierde jocul dacă ghicește un număr prea mare de două sau mai multe ori. Câte întrebări îi sunt necesare lui Bogdan? Dar dacă Ana are voie să ascundă un număr arbitrar de mare?

Ghicirea unui număr #2

Ana alege un număr întreg aleator între 1 și 10.000. Bogdan trebuie să ghicească numărul din cât mai puține încercări. La fiecare încercare, Ana îi spune lui Bogdan dacă numărul ghicit este mai mare, mai mic sau egal cu numărul ascuns. În plus, dacă Bogdan ghicește un număr prea mare, Ana își alege un nou număr, tot aleator. Câte întrebări îi sunt necesare lui Bogdan (în medie)?

Prizonierii și becul

Aici chiar aveți ce programa.

O sută de prizonieri au fiecare celula proprie. Închisoarea are o grădină în care există o lampă. Zilnic, gardianul alege un prizonier la întâmplare și îl scoate la plimbare prin grădină. Dacă dorește, prizonierul poate să schimbe starea lămpii din grădină. În orice zi, orice prizonier poate afirma că toți prizonierii au vizitat grădina cel puțin o dată. Dacă afirmația este falsă, atunci toți prizonierii sunt executați. Dacă afirmația este adevărată, toți prizonierii sunt eliberați. Înainte de începerea experimentului, prizonierii pot discuta între ei ca să-și aleagă o strategie, dar apoi nu mai pot comunica între ei. Propuneți o strategie deterministă care să-i elibereze cât mai repede (în medie).

Încercați diverse strategii și vedeți cât de jos puteți coborî valoarea așteptată. Veți avea nevoie de matematică pentru a evalua unele soluții. Dacă nu reușiți, scrieți un program care să simuleze strategia propusă. Un algoritm destul de simplu produce un timp de circa 28 de ani până la eliberare, dar se poate mult mai bine (recordul găsit până acum este pe la 10 ani).

Dar dacă am permite o abordare probabilistă?

Diverse probleme cu cântăriri

Toate problemele de mai jos folosesc o balanță cu două talere. Ea poate sta în echilibru sau se poate înclina spre unul dintre talere, după cum punem pe ele greutăți egale sau diferite.

(a) Ni se dau 9 bile, identice ca formă, din care una este mai ușoară. Cum o putem afla din două cântăriri?

(b) La fel, dar cu 10 bile.

(c) Ni se dau 12 bile, din care una diferă ca greutate. Cum o putem afla din trei cântăriri?

  • Discuție despre spațiul soluțiilor și numărul minim de operații necesare în mod teoretic.
  • Așa se demonstrează că sortarea prin comparații necesită cel puțin O(n log n) operații.

(d) La fel, dar cu 13 bile. Este întrunită limita teoretică? Avem o soluție practică?

(e) Ni se dau 6 bile, din care trei sunt ușoare (și egale între ele), iar trei sunt grele (și egale între ele). Cum le putem separa prin numărul minim de cântăriri?

(f) Nu se dau 6 bile: două roșii, două galbene și două albastre. Din fiecare pereche, una cântărește 99 g și una 100 g. Cum le putem separa prin numărul minim de cântăriri?

Două probleme cu pitici și pălării

(a) 10 prizonieri joacă următorul joc cu gardianul lor. Gardianul îi așează în linie, unul în spatele altuia. Apoi le așează câte un fes pe cap, alb sau roșu, la întâmplare. Astfel, fiecare prizonier poate vedea fesurile prizonierilor din fața lui, dar nu pe al său însuși nici pe ale prizonierilor din spate. Începând cu cel mai din spate prizonier, fiecare prizonier anunță „alb” sau „roșu”. Dacă își ghicește culoarea fesului este eliberat, altfel este executat. Prizonierii se pot pune de acord asupra unei strategii. Cum procedează pentru a salva câți mai mulți dintre ei?

(b) 10 prizonieri joacă următorul joc cu gardianul lor. Gardianul le pune pe cap fesuri cu numere extrase aleator din mulțimea [1-10]. Este posibil ca mai mulți prizonieri să capete același număr. Fiecare prizonier poate vedea celelalte nouă numere, dar nu pe al său. La un semn al gardianului, simultan, prizonierii anunță numărul pe care cred că îl au pe cap. Dacă cel puțin unul dintre ei ghicește, toți sunt eliberați. Ce strategie aleg ei pentru a-și maximiza șansele de eliberare?