Difference between revisions of "Clasa a V-a lecția 1 - 13 sep 2019"

From Algopedia
Jump to: navigation, search
(Created page with "= Introducere = == Prezentarea instructorilor == Numele meu este Mihai Tuțu și vă voi ghida în acest an în cadrul cercului de informatică IQ Academy. Contacte: * email...")
(No difference)

Revision as of 16:49, 10 September 2019

Introducere

Prezentarea instructorilor

Numele meu este Mihai Tuțu și vă voi ghida în acest an în cadrul cercului de informatică IQ Academy. Contacte:

  • email Mihai: mihaitutu7@gmail.com
  • telefon Mihai

Mihai Tuțu

  • Un pasionat de tehnologie, programare și gaming. Mai ales gaming :).
  • Colegiul Național „Mihai Viteazul” București, clasă de intensiv engleză.
  • Facultatea de Construcții Civile, Industriale și Agricole, UTCB și Facultatea de Informatică, Universitatea București și Universitatea „Titu Maiorescu”.
  • Activist în cadrul Fundației Leaders, unde am ajutat peste 3000 de tineri în cadrul programelor educaționale, în calitate de instructor, 2013 - 2016.
  • Programator web și desktop în cadrul mai multor companii, 2016 - 2018.
  • Profesor de robotică cu multiple participări la concursuri internaționale.

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.

Studiați informatică în cadrul orelor de la școală. 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, engleză, înot sau baschet. 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: sunteţi la o instituție de vârf, la cercul de informatică (peste nivelul orelor de clasă), unde predă un profesor de vârf. Aştept totul de la voi, altfel nu veţi reuşi să ţineţi pasul.

Scopul cercului de informatică

Informatica ca știință este foarte la început, la nivelul la care erau matematica și fizica în evul mediu. În informatică încă așteptăm un Newton care să o structureze și să o închege. Pentru ca aceasta să se întâmple, ea ar trebui predată din clasa a doua, imediat ce copiii învață primele noțiuni de matematică. Mintea copilului trebuie abstractizată pentru a învăța bine informatică (precum spunea și Moisil), ceea ce este bine să facem cât mai de mici.

Chiar și atunci când informatica este predată în școli, în clasele 5-8, ea are tendința de a fi predată dezlânat, haotic, de multe ori punând accentul pe utilizarea calculatorului și nu pe programare. Atunci când se predă programare, de multe ori se pune accentul pe limbaj și mai puțin pe algoritmi. Este ca și cum i-am explica unui copil în detaliu ce conține un microscop, lentile, măsuța microscopului, carcasa metalică, etc, iar apoi i l-am da copilului să-l folosească. N-ar trebui să rămînem surprinși dacă elevul va bate cuie cu el; pentru că nu l-am învățat să răzuiască un strat subțire de celule, să-l așeze pe lamelă, să adauge colorant, apoi să se uite prin lentile și să rotească pînă ce imaginea se clarifică.

Scopul acestui cerc este formarea unor minți algoritmice, cu putere de abstractizare. Olimpiada și alte concursuri sunt un corolar, nu un scop, dar sînt evaluatoare necesare, deci le vom acorda o atenție deosebită. La fel și limbajul C, el nu este un scop, ci un corolar. Scopul principal sînt algoritmii, iar limbajul C este modul în care îi putem implementa și testa.

Conduită

Elevul care vine la acest cerc este cel care a epuizat materia de la clasă și vrea să învețe mai mult. Pun accentul pe cuvântul vrea. Există în București școli foarte bune la care pregătirea la orele de informatică este pe măsură de bună. Nu aveți nevoie să veniți la acest cerc pentru a învăța informatică. Veniți aici pentru aprofundare și pentru lucruri în plus. Dacă nu vă doriți acest lucru nu are rost să veniți, veți pierde timpul, pe al vostru, pe al colegilor voștri și pe al meu. Iată o listă incompletă de motive incorecte de a veni la cerc:

  • Ne predă unul tare de la Google. Credeți că ăla tare de la Google a venit să-și piardă vremea cu cei care nu vor să învețe ci să obțină autografe?
  • M-a pus mama/tata/fratele/sora. Nu cred că este așa. Nu vă obligă nimeni. Familia vă dorește binele și vă arată cercul nostru, dar nu vă și obligă. În acest caz le puteți spune nu, dacă nu doriți cercul.
  • Mulți colegi de clasă sînt la cerc. Și mai mulți colegi nu sînt la cerc, nu este un motiv.
  • Colega pe care o iubesc în secret merge la acest cerc. Un motiv aproape valid. Dar foarte distructiv, invitați-o vă rog în parc, sau la cofetărie la un suc, sau să-i arătați ultima aplicație de Android.

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.

