Anul asta Stanford va tine cursul de inteligenta artificiala si online. Puteti participa si primi la sfarsit un certificat daca ati facut temele la nivelul la care sunt facute de studentii universitatii.

Cursul e predat de Sebastian Thrun care e Google Fellow. El a coordonat echipa ce a castigat DARPA Challenge iar acum conduce la Google cateva echipe printre care pe cea care a realizat masina ce conduce autonom. De asemenea cursul mai e predat de Peter Norvig, engineering research director la Google, el a scris cartea "Artificial Intelligence: A modern approach" si a fost inainte director pe o divizie de cercetare la NASA.

Cursul va fi foarte interesant si ca nivel un elev de liceu care are interes pentru domeniu ar trebui sa il poata face. Probabil va trebui sa stie sau sa invete ceva algebra liniara, dar nu e cu mult peste nivelul notiunilor care sunt la olimpiada de info.

Va recomand cu caldura sa va inregistrati la ai-class.com Il voi lua si eu. Poate putem discuta pe forum unele cursuri.

Am urmatoarea provocare pentru voi:

In ce complexitate puteti determina al n-lea termen al sirului Fibonacci. Sirul are F0 = 0, F1 = 1 si respecta relatia de recurenta Fn+1 = Fn + Fn-1. (presupunem ca operatiile de baza ca adunarea, inmultirea etc iau timp constant pe numere de log n biti).

In caz ca sunt lurkeri pe blog scriu ideile de rezolvare pentru problemele postului anterior:

1. (Amazon) Se da un sir A de n elemente intregi. Sa se determine doi intregi din sir a, b astfel ca a + b = X. Complexitate O(n).

Parcurgem sirul element cu element si pastram in tabela de dispersie HT elementele deja parcurse. La pasul curent cand ne uitam la elementul A[i] cautam daca in HT exista elementul de valoare S - A[i].

2. (Google, Facebook) Se da un sir A de n elemente intregi. Se cere sa se determine o subsecventa a sirului care are suma elementelor egala cu X. Complexitate O(n).

Din nou parcurgem sirul dar in loc sa adaugam fiecare element, vom adauga Sum[i], suma cumulata a elementelor de la 1 la i Sum[i] = sum(A[1..i]) in structura noastra de date. Acum la fiecare element curent cautam daca exista vreun j astfel ca Sum[j] == Sum[i] - S.

3. (Microsoft, algoritmiada) Se da un arbore T de n noduri ce are costuri intregi pe muchii. Sa se determine un drum ce merge in jos in arbore care are suma costurilor muchiilor egala cu X. Complexitate O(n).

Foarte similar cu ideea din problema anterioara. Cand coboram pe o muchie adaugam in arbore valoarea drumului de la radacina pana la nodul curent, iar cand urcam o stergem.

4. (CLRS) Se da un arbore T de n noduri. Sa se determine un nod pentru care stegerea din graf genereaza componente conexe cu dimensiuni mai mici de n/2 noduri. Complexitate O(n).

Consideram un arbore cu radacina. Pornim de la frunze in sus si pt nod avem un subarbore asociat lui ce merge in jos. Dupa ce stim numarul nodurilor din fiecare subarbore determinat de fii, putem calcula numarul de noduri din subarborele determinat de nodul curent. Avand informatia asta putem calcula care nod are proprietatea din enunt. Acel nod este numit centrul arborelui.

5. Dandu-se un arbore ce are costuri intregi pentru muchii, sa se gaseasca un drum cu numar minim de muchii care are suma costurilor S. Complexitate mai buna de O(n^2).

Aplicam o solutie pe ideea divide et impera. La fiecare pas alegem centrul arborelui curent si cautam daca exista un drum ce trece prin el care sa aiba costul S. Putem face asta usor calculand costul drumurilor de la nod la restul nodurilor si folosind o tabela de dispersie. Apoi aplicam acelasi algoritm recursiv pe toti subarborii care apar dupa stergerea centrului din graf. Solutia asta va avea complexitate O(n log n).

Cam atat, nu erau prea grele nu-i asa?

Cateva probleme care apar prin cartile de algoritmica, majoritatea folosite frecvent in interviuri:

1. (Amazon) Se da un sir A de n elemente intregi. Sa se determine doi intregi din sir a, b astfel ca a + b = X. Complexitate O(n).

