Reguli ale cercului de informatică

From Algopedia
Jump to: navigation, search

Reguli generale

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ă, 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 sînt 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. Liceul Vianu este unul din cele mai bune licee din țară în acest domeniu, iar pregătirea la orele de informatică este pe măsură. 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.

Reguli în legătură cu conținutul acestui cerc

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, 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 (foarte avansat)

  • 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

La ora cînd scriu aceste rînduri (septembrie 2013), materia informatică la nivel de gimnaziu este opțională. Acest lucru înseamnă că nu există o programă de studiu uniformă, pentru toate școlile, aprobată de ministerul educației. Fiecare școală care dorește să predea informatică își alcătuiește propria programă și o supune aprobării ministerului. Aceasta este și situația claselor de gimnaziu din cadrul liceului de informatică Tudor Vianu.

Î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. Ele vor fi recomandate la ore.

Aceste motive m-au determinat să adun materiale de studiu în cadrul acestui site. Desigur că nu este un site complet, ci, ca toate celelalte materiale se vrea un ajutor, un complement pentru elevii de gimnaziu. Sper ca el să devină în timp din ce în ce mai complet, un adevărat manual în toată puterea cuvîntului. De asemenea, sper ca el să evolueze odată cu evoluția cerințelor.

Acestea fiind spuse, iată 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 :)

Limbajul C

La cercul de informatică vom folosi limbajul C. Aceasta înseamnă că programele noastre trebuie să fie denumite ".c" și trebuie sa fie compilabile cu un compilator de C. Amestecul de elemente C++ nu este permis, făcînd automat programul necompilabil. Ce înseamnă asta, concret? Înseamnă următoarele:

  • Trebuie să cunoașteți limbajul, ce este corect în C și ce nu este C, ci C++
  • Trebuie să cunoașteți instrucțiunile de intrare/ieșire C, mai ales cele legate de fișiere. Găsiți aici un mic manual de utilizare: Instrucțiuni de intrare/ieșire în limbajul C.

De ce nu avem voie să amestecăm C cu C++, așa cum unii dintre noi facem de ceva vreme? Din următoarele motive:

  • Cunoștințe despre limbaj. Majoritatea dintre noi programăm într-o struțo-cămilă, nici C, nici C++. Dacă ni se cere să scriem un program în C nu putem, deoarece nu știm fscanf și fprintf, ci insistăm în a folosi cin și cout, iar dacă ni se cere să scriem un program în C++ iarăși nu știm, deoarece un program C++ este obiectual și nu funcțional. Cîtă vreme nu definim clase în programele noastre și nu instanțiem obiecte nu putem spune că programăm în limbajul C++. Astfel, dacă nu sîntem capabili să scriem un program nici în C, nici în C++, rezultă că de fapt nu știm nici un limbaj.
  • Arta programării. Programarea este o știință dar și o artă, iar limbajele de programare sînt limbaje, artificiale, dar limbaje. Așa cum în viața de zi cu zi nu amestecăm româna cu engleza atunci cînd vorbim, la fel nu facem asta nici nu limbajele artificiale. Deși nu ne împiedică nimeni, nu este frumos, deoarece limba română nu este doar un mod de comunicare ci este și o artă în același timp, precum și oglinda a ceea ce sîntem noi ca persoane. Așa cum spunea marele lingvist Noam Chomsky, tatăl lingvisticii moderne, sîntem una cu limbajul pe care îl folosim, el definind ceea ce putem gîndi.
  • Învățarea dincolo de olimpiadă. Scopul acestui cerc este să învățăm informatică și algoritmi și nu să ajungem la faza pe țară a olimpiadei de informatică. Informatica înseamnă cu mult mai mult decît olimpiada. Nu uitați: olimpiada nu este un scop în sine, ea este doar un concurs anual de testare a cunoștințelor. A face din olimpiadă un scop înseamnă a avea ochelari de cal și a nu înțelege rostul școlii în general. Aud uneori argumentul "scriem cu cin și cout deoarece cîștigăm timp la olimpiadă". Acesta este un argument fals. Lenea este adevăratul motiv, e mai simplu așa. Chiar dacă ar fi adevărat, noi nu învățăm pentru olimpiadă. Consideri că fprintf și fscanf îți consumă timpul la olimpiadă? Atunci învață-le și apoi învață extra și cin/cout! Nu uita, informatica nu înseamnă olimpiadă. Dacă olimpiada este tot ceea ce vrei să înveți, atunci poate locul tău nu este la acest cerc.

Și totuși, eu știu C++!

Serios? Atunci înseamnă că nu vei avea nici o problemă să spui ce face programul C++ de mai jos. Fii corect, nu trișa tastînd programul și executîndu-l. Scopul acestui test este să afli dacă știi C++, așa cum crezi. Programul este unul foarte simplu pentru cineva care știe sintaxa C++, deci nu ar trebui să ai probleme.

