Lecție

Prezentarea instructorului

Mă numesc Cristian Frâncu și vă voi ghida în acest an în cadrul cercului de informatică. Sînt un fost elev al liceului Tudor Vianu care s-a întors cu drag înapoi pentru acest cerc. Mă puteți contacta la adresa de email cristian@francu.com.

Prezentarea cercului de informatică

La acest cerc vom face informatică la cel mai înalt nivel. Vom include cunoștințele de olimpiadă dar nu ne vom rezuma la ele. Nu vom învăța materie în avans înainte de a stăpîni bine materia din urmă. Cu alte cuvinte nu vom face dopaj de dragul olimpiadei. Toate lecțiile predate vor fi disponibile electronic, ca pagini web. Locul unde găsiți rezumatul lecțiilor trecute, precum și temele este algopedia.francu.com. Consider că în acest fel vom avea mai multă transparență, toată lumea, inclusiv părinții, vor ști ce facem noi aici. De asemenea vă ușurează vouă munca, nemaifiind obligați să notați totul în timpul orelor de cerc.

Reguli

La acest cerc vom respecta anumite reguli: reguli ale cercului de informatică. Vă recomand să citiți acest document cu mare atenție. Le recomand, de asemenea, și părinților voștri să-l citească. Pe scurt, iată la ce mă aștept de la cei care veniți la acest cerc:

Prezență. Nu sîntem institutul de învățare la distanță. La vîrsta voastră este important să fiți prezenți la cerc. Este în regulă dacă din forță majoră nu veniți o dată la zece lecții. Nu este în regulă dacă din forță majoră veniți una din doua lecții.
Seriozitate. Tratați cercul cu seriozitate. Faceți-vă temele chiar dacă nu voi apuca mereu să le corectez. Nu lipsiți nemotivat.
Dorința de a învăța. Vreau să aveți o atitudine pozitivă, la modul "pot și vreau să fac asta". Nu vreau să aud oftaturi ci vreau să văd sclipiri de bucurie în ochi. Dacă la cerc intrați cu un oftat, poate că nu aici vă este locul. Nu uitați, cercul este absolut opțional și facultativ. Ideal, aș vrea ca elevul de la cerc să dea dovadă de o anume exaltare și curiozitate, să încerce să facă și alte lucruri decît cer eu, în plus față de ceea ce cer eu.
Spirit analitic. Treceți întotdeauna prin filtrul minții voastre ceea ce spun. Uneori voi greși, încercați să vă dați seama că am greșit. Uneori voi greși intenționat, pentru verificare, alteori voi greși genuin. În ambele cazuri exprimați-vă, atrageți-mi atenția.

Test de selecție

Dacă numărul elevilor doritori să participe la cerc este foarte mare (mai mult de 20 de copii) vom da un test de selecție, în urma căruia vom forma două grupe a cîte 15 elevi. Eu voi prelua una din grupe, iar doamna profesoară Isabela Coman va prelua cealaltă grupă. Materia predată va fi aceeași.

Exemple probleme auxiliare

Exemple de jocuri care stimulează mintea: cubul rubik, scrabble flash, powerball
Problemă de matematică: dacă 5 oameni construiesc 6 case în 3 zile în cît timp construiesc 10 oameni 4 case?
Exemple de întrebări puzzle:
- De ce este iarba verde?
- De ce este cerul albastru?
- De ce nu cade luna pe Pămînt?

Algoritmi

Definiție

Ce sînt algoritmii?

Definiție - Algoritm: un set de instrucțiuni sau reguli care, pornind cu un set de date inițiale, rezolvă o clasă de probleme folosind operații precise, executate mecanic, fără intervenția creativă a omului.

Exemple

Exemple: rețete de bucate, asamblarea jocurilor Lego, convorbire telefonică la telefon public, înmulțirea și împărțirea numerelor, navigarea într-un oraș folosind o hartă.

Ne-am putea gîndi la rețetele de bucătărie ca algoritmi. Ele enumeră pas cu pas o procedură care atinge un scop (mîncarea) începînd cu date inițiale (ingredientele) și cerîndu-vă să executați instrucțiuni relativ ușoare și clare. Cu toate acestea, oricare dintre noi a încercat să folosească o carte de bucate știe că "ușoare și clare" sînt termeni relativi. Rețetele tind să fie ambigue ducînd la un potențial coșmar pentru bucătarul neavizat. Și atunci, cum ar trebui să fie o rețetă bine scrisă?

Proprietăți

Pentru a constitui un algoritm, setul de instrucțiuni trebuie să aibă următoarele proprietăți:

Precizie - Sau neambiguitate. Fiecare pas trebuie să fie neambiguu și executabil fără intervenție creativă.
Generalitate - Să rezolve o clasă de probleme, nu doar o problemă în particular.
Finitudine - Algoritmul trebuie să se termine în timp finit. Din punct de vedere practic trebuie să se termine într-un timp rezonabil (de exemplu pînă la sfîrșitul vieții noastre).
Corectitudine - Rezultatul final trebuie să fie corect pentru toate datele de intrare.

Au rețetele de bucate proprietățile de mai sus? Probabil că sînt corecte. De asemenea sînt finite. Nu sînt generale, deoarece gătesc o singură mîncare folosind aceleași ingrediente. Iar multe dintre rețete sînt imprecise, ceea ce, pe de o parte, le transformă în exemple proaste de algoritmi, pe de alta lasă loc pentru creativitate si unicitate.

Scheme logice

