Introducere

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.ro. În acest fel vom avea 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.

Felicitări, aţi devenit elevi la unul din cele mai bune licee de informatică din ţară. Materia pe care o veţi face la ore va fi la un nivel foarte ridicat, nivel suficient pentru un elev foarte bun la învăţătură, nivel suficient pentru olimpiadă. Dacă veniţi la acest cerc înseamnă că vreţi să studiaţi mai mult, dincolo de olimpiadă: informatică la cel mai înalt nivel posibil la vîrsta voastră. Aceasta înseamnă un efort deosebit de mare. Nu oricine poate acest lucru. S-ar putea să fiţi nevoiţi să faceţi sacrificii pentru a putea face faţă, cum ar fi să renunţaţi la orele de pian, sau de engleză. Dacă vă aşteptaţi că acest cerc este doar una din activităţile voastre de autodezvoltare veţi avea surpriza că vă înşelaţi. Pe scurt: sînteţi la un liceu de vîrf, la cercul de informatică (peste nivelul orelor), unde predă un profesor de vîrf. Aştept totul de la voi, altfel nu veţi reuşi să ţineţi pasul.

De ce începem mai devreme?

La clasa a cincea pornim de la zero; în cîţeva luni trebuie să învăţăm ce este acela un calculator, algoritmi, scheme logice, limbajul C. Este o cantitate mare de informaţie şi un salt calitativ mare. Acesta este un motiv.

Al doilea motiv este că programa de olimpiadă de clasa a cincea este cea mai încărcată programă din anii de gimnaziu. Este, probabil, dublă ca nivel de cunoştinţe acumulate faţă de oricare din celelalte clase. Nu ştiu motivul pentru care comisia de olimpiadă insistă să dea probleme foarte grele la clasa a cincea. Poate că mottoul lor este "hai să depășim clasa a 6^a la greutatea problemelor". Aceasta ar explica faptul că anul trecut la clasa a 5^a s-a dat problema iepurași, problemă NP-hard, de cercetare mondială, pentru care omenirea nu cunoaște o rezolvare bună.

Dacă aş putea, aş preda această materie în ritm mai lent, lăsînd o parte pentru clasa a 6^a. Aceasta ar însemna rezultate mai slabe la olimpiadă. Din nefericire atît profesorii cît şi părinţii îşi doresc foarte mult aceste rezultate, aşa încît sînt pus în situaţia să aleg: fie predau în ritmul infernal impus de olimpiadă şi unii elevi vor fi nefericiţi, fie predau mai lent, dar risc să fiu perceput ca un instructor slab, fără rezultate la olimpiadă, ceea ce ar însemna implicit că anul următor nu aş mai avea elevi dornici să vină la acest cerc.

Al treilea motiv pentru care începem mai devreme este unul organizatoric: nu pot lucra cu 60 de elevi. Ca soluţie mi s-a sugerat ca la începutul anului să dau un test. Deoarece majoritatea elevilor nu ştiu încă informatică, testul ar trebui să fie la matematică. Nu am fost de acord cu această soluţie deoarece mi se pare incorectă. Am preferat să predau cinci lecţii cu toţi elevii doritori şi apoi să dau un test bazat pe materia predată. Este o soluţie imperfectă, dar cea mai bună pe care am găsit-o.

Eventualii nemulţumiţi de această soluţie aş vrea să ţineţi cont de faptul că aceste cinci lecţii reprezintă un efort uriaş. Voi corecta 50-60 de teme de două ori pe săptămînă şi le voi returna elevilor spre învăţare.

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 altcineva va prelua cealaltă grupă. Materia predată va fi aceeași, precum şi aceleaşi probleme. Voi colabora foarte îndeaproape cu acea persoană, asigurîndu-ne că ambele grupe menţin acelaşi nivel de calitate.

La acest nivel de performanţă îmi este imposibil să lucrez cu 40 de elevi. În fapt, numărul maxim este de 8-10 elevi. O grupă de 15 elevi reprezintă un efort foarte mare din partea mea, dar o voi face dacă am doritorii.

Ce se întîmplă cu elevii care nu au putut să vină la lecţiile pregătitoare pentru test, deoarece erau în vacanţă, sau poate nu au fost anunţaţi de secretariat? Vă rog să mă contactaţi şi voi decide de la caz la caz.

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ă nu 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 opțional și facultativ. Elevul de la cerc trebuie să dea dovadă de 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.

Grup de discuții

Grupul de informatică al claselor a 5^a se numește clubul gânditorilor. Înscrierea este obligatorie pentru cei ce vin la cercul de informatică și opțională pentru ceilalți. Se pot înscrie şi părinţii. Atenţie: este modul prin care pot face anunţuri urgente. Instrucțiuni de înscriere aici.

Exemple probleme auxiliare

Exemple de jocuri care stimulează mintea: cubul rubik, scrabble flash, powerball
Problemă de matematică: dacă 5 oameni construiesc 6 case în 300 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?

Lecție

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.

Citiţi secţiunea reguli ale cercului de informatică pe acest site.
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 - 2 sep 2014

Contents