Ce face acest program?

Reguli de programare în limbajul C

Această secțiune este un schelet. Mai multe detalii în curînd.

  • Variabilele simple nu se inițializează la declarare. Ele se inițializează cît mai aproape de secțiunea de program care le folosește. Cu alte cuvinte orice variabilă se inițializează cît mai jos posibil. De ce? Pentru citibilitatea codului. Imaginați-vă că la linia 300 vedem o instrucțiune a = a + y;. Ne punem întrebarea cu ce valoare a fost inițializată a. Imaginați-vă că trebuie să mergem cîteva pagini în sus pentru a constata că variabila a fost inițializată la declarare int a = 1;
  • Vectorii încep de la 0, nu de la 1. Este o regulă importantă, nu o preferință personală. Avantaje: cînd folosim modulo, vectori caracteristici, etc.
  • Vectorii au dimensiunile specificate de cerinţă. Ei nu se declară int v[10010]. Aceasta se cheamă programare aproximativă şi nu este o practică acceptată în unul din locurile de top din ţară. Dacă la matematică vi s-ar cere să rezolvaţi ecuaţia 2 · x = 5 şi aţi răspunde că x este un număr între doi şi trei nu cred că aţi putea fi consideraţi cei mai mari matematicieni ai ţării. Programarea aproximativă reprezintă lenea minţii. Să punem cîteva elemente în plus, în caz că depăşesc vectorul. Cine depăşeşte vectorul? Zîna memoriei? Nu, voi. Soluţia corectă este să vă corectaţi gîndirea şi să vă ascuţiţi mintea pentru ca algoritmul vostru să nu depăşească vectorul. Altfel veţi rămîne incapabili de a scrie programe în lumea reală unde aproximarea nu e acceptabilă.
  • Reguli de indentare, exemple:
    • Indentarea se face la două sau la patru spații. Două sînt suficiente pentru citibilitate. Atenție: setați code::blocks să nu folosească caractere TAB.
    • Acolada deschisă se pune pe același rînd cu instrucțiunea precedentă.
    • Acolada închisă se pune pe rîndul următor aliniată sub instrucțiunea de care aparține.
    • Dacă după else urmează un if atunci if-ul se pune imediat după else pe aceeași linie, iar corpul de instrucțiuni aparținînd lui else se indentează cu două spații, nu cu patru. Astfel, în cazul unor instrucțiuni de genul if ... else if ... else if ... se evită migrarea codului către dreapta prin indentări inutile.
  • Fără break/continue/return/goto în interiorul buclelor. Ele distrug programarea structurată și, implicit, zeci de ani de experiență ai omenirii.
  • Folosim for pentru bucle cu număr cunoscut de pași, while în celelalte cazuri. Aceasta este o regulă de programare ordonată, care face codul mai citibil.
  • Nu avem voie să modificăm variabila de buclă for. Dacă este un ciclu cu număr cunoscut de pași nu avem de ce să modificăm variabila.
  • Cînd eliminăm un element din vector scădem lungimea lui (n--). În felul acesta n continuă să arate numărul de elemente din vector.
  • Nu aveți voie să aveți warnings, vă pot fi fatale: declaraţi int main() si folosiţi return 0 la final. Eliminați orice alte warnings deoarece majoritatea sînt o problemă reală. Unele concursuri compilează sursa cu opriri la warnings (adică tratează warning-urile ca erori). Unele warnings se referă la variabile neinițializate sau la număr diferit de "%d" versus variabile citite, in fscanf, deci sînt importante. Este obligatoriu să setaţi Code::Blocks să vă afişeze toate warnings. Pentru aceasta, după crearea proiectului, navigaţi în meniul Project, submeniul Options. În acea fereastră setaţi opţiunile -Wall şi -O2.
  • Comentați codul cînd e ceva complicat, de exemplu o formulă. Scrieți ideea algoritmului, dacă nu e ceva trivial. Nu trebuie să umpleți de comentarii, dar minimal. Mă ajutați mult în corectarea temei.
  • Denumiți variabilele mai clar. Nu lungi, dar să aibă semnificație: prod, sum, nrcf, etc.
  • Nu abuzați stegulețele. Exemplu unde nu sînt necesare break sau stegulețe: căutarea unui element e în vectorul v:
    i = 0;
    while ( (i < n) && (v[i] != e) )
      i++;
  • Folosiți corect fișiere, le deschideți cu fopen, iar la final obligatoriu le închideți cu fclose. În nici un caz nu folosiți freopen.
  • Nu folosiți funcții gen sort și qsort. Aveți nevoie de dispensă specială ☺