Schemele logice sînt un mod de descriere a algoritmilor (un alt mod este pseudocodul). Ele conțin următoarele blocuri:

Bloc de calcul
Bloc de citire sau scriere
Bloc de decizie
Bloc terminator

Bloc de calcul

Așa cum sugerează și numele, aceste blocuri sînt folosite pentru a calcula expresii. De obicei conțin calcule matematice. Exemple:

calculează expresia 2 + 3 și stochează rezultatul (în acest caz 5) în x.
ia vechea valoare a lui x x, îi adună 1 și stochează rezultatul în variabila x, suprascriind vechea valoare. Dacă x era 5 inițial, valoarea finală va fi 6, după execuția acestui bloc.

Bloc de citire/scriere

Aceste blocuri controlează fluxul de date către și dinspre algoritmul nostru. Putem citi valori inițiale, sau să scriem rezultatele. Exemple:

citește o valoare și o depozitează în x. 'C' vine de la 'citește'.
citește două valori, una ce va fi depozitată în x iar a doua în y.
scrie valoarea stocată în y. 'S' vine de la 'scrie'.

Bloc de decizie

Un bloc de decizie este folosit pentru a crea o 'intersecție pe șosea'. Desparte firul execuției în funcție de rezultatul condiției din bloc. Dacă expresia este adevărată execuția algoritmului continuă pe ramura din dreapta. Dacă expresia este falsă execuția continuă cu ramura din stînga. Exemple:

testează dacă x este mai mic ca zece, atunci cînd se ajunge în acest punct al algoritmului. Dacă x este mai mic ca zece continuăm cu blocurile de pe ramura dreaptă. Dacă x este mai mare ca zece, sau egal cu zece, continuăm cu ramura din stînga.
testează dacă valoarea lui x este mai mare sau egală cu valoarea lui y plus 3. În acest caz continuăm pe ramura din dreapta. Dacă nu, continuăm pe ramura din stînga.

Ne vom face o idee mai bună despre blocurile de decizie atunci cînd vom scrie prima noastră schemă logică.

Bloc terminator

Nici nu aș denumi acest simbol un bloc propriu, probabil că ne-am putea descurca fără el foarte bine. Singurul lui rol este să specifice unde începe algoritmul și unde se termină. Iată cele doua blocuri pe care le vom folosi:

este locul unde începe schema logică.
este locul unde se termină schema logică.

Exemplu: distanța pînă la Stormwind

Orașul Stormwind se află pe autostrada A1 la kilometrul 60. Se știe că noi ne aflăm pe autostradă la kilometrul k (k citit). La ce distanță de Stormwind ne aflăm? Să construim o schemă logică care o calculează (vezi figura din dreapta).

Pentru a executa o schemă logică pornim de la blocul de START si urmăm săgețile. Primul pas este să citim k, kilometrul la care ne aflăm pe autostradă. Apoi vom testa dacă am depășit Stormwind, adică dacă am trecut de kilometrul 60. Dacă k este mai mare decît 60 o vom lua pe ramura din dreapta, numită și ramura DA, unde vom calcula distanța d ca fiind valoarea k - 60. Dacă k este mai mic sau egal cu 60 vom urma ramura din stînga (ramura NU) unde vom calcula distanța ca fiind 60 - k. Indiferent ce ramură am urmat vom ajunge în final la conectorul cerculeț. În acest moment d conține valoarea corectă a distanței. Tot ce mai avem de făcut este să o afișăm, după care ne oprim la blocul STOP.

Am vorbit despre variabile. Asemănătoare cu cele de la matematică, dar la informatică ele își pot schimba valoarea. Analogie cu sertare pe care avem etichete cu numele variabilelor.

Exemplu: cifrele unui număr

Se dă un număr n între zero și 999 inclusiv. Să se afișeze cifrele lui în ordine inversă. Soluție: avem trei cazuri posibile. Numărul poate să aibă o cifră, două cifre sau trei. Cum testăm dacă un număr are o cifră? Un număr are o cifră dacă este mai mic decît 10. Cum testăm dacă un număr are două cifre? Un număr are două cifre dacă este între 10 și 99. Similar, el are trei cifre dacă este între 100 și 999. Algoritmul nostru va testa în care din cele trei cazuri se încadrează numărul citit n, apoi va calcula și afișa cifrele componente în ordine inversă. Iată schema logică bazată pe această idee:

Afișare cifre număr în ordine inversă (0 ≤ n ≤ 999)

Tema

Scrieți temele pe foi, nu în caiete! Data viitoare îmi veți aduce tema pe aceste foi, pe care le voi lua acasă pentru a le corecta. Vă voi returna tema corectată. Nu uitați să semnați aceste foi! Gîndiți-vă singuri la răspunsuri, apoi, dacă nu găsiți rezolvarea căutați pe google și abia apoi, dacă nu reușiți, întrebați părinții sau prietenii. Mă bazez pe codul onoarei.

Din ce sînt făcute stafidele?
De ce este cald vara și frig iarna? (cu mențiunea că răspunsul de la geografie din școală se predă greșit, de multe ori)
Ce număr trebuie completat în ultima figură:

Schemă logică: ecuația de gradul 1: se dau a și b astfel încît a * x = b. Să se determine x pe baza valorilor a și b. Am discutat cele trei cazuri:
- cînd a este diferit de zero x este b : a.
- cînd a este zero și b este diferit de zero x nu există.
- cînd a este zero și b este zero x poate avea orice valoare.

Rezolvări aici [1]

Clasa a V-a lecția 1 - 3 sep 2013

Contents