Note de curs, clasele 9-10, 28 septembrie 2012

From Algopedia
Jump to navigationJump to search

Scopul pentru prima întâlnire a fost să-mi fac o idee despre nivelul la care urmează să predau. Am dat șase problemuțe de logică și de implementare și un chestionar de auto-evaluare. În jumătatea de oră rămasă am discutat despre rezolvări.

Chestionar introductiv

Probleme de matematică și de logică

  • Doi prieteni ies la restaurant și doresc să arunce cu o monedă pentru a decide cine plătește consumația. Totuși, ei bănuiesc că moneda nu este corectă, ci stema are o probabilitate p > 1/2. Cum pot ei folosi această monedă pentru a garanta un rezultat echitabil (probabilitate 1/2 pentru ambii prieteni)?
  • Invers, doi prieteni au la dispoziție o monedă corectă (probabilitate 1/2 pentru ambele fețe). Ei doresc să joace un joc unde primul jucător are șansa p să câștige, unde 0 < p < 1. Cum procedează?
  • Un alpinist dorește să coboare o prăpastie verticală de 200 m. La jumătatea prăpastiei există o mică treaptă pe care poate sta, dar în rest peretele este perfect neted. Alpinistul are 150 m de sfoară, cuțit, pitoane și ciocan. Cum procedează?

Probleme de implementare

  • Calculați cât mai eficient pentru a și n numere naturale. Ignorați dimensiunea unui întreg, necesarul de stocare etc.
putere(a, n) {
  // Codul vostru aici
}
  • Implementați o coadă (structură de date de tip FIFO) folosind două stive (structuri de date de tip LIFO). Aveți voie să declarați numai două obiecte s1 și s2 care permit operațiile:
operație efect
s1.init() creează o stivă nouă, goală.
s1.push(x) adaugă elementul x la vârful stivei.
s1.pop() extrage ultimul element de la vârful stivei și îl returnează. Dă eroare dacă stiva este goală.
s1.empty() returnează true dacă stiva este goală, false altfel.

Implementați funcțiile de mai jos și calculați complexitatea fiecăreia.

var s1, s2;

init() {
  // Creează o coadă nouă, goală
}

enqueue(x) {
  // Adaugă elementul x la sfârșitul cozii
}

dequeue() {
  // Extrage elementul de la începutul cozii și îl returnează.
  // Poate face orice când coada este goală.
}

empty() {
  // Returnează true dacă coada este goală, false altfel.
}
  • Implementați un vector de 1.000.000 de valori booleene folosind 125.000 de octeți de memorie. Puteți presupune că tipul de date unsigned int are 32 de biți. Scrieți codul pentru funcțiile get(i) și set(i, b), care citesc valoarea celei de-a i-a variabile, respectiv îi schimbă valoarea în b (0 sau 1).

Chestionar

Vă considerați capabili să implementați, în timp de concurs, următorii algoritmi și structuri de date:

(Includ aici și răspunsurile lor, da, nu și altceva. Altceva a însemnat, în general, că știu ceva-ceva despre subiect).

algoritmul da nu altceva
Un algoritm de sortare în O(n2) 11 2 0
Un algoritm de sortare în O(n log n) 11 2 0
Descompunere în factori primi 12 1 0
Operații pe numere mari (adunare, scădere, înmulțire, împărțire) 11 2 0
Căutări în șiruri de caractere (KMP sau altceva eficient) 6 2 5
Generarea permutărilor, combinărilor, submulțimilor unei mulțimi 10 2 1
Parcurgere de graf (matrice de adiacență) 7 4 2
Parcurgere de graf (liste de adiacență) 3 8 3
Parcurgere de arbore (în adâncime) 4 6 3
Parcurgere de arbore (în lățime) 2 8 3
Arborele de cost minim (Kruskal, Prim sau alt algoritm) 1 9 3
Componentele tare conexe ale unui graf 2 7 4
Sortare topologică 2 6 5
Drumurile cele mai scurte de la un nod la toate celelalte 2 8 3
Drumurile cele mai scurte între oricare două noduri 2 8 3
Cuplaj într-un graf bipartit 0 9 4
Flux maxim 0 9 4
Flux maxim de cost minim 0 8 5
Programare dinamică (cel mai lung subșir crescător, distanța între două șiruri de caractere, problema rucsacului etc.) 7 2 4
Liste înlănțuite (cu pointeri) 3 8 2
Heaps 4 7 2
Tabele hash 0 11 2
Arbori de căutare 2 9 2
Structuri de mulțimi disjuncte (union-find) 1 10 2