Pe data de 9 ianuarie 2011, incepand cu ora 12:00, are loc UBBots 2011 - Ziua Robotilor Inteligenti la Universitatea Babes-Bolyai, Cluj-Napoca. Evenimentul are loc la adresa: Cladirea Campus FSEGA, parter, str. Teodor Mihali 58-60, Cluj-Napoca.

La expozitie participa echipe formate din studenti din anul III de la Facultatea de Matematica si Informatica. In cadrul evenimentului vor fi prezentate urmatoarele proiecte: Robot care pune gresie, Robot postas, Robot care sterge praful, Robot care culege pet-uri de pe lac, Robot care planteaza copaci, Robot care stinge incendii, Robot care traseaza linii de trafic rutier si Robot care serveste masa. Robotii implicati in aceste proiecte sunt: IRobot, Lynx Arm, Lego, Robotino si IntelliBrainBot.

Expozitia este organizata de profesorii Mihai Oltean, Laura Diosan, Ovidiu Serban si Liviu Stirb si este sprijinita de Facultatea de Matematica si Informatica a Universitatii Babes-Bolyai.

Mai multe informatii gasiti pe site-ul evenimentului.

Google Code-in este un concurs adresat elevilor cu vârste cuprinse între 13 - 18 ani, având ca scop familiarizarea participanţilor cu tipurile de contribuţii în cadrul proiectelor open source. Varietatea de task-uri propuse spre a fi rezolvate vă oferă şansa să cunoaşteţi toate modurile în care puteţi contribui în cadrul unui proiect open source şi să primiţi feedback din partea unui număr foarte mare de utilizatori şi dezvoltatori.

O descriere mult mai detaliată puteţi regăsi în aceste slide-uri. Sperăm ca printre finaliştii acestui concurs să se afle şi unii dintre voi!

Mult succes!

Folosiţi secţiunea pentru comentarii pentru eventuale întrebări sau nelămuriri.

Continuam cu o problema clasica de teoria grafurilor:

Spunem ca un graf neorientat cu n noduri ca e de tip scorpion daca are trei noduri speciale pe care le numim acul, coada si corpul. Acul are gradul 1 si este legat de coada. Coada are gradul doi si e legata de ac si de corp. Corpul are gradul n - 2 si e legat la toate nodurile din graf cu exceptia acului. Celelalte noduri pot fi conectate oricum intre ele. Se cere sa se determine in O(n) intrebari de genul "Sunt nodurile i si j vecine?" daca graful este scorpion sau nu.

Puteti trimite solutii pe adresa cosminn at gmail.com

Aceasta problema are mai multe solutii intermediare. Ea s-ar potrivi destul de bine in un concurs sau chiar in un interviu de job. A fost rezolvata de cinci cititori.

Rezolvitori:
Andrei Dragus, Cosmin Balan, Andrei Damian, Serban Andrei Stan si Sturzu Antonio-Gabriel. Au mai fost altii: Mihai Calancea, Stefan Istrate, Marius Pungaru si Tabara Mihai dar ei au o scapare in solutie.

Solutie:
Un model mental al problemei este sa ne uitam la matrice ca la un relief cu inaltimi. Putem din fiecare celula ne uitam care e celula vecina cu inaltime minima. Daca mergem la fiecare pas in celula vecina minima, la un moment dat ne vom opri intr-un minim local. Aceasta strategie gaseste destul de repede un minim local pe un relief aleator, dar exista situatii in care algoritmul poate fi fortat sa foloseasca O(n^2) pasi. Un astfel de caz e bazat pe construirea reliefului ca o spirala sau un sarpe. Pe aceiasi idee merg algoritmii de hill climbing sau steepest descent. Ei isi gasesc aplicatii in multe domenii cum ar fi machine learning sau inteligenta artificiala.

Putem imbunatati solutia curenta prin folosirea catorva intrebari pentru a scurta lantul pe care ne deplasam. Astfel putem folosi n intrebari sa aflam valorile din n celule aleatoare. Apoi pornim din celula cu inaltimea cea mai joasa. In cazul in care relieful e un lant de lungime n^2 aceasta idee ne aduce la o distanta medie de n pozitii de capatul lantului, deci vom face cam 4n pasi.

In rezolvarea unei probleme 2d ne ajuta frecvent sa rezolvam varianta ei mai simpla unidimensionala. In cazul problemei curente pentru cazul unidimensional exista o rezolvare simpla si eficienta bazata pe o idee similara cu cautarea binara.

Astfel incercam sa facem acelasi lucru in cazul bidimensional si incercam sa eliminam jumatate din problema. Pentru asta intrebam toate valorile de pe linia din mijloc a matricei. Ne uitam la elementul minim de pe linie si la cele doua elemente vecine pe verticala cu el. Daca elementul e minim local ne oprim, daca are un vecin mai mic putem elimina jumatatea opusa vecinului. Putem face asta pentru ca exista un lant descrescator ce trece prin elementul minim al liniei si vecinul lui vertical mai mic care intra in jumatatea corespunzatoare vecinului si nu mai poate iesi din ea. Un pas ne ia n + 2 intrebari. Ca sa rezolvam problema complet trebuie sa injumatatim solutia de log n ori deci numarul total de intrebari va fi n log n + 2 log n. Putem insa la fiecare pas sa alternam injumatatirea dupa linie cu cea dupa coloana si astfel pentru a trece de la o problema de dimensiune nxn la una de n/2 x n/2 vom face n + 2 + n/2 + 2 pasi. In total aceasta solutie va folosi 3/2 (n + n/2 + ...) + 4 log n = 3n + 4 log n pasi.

Solutia asta are o mica scapare de care va spuneam la inceput. Incercati sa vedeti daca o gasiti inainte sa cititi mai departe. Daca ne uitam doar la minimul de pe coloana si minimul de pe linie e mai mic atunci s-ar putea sa alegem jumatatea gresita. Ce vrem e ca la fiecare pas toate elementele de pe margine a patratului in care continuam sa fie mai mari decat un element din interiorul lui. Daca ne uitam doar la coloana exista cazuri in care nu respectam aceasta proprietate. Solutia poate fi reparata usor: la fiecare pas alegem jumatatea in care se afla minimul elementelor cercetate pana acum.

Probleme inrudite:
Daca avem un arbore binar cu n noduri. Fiecare nod are o valoare in el. Care e numarul minim de intrebari in care puteti garanta ca gasiti un minim local?

Maxim (Lot 2005) Se da un sir circular A de n elemente distincte (n <= 1000000). Se cere sa determinati un maxim local in cel mult 25 de intrebari. O intrebare ask(i, j, k) ne spune ordinea lui A[i] fata de A[j] si ordinea lui A[j] fata de A[k].

Problema "Minim local" e din paperul "Local optimization on graphs" de Llewellyn, Donna Crystal, Tovey, Craig si Trick, Michael.

Saptamana aceasta avem o problema ce vroiam sa o folosim ca problema simpla in una din zile la Olimpiada Europei Centrale de Informatica (CEOI 2009). Ea s-a dovedit a fi destul de cunoscuta fiind deja folosita in alte doua concursuri la care participasera unii dintre concurenti.

Se da o matrice A de 1000×1000 de numere intregi distincte. Putem pune intrebari de tipul "care este valoarea elementului A[x][y]". Dati un algoritm ce gaseste un minim local in aceasta matrice folosind cel mult 3100 de intrebari. Un element este minim local daca este mai mic decat cele patru elemente vecine ortogonal in matrice.

Puteti trimite solutii la adresa cosminn at gmail.com

Problema saptamanii curente a fost rezolvata de 13 cititori. Ea nu e asa dificila ca si problemele anterioare, dar e singura de vara asta care are o aplicatie practica.

Rezolvitori:

Andrei Grigorean, Radu Berinde, Andrei-Marius Teodorescu, Delia David, Andrei Dragus, Adrian Carcu, Ovidiu Gheorghioiu, Adrian Vladu, George Nachman, Laura Draghici, Paul Dan Baltescu, Mihai Feier si Mihai Calancea.

Solutie:
Notam umem sirul de U pozitii cu memoria neinitializata. Cum avem nevoie de operatii in timp constant am putea tine 1 sau 0 pe pozitia v din umem daca elementul v este in set sau nu. Din pacate memoria nu este initializata si astfel pot exista deja 0 si 1 prin sir care sa ne pacaleasca.

Pentru a scapa de problemele generate de memoria neinitializata folosim un al doilea sir, nmem, de lungime N ce il initializam pentru a verifica daca umem spune adevarul. La adaugarea unui nou element v in set, dupa ce au fost deja adaugate max elemente, il adaugam in nmem la final si pe pozitia v din umem punem valoarea max. Astfel putem testa daca un element este intradevar in set folosind conditia nmem[umem[v]] == v. Trucul e ca realizam o legatura bidirectionala care este reala pentru ca noi controlam sirul nmem.

Aveti aici niste cod in Python scris de George Nachman pe aceasta idee:

umem = newarray(U)
nmem = newarray(N)
max = 0

def contains(v):
  if v >= U:
    return False
  i = umem[v]
  if i >= max:
    return False
  return nmem[i] == v

def add(v):
  if contains(v):
    return
  umem[v] = max
  nmem[max] = v
  max += 1

Initializarea memoriei ajunge, in cazul unor algoritmi eficienti, sa incetineasca timpul total de executie. Saptamana asta incercam sa gasim o metoda ce evita aceasta problema.

Gasiti o structura de date ce reprezinta o submultime a multimii {0, 1, ... , U - 1}. Operatiile de initializare, adaugare si verificare a incluziunii trebuie sa se execute in timp constant in cazul cel mai nefavorabil (daca am cere timp constant pe cazul mediu, o solutie este sa folosim un hash table). Aveti la dispozitie o zona de memorie continua in care incap U intregi ce nu e initializata, deci contine valori oarecare. Puteti folosi memorie suplimentara O(N), unde N este numarul de intregi ce vor fi adaugati in multime.

Ca de obicei puteti trimite solutii sau propuneri de probleme pe adresa cosminn at gmail.com

Saptamana asta am avut o problema de matematica, dar care avea nevoie de cunostinte elementare.

Rezolvitori:
Dumitru Daniliuc, Andrei Dragus, Mihai Damaschin, Adrian Vladu si Andrei Marius Teodorescu.

Solutie:
Proiectam segmentele pe Ox si pe Oy. Suma lungimilor proiectiilor va fi mai mare sau egala cu 18. Asta inseamna ca cel putin una dintre cele doua sume a lungimilor proiectiilor verticale sau a lungimilor proiectiilor orizontale va fi mai mare sau egala cu 9. Presupunem fara a restrange suma aceasta este realizata pe axa Ox.

In cazul in care o suma este strict mai mare decat 9, vom avea un punct pe Ox unde au fost proiectate puncte de pe 10 sau mai multe segmente si putem astfel duce prin acel punct o dreapta paralela cu Oy ce va intersecta cel putin 10 segmente.

In cazul in care ambele sume sunt egale cu 9 si nu exista nici un punct pe o axa cu cel putin 10 puncte proiectate in el, rezulta ca avem doar segmente verticale si orizontale, iar fiecare in fiecare punct de pe axe sunt proiectate exact noua segmente paralele cu axa respectiva. Astfel, alegem orice dreapta suport a unui segment vertical si acesta va intersecta exact 9 segmente orizontale.

Daca stiti probleme interesante care s-ar potrivi la "Problema saptamanii" va rog sa mi le trimiteti pe email. Problema saptamanii ar trebui sa nu fie foarte cunoscuta, sa aiba o rezolvare ingenioasa dar care nu are multi pasi si prefer sa fie legata cat de cat cu programarea, dar poate fi si de matematica.

Continuam cu urmatoarea problema:

Patratul [0, 1] x [0, 1] contine niste segmente cu suma lungimilor egala cu 18. Sa se demonstreze ca exista o dreapta ce intersecteaza cel putin 10 din aceste segmente.

Puteti trimite solutii sau propuneri de probleme la adresa cosminn at gmail.com

Am aflat problema anul trecut de la Mihai Patrascu. Ea e pe stilul multor intrebari din interviuri de joburi de programare. Are aplicatii in multe contexte cum ar fi in baze de date unde vrem sa detectam obiecte duplicate, pentru motoare de cautare unde vrem sa detectam pagini ce se repeta in index sau la monitorizarea traficului pe retele unde se incearca detectarea de anomalii. Ea a fost abordabila, fiind solutionata de 16 cititori.

Rezolvitori:
Dumitru Daniliuc, Andrei Grigorean, Tiberiu Savin, Andrei Dragus, Alex Mosoi, Marius Pungaru, Adrian Vladu, Marius Andrei, Daniel Dumitran, Marius Dragus, Andrei Marius Teodorescu, Laura Draghici, Delia David, Adrian Airinei, Armand Rotaru si Stefan Istrate.

Solutie:
Fie x = [sqrt n]. Tinem un sir de x pozitii F[i] cu frecventele elementelor pe intervalul [i * x + 1, (i + 1) * x]. Din principiul cutiei rezulta ca un interval va avea mai mult de x elemente in el. Prin o parcurgere al sirului aflam un astfel de interval. Cu o a doua parcurgere aflam frecventele exacte ale elementelor din intervalul respectiv folosind un sir de dimensiune x. Am determinat astfel un element duplicat folosind doua parcurgeri si memorie O(sqrt(n) log n) biti.

Daca facem k parcurgeri putem folosi memorie O(n^(1/k) * log n) biti.

Probleme inrudite:

Pentru probleme pe acelasi stil cu nivel de dificultate bun pentru interviuri tehnice pentru programatori puteti citi articolul Probleme cu numere lipsa si nu numai. Doua exemple:

1. Un sir de lungime n contine numere intregi din multimea {1, 2, ..., n-1}. Folosind Principiul lui Dirichlet deducem ca cel putin un element se repeta. Gasiti un algoritm liniar care afiseaza o valoare ce se repeta, folosind memorie suplimentara constanta si nemodificand la nici un pas vreun element din sir.

2. Se dau n numere de la 1 la n. Unul din ele apare in sir de doua ori, iar restul sunt distincte. Evident ca un numar nu va aparea niciodata. Sa se dea un algoritm cat mai eficient care sa determine numarul lipsa si numarul ce apare de doua ori.

Literatura:

Problema a fost studiata recent.

Finding duplicates in a data stream, P Gopalan, J Radhakrishnan - … of the Nineteenth Annual ACM-SIAM …, 2009 Aici se arata un algoritm randomizat ce foloseste o parcurgere si O(log^3(n)) memorie.

Finding a duplicate and a missing item in a stream, J Tarui - Proceedings of the 4th international conference on …, 2007 Aici se demonstreaza ca pentru algoritmi deterministi la k parcurgeri trebuie folosita cel putin O(n^(1/(2k - 1)) spatiu, iar pentru algoritmi ce folosesc doar O(log n) spatiu e nevoie de cel putin O(log n/log log n) parcurgeri.