Despre situația clasei a cincea

În trecut informatica a fost materie opțională la gimnaziu. Puține școli o predau, fiecare avînd programa proprie. Olimpiada de informatică are o programă scrisă, inutilă, deoarece menționează generalități. Profesorii ce făceau pregătire pentru olimpiadă trebuiau să își formeze propria programă bazată pe istoricul problemelor date la concurs. Acest lucru l-am făcut și eu.

De câțiva ani, informatica a devenit obligatorie în toate școlile la clasa a Va. Avem, deci, o programă unitară. Acesta este un lucru bun, deoarece mai mulți elevi vor învăța această materie. Dar, ca orice început, există și probleme: timpul alocat este de o oră pe săptămînă, iar jumate din el este alocat pentru TIC, ceea ce duce la o jumate de oră de informatică pe săptămînă, timp prea scurt pentru a acoperi programa de olimpiadă. În consecință, programa de școală este mult sub nivelul programei olimpiadei.

Nivelul acestui cerc va fi același ca la cercul pe care l-am susținut la Vianu, adică undeva peste nivelul olimpiadei de anul trecut, întrucît noi creăm informaticieni, nu olimpici. În caz că programa de olimpiadă se modifică veți fi supracalificați și, poate, o idee dezavantajați, deoarece programa școlară nu include limbajul C, ci Scratch, un limbaj vizual dezvoltat la MIT, despre care înșiși creatorii spun că este recomandat la opt ani. Oare aceasta este vârsta elevilor de clasa a cincea?

De ce începem în ritm accelerat?

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, cea veche, 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 6a la greutatea problemelor". Aceasta ar explica faptul că în 2014 la clasa a 5a 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 6a. 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 curs.

Al treilea motiv pentru care începem atât de repede este unul organizatoric: nu pot lucra cu 60 de elevi. O soluţie ar fi 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 patru 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 patru 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

Deoarece numărul elevilor doritori să participe la cerc este mare vom da un test de selecție, în urma căruia vom forma două grupe a cîte 15 elevi. Formăm două grupe deoarece unii elevi învață dimineața, iar alții după amiază.

La acest nivel de performanţă îmi este imposibil să lucrez cu 40 de elevi. În fapt, numărul ideal este de 8-10 elevi. O grupă de 15 elevi reprezintă un efort foarte mare din partea mea, pe care îl fac pentru voi, copiii.

Ce se întîmplă cu elevii care nu se vor califica la curs? După cum spuneam, voi mai forma o grupă sâmbătă dimineața pentru aceștia, în care voi face o materie mai de bază, în pregătirea materiei pentru anul următor. Regulile acestei grupe sunt aceleași, diferă doar materia de curs.

Atenție, cei ce nu dau dovadă de seriozitate nu vor putea continua, locurile lor fiind date altor elevi, ce nu au fost selecționați, dar au continuat să lucreze singuri.

Materia: ce vom învăța?

La acest cerc nu vom învăța doar informatică! O gîndire algoritmică necesită mai multe elemente: matematică, psihologie, sport, joacă, gîndire abstractă (probleme de logică). În cadrul acestui cerc voi încerca să ating toate aceste puncte.

Ca informatică vom încerca să atingem următoarele subiecte, de-a lungul a patru ani, unele mai în detaliu, altele tangențial, cu mențiunea că aceasta este doar o listă orientativă:

Nivel 1 (avansat)

  • probleme de logică (dezvoltarea gîndirii abstracte)
  • algoritmi, definiție, proprietăți
  • scheme logice, programare structurată
  • probleme cu structuri alternative
  • probleme cu structuri repetitive
  • definitii de bază: variabilă, contor, acumulator, steguleț, sentinelă
  • analiza algoritmilor (timp de execuție și memorie ocupată)
  • despre organizarea calculatorului (procesor, memorie, periferice)
  • despre limbaje (mașină, asamblare, nivel înalt)
  • limbajul C
  • algoritmi fără șiruri
  • algoritmi cu șiruri (dar fără vectori)
  • algoritmi cu vectori (tablouri unidimensionale)
  • algoritmi cu matrice (tablouri bidimensionale)
  • matematică aplicată, "cărămizi" de bază (divizibilitate, primalitate, baze de numerație)
  • aplicații ale matematicii in informatică: ecuația de gradul întîi și doi, calcule cu polinoame, calcule cu fracții, codul Gray, operații pe mulțimi, cmmdc/cmmmc, fibonacci, combinatorică
  • căutare (căutare liniară, căutare binară, KMP, căutare cu funcții hash, arbori de căutare)
  • sortare (bubble sort, select sort, merge sort, sortare cu arbori de căutare, quicksort, radix sort, heapsort)
  • baze ale geometriei analitice (sistemul cartezian, distanța euclidiană, distanța manhattan, segmente, arii)
  • elemente de grafică pe calculator
  • pregatire pentru concurs (psihologie, ce să facem și să nu facem, reguli)
  • jocuri: tip puzzle, gen cubul rubik, turnurile din hanoi, nim, etc, precum și anumite jocuri pe calculator gen sokoban, lines, etc

Nivel 2 (liceu, posibil clasa a 8a)

  • structuri de date (vectori, heaps, liste, arbori, grafuri, functii hash si tabele hash)
  • arbori (reprezentari, parcurgeri, arbori binari, arbori binari de cautare, codul lui Pruffer)
  • grafuri (reprezentari, parcurgeri, arbore minim de acoperire, distanta minima, sortare topologica, drum/ciclu eulerian, drum/ciclu hamiltonian, cuplaj)
  • recursivitate
  • tehnici de programare (greedy, divide et impera, backtracking, programare dinamica)
  • bazele compilarii (analiza lexicala, analiza sintactica, automate finite)
  • compresie (huffman, shannon-fano, lzw, lz)
  • grafica (trasare linie, cerc, fillpoly, grafica 3D)
  • elemente de inteligenta artificiala (algoritmul alfa-beta)
  • analiza algoritmilor, NP completitudine, probleme de lower si upper bound

Materiale de studiu

În acest moment, materia informatică este într-o stare de tranziție. Pînă anul acesta informatica la nivel de gimnaziu era opțională. Acest lucru înseamna că nu exista o programă de studiu uniformă, pentru toate școlile, aprobată de ministerul învățămîntului. Fiecare școală care dorește să predea informatică își alcătuiește propria programă și o supune aprobării ministerului.

În aceste condiții viața celor care scriu manuale de informatică pentru clasele V-VIII este foarte complicată. Sper să nu supăr pe nimeni afirmînd că la acest moment nu există nici un manual care să corespundă nivelului extra-olimpiadă, nivelul pe care îl dorim la acest cerc. Există unele culegeri de probleme destul de bune, dar care sînt gîndite pentru începători la nivel de liceu, de aceea nu le voi recomanda aici.

Aceste motive m-au determinat să adun materiale de studiu în cadrul acestui site. Desigur că este o listă incompletă.

Iată, deci, recomandările, firave, de materiale de studiu:

  • Biblia informaticii, către care trebuie să tindă o minte algoritmică și cartea de bază în teoria calculatoarelor este Indroduction to Algorithms de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (porecla oficială a acestei cărți, după autori, este CLR). A fost tradusă și în română; nu este clar unde poate fi cumpărată, în afară de anticariate și pe okazii.ro; acesta este site-ul editurii care pare să o comercializeze. Atenție! Este o carte la nivel de anul doi de facultate! Deși tot ceea ce vom face la cerc este prezent în această carte, modul de abordare la ore va fi foarte diferit, fiind transformat pentru înțelegerea la nivel de gimnaziu. Cu toate acestea este o carte care trebuie să existe în casa oricărui informatician și pe care o vom consulta de-a lungul anilor.
  • Web-ul este prietenul vostru pentru subiecte specifice, voi încerca să dau referințe bibliografice pe parcurs
  • Ca surse de probleme:
  • Acest site, desigur :)

Altele

  • Lecțiile vor fi pe algopedia.ro, nu scrieți lecția în caiet, nu are rost, la clasa a cincea scrieți prea încet față de cantitatea de cunoștinte predate. Notați numai lucrurile interesante.
  • 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.

Exemple probleme auxiliare

Iată niște exemple de probleme complementare, nu de informatică, ce susțin o minte computațională. Vom rezolva și astfel de probleme:

  • Jocuri ce 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?