2. (Google, Facebook) Se da un sir A de n elemente intregi. Se cere sa se determine o subsecventa a sirului care are suma elementelor egala cu X. Complexitate O(n).

3. (Microsoft, algoritmiada) Se da un arbore T de n noduri ce are costuri intregi pe muchii. Sa se determine un drum ce merge in jos in arbore care are suma costurilor muchiilor egala cu X. Complexitate O(n).

4. (CLRS) Se da un arbore T de n noduri. Sa se determine un nod pentru care stegerea din graf genereaza componente conexe cu dimensiuni mai mici de n/2 noduri. Complexitate O(n).

Problema Race de la olimpiada internationala de informatica de anul asta are urmatoarea cerinta:

Dandu-se un arbore ce are costuri intregi pentru muchii, sa se gaseasca un drum cu numar minim de muchii care are suma costurilor S. Complexitate mai buna de O(n^2).

Rezolvarea problemei consta in combinarea ideilor celor patru probleme de mai sus. Romanii au luat 100, 21 si 43 de puncte pe ea in concurs.
Mai trebuie sa se antreneze un pic pentru Silicon Valley, dar nu sunt departe :).

Voi cate din cele 5 le stiti rezolva?

Din cand in cand intre programatori apare discutia despre utilitatea algoritmicii. Parerile se impart pe liniile celor ce au fost la olimpiada care sustin sus si tare ca sunt foarte importanti si cei ce nu au fost care se descurca foarte bine fara ei.

Vreau sa scriu doua, trei posturi scurte cu exemple de aplicatii algoritmice in industrie daca postul trezeste destul interes.

Care dintre urmatoarele subiecte vreti sa le discutam? Puteti sugera si altele.

1. job search (balaur.ro)
2. file diff tool (infoarena, ubuntu)
3. url spell correction (google search)
4. string segmenter (google search)
5. translation (google translate)
6. reservation based ad serving (google ads, youtube, facebook)
7. reservation based inventory management (google ads)
8. reverse geo coding (google maps)
9. nearby points of interest (google maps)
10. path finding (google maps)
11. airplane ticket pricing
12. recommender systems (online dating match.com, movies netflix.com, products amazon.com)

Infoarena a adoptat modelul internship-urilor (stagii de pregătire de scurtă durată) folosit la scală largă de marile companii de IT. La infoarena, un internship reprezintă o perioadă de timp de aproximativ 3 luni în care unui utilizator i se oferă oportunitatea de a lucra mai îndeaproape cu echipa infoarena, cu scopul de a-l familiariza cu atmosfera din cadrul echipei. În această perioadă, utilizatorul dispune de drepturi şi responsabilităţi suplimentare, precum şi de un mentor din echipă ce are rolul de a-l ajuta să se acomodeze cu activităţile obişnuite ale unui administrator. Mentorii trebuie să se asigure că activităţile desfăşurate de internii aflaţi în responsabilitatea lor coincid cu interesele acestora (development, propus probleme, studiat algoritmi şi scris articole, etc.).

De ce să devii intern infoarena?

Munca ta ca intern infoarena va avea impact asupra mii de utilizatori. Este grozav să ajuţi tineri cu aceleaşi aspiraţii şi interese ca şi tine!

De asemenea, prin intermediul unui astfel de internship, conducerea infoarena va strânge suficiente informaţii despre tine pentru a decide dacă eşti pregătit să te alături echipei. Aşadar, în funcţie de evoluţia ta pe parcursul acestor 3 luni de pregătire, poţi fi apoi invitat în echipă ca membru cu drepturi depline! Trebuie ştiut că există si alte criterii care stau la baza primirii acestei invitaţii (cum ar fi de exemplu vârsta şi realizările personale, nu neapărat legate de concursurile de programare), însă celor interesaţi să ni se alăture, un internship le va spori considerabil şansele de reuşită!

În plus, internship-ul va fi o activitate voluntară care va da bine în CV-ul tău. Astfel de activităţi sunt foarte importante dacă doreşti să aplici la facultăţi sau programe de studiu în străinătate. Echipa infoarena te poate ajuta cu diplome sau recomandări dacă crezi că îţi sunt de folos.

Cum poţi deveni intern infoarena?

În primul rând, trebuie să te faci remarcat în comunitate. Ajută pe forum utilizatori mai puţin experimentaţi ca tine în mod regulat şi implică-te în proiectele de voluntariat aflate în desfăşurare. Un lucru de remarcat este că nu toate aceste proiecte au aceeaşi prioritate pentru noi. De exemplu, am aprecia mai tare dacă te-ai oferi să lucrezi în cadrul unor proiecte precum Development, Arhiva educaţională sau Scrie articole, dar până la urmă orice efort este binevenit.

Următorul pas este ne anunţi că eşti interesat de un internship. Trimite-ne un email la adresa [email protected] în care să prezinţi punctual activităţile în care te-ai implicat şi motivele pentru care crezi ca ai fi potrivit ca intern infoarena. Echipa va evalua aceste argumente şi în funcţie de rezultat te vom programa la un interviu. Interviul nu este unul tehnic, ci de fapt urmărim să te cunoaştem mai bine: să vedem ce preocupări ai, cu ce ţi-ar plăcea să ne ajuţi şi cum ai vrea să faci asta, cât timp îţi poţi dedica, etc. Dacă suntem mulţumiţi de cum decurge interviul, vom încerca să-ţi pregătim un internship cât mai curând. În momentul de faţă încercăm să organizăm internship-uri cel puţin anual, în perioada iulie-septembrie.

Cine sunt internii din această vară?

Anul acesta, echipa infoarena a condus o serie de interviuri la tabăra de pregătire a lotului naţional. La interviuri au participat 8 candidaţi, dintre care 6 au fost selectaţi pentru a deveni primii interni din istoria infoarena! Aceştia sunt (împreună cu mentorii lor):

• •Andrei-Bogdan Antonescu -- •Andrei Parvu
• •Andrei Poenaru -- •Andrei Parvu
• •Serban Andrei Stan -- •Paul-Dan Baltescu
• •Gavrila Vlad -- •Andrei Parvu
• •Adrian Budau -- •Savin Tiberiu
• •Tache Alexandru -- •Bogdan-Cristian Tataroiu

Avem aşteptări mari din partea voastră şi sperăm să ne confirmaţi faptul că merită să investim în acest proiect pe viitor. Mult spor şi să sperăm că la finalul acestor 3 luni veţi avea multe realizări cu care să ne mândrim împreună!

Dacă doriţi să aflaţi şi mai multe informaţii despre internship-uri, trimiteţi un email cu întrebări la adresa [email protected].

Problema pare initial complicata dar ea are o solutie simpla si eleganta daca o privim in trei dimensiuni.

Putem roti triunghiurile ADB, BEC si CFA in jurul laturilor AB, BC respectiv CA astfel ca cele trei triunghiuri impreuna cu triunghiul ABC sa fie fetele unui tetraedru. Acum conditia CFA + ADB + BEC <= 360 e evident adevarata: suma celor trei varfuri care se intalnesc in un varf al tetraedrului trebuie sa fie mai mica de 360 de grade.

Misto nu?

O problema misto de la Christian Szegedy:

Se da un triunghi ABC si trei puncte in exteriorul lui D, E, F astfel ca FA = DA, DB = EB, EC = FC si DAB + CAF >= BAC. Sa se demonstreze ca CFA + ADB + BEC <= 360.

Have fun!

UPDATE: Problema avea o conditie lipsa, am adaugat-o cu underline

Am auzit problema acum cativa ani de la Bogdan Piloca, si mi-a placut asa mult incat am dat una aproape identica la Google Code Jam in 2008.

O observatie care ne ajuta este urmatoarea: daca transformarea are un punct fix atunci si cand e aplicata asupra dreptunghiului transformat se va pastra punctul fix. Deci, putem sa o aplicam de mai multe ori pana cand dreptunghiul rezultat este foarte mic.

Pentru solutii mai detaliate puteti citi explicatiile de la google code jam.

Chief Executive Officer - Facebook
Handle: mzuckerberg
Algorithm Rating: 1044
Total Earnings: $124.00
Member Since: 04.10.2002
Country: United States
School: Harvard University
profil

Fost Chief Technical Officer - Facebook, fondator Quora
Handle: dangelo
Algorithm Rating: 2351
Total Earnings: $3,082.50
Member Since: 01.05.2002
Country: United States
School: California Institute of Technology
profil

Discutati.