Joi 10 aprilie ora 13 in sala 318 (etaj 3) a Facultatii de Matematica si Informatica din Universitatea din Bucuresti, va avea loc prezentarea cu titlul "Runtime Verification Based on Register Automata" sustinuta de Radu Grigore.

Un abstract si o scurta prezentare a speaker-ului mai jos. In particular, Radu a contribuit adesea cu comentarii pe forumul infoarena si, daca imi aduc aminte bine, a scris macar un post pe blog.

-----------------------------------------------------------------------------------------------------
Abstract:

Runtime Verification, like Military Intelligence, is an established oxymoron.
It is a thriving research area concerned with finding bugs by monitoring programs while they run.
I will begin with a short review of some notable tools and of the formalisms on which they are based.
Typically, each tool invents its own formalism. I will then present TOPL, a tool whose main claim to glory is that it is based completely on a pre-existing formalism, namely, register automata. The connection between these two domains, runtime verification and automata over infinite alphabets, is rather obvious with hindsight.
Still, the connection was not noticed before, and is yet to be fully exploited.

------------------------------------------------------------------------------------------------------------
O scurta biografie a lui Radu Grigore:

Radu Grigore is a postdoctoral researcher at University of Oxford. Previously (2010--2013), he was a postdoc at Queen Mary, University of London. Earlier (2005-2010), he was a doctoral student at University College Dublin. Even earlier (2003-2005), he was a software engineer in Nobug Consulting, Bucharest.
In 2003, he finished University Politehnica of Bucharest (Electronics).

Yeah, actually "whatever data structure you prefer" included the functions computed by KMP But I must confess that I kind of like suffix arrays, so I just gave them priority Anyway, as I said, the linear solution can be achieved with some sort of rolling hash as well.

@Andrei: Actually, problem 4 can be solved in a much easier way
You are just interested in the existence of a border in the word S. That is, some L such that S[1..L]=S[N-L+1..N]. This can be tested in linear time with suffix arrays (or whatever data structure you prefer), as well as with rolling hash.
But, anyway, nice solutions

S-a facut un site memorial pentru Mihai aici: http://mipmemorial.blogspot.de/

O veste groaznica. Sa se odihneasca in pace!

Eu cand ma gandesc la Mihai imi vine intotdeauna in cap descrierea pe care i-a facut-o un fost student (Andrei Matei) mai demult: un rock-star al informaticii teoretice. Imi voi aduce aminte intotdeauna amabiliatea si entuziasmul cu care a acceptat ideea de a tine cateva talk-uri la Unibuc prin 2008, si generozitatea cu care dorea sa se implice in a ajuta studentii talentati sa o ia pe drumul cercetarii. Cred ca a fost pentru multi dintre cei mai tineri cercetatori romani in TCS un etalon si o inspiratie (inclusiv pentru mine).

Avand in vedere implicarea sa continua in fenomenul olimpiadelor as sugera board-ului infoarena sa acorde anual un premiu care sa ii onoreze memoria (spre exemplu, premiul 1 de la Algoritmiada ar putea sa ii poarte numele). 

PS: Trebuie spus si ca Mihai tocmai ce primise unul dintre cele mai importante premii pentru cercetatorii tineri in TCS: Presburger Award. Merita citit laudatio-ul asociat acestui premiu pentru a intelege exact impactul pe care l-a avut Mihai in prea scurta sa cariera: http://eatcs.org/index.php/component/content/article/1-news/1243-presburger-award-2012

E incredibil cum se termina stirea indicata de Andrei. Primul-ministru spune: "Probabil in perioada urmatoare vom afla ca acuzatiile care i se aduc domnului Mang nu se sustin, probabil obiectivul era sa plece domnul Mang." Mda.

Update: Din pacate, intr-un moment de maxim penibil, Academia Romana a decis sa nu mai aiba o opinie asupra acestui fapt. Desi legal ei nu aveau nici o treaba cu subiectul, mi se pare jenant ca nu au decis sa condamne public declaratiile (citate in post) facute de Mang.

Pe de alta parte, cazul a ajuns in Nature: http://www.nature.com/news/plagiarism-charge-for-romanian-minister-1.10646

@tudalex: documentele care au aparut sunt de tot rasul. Nu cred ca merita studiate in amanunt. Sunt copiate aproape cuvant cu cuvant dupa diverse lucrari (mai mult sau mai putin corecte / serioase, la randul lor). Sunt sigur ca cine le-a scris nu intelegea mare lucru din ceea ce copia. Cred ca e pierdere de vreme sa te mai uiti la ele, si sa le mai analizezi.

@Filip: tot scandalul asta are si ceva bun in el. Arata stadiul (de degradare) in care este cercetarea (in informatica) si educatia din Romania. Ce speranta sa ai in contextul in care se "vand" diplome la universitati chiar mari din tara, sub numele de "invatamant cu taxa / la distanta / fara frecventa", in contextul in care multi studenti cauta metode noi de a copia in loc sa caute sa inteleaga ceea ce se preda (gandindu-se ca poate le va folosi candva), in contextul in care majoritatea productiei stiintifice originata in Romania este publicata in jurnale sau conferinte invizibile pentru oamenii seriosi, cand aceste lucrari nu sunt citate deloc in locuri respectabile?

Referitor la scandalul propriu-zis, ultima noutate mai interesanta este pozitia oficiala Ad-Astra, referitoare la plagiat: http://www.ad-astra.ro/posts/view_post.php?post_id=1937&lang=en. Trebuie precizat ca Ad-Astra e o organizatie a cercetatorilor din Romania (cei seriosi, care chiar produc ceva) care a avut pana acum ca interes principal instituirea unor criterii de calitate in evaluarea cercetarii de la noi.

Apoi ar mai fi cateva declaratii ale lui Mang, care continua sa para din alta lume. In timp ce sustine in continuare ca el nu are nici o treaba cu articolele copiate, mai spune si ca statea de vorba cu "niste colegi, profesori reputati,"  si se gandeau cum se poate sa ne asiguram ca nu trimite altcineva articole in locul nostru la jurnale / conferinte. Asta arata, inca o data, ca domnul Mang nu are nici o treaba cu cercetarea serioasa. In general, orice "submission" la un jurnal serios este insotita de o serie (parca interminabila) de confirmari (pe site-ul unde faci submisia sau prin e-mail), de aprobari necesare, de formulare de copyright, si asa mai departe. Chiar daca cineva reuseste sa isi asume identitatea ta si sa treaca prin toate aceste filtre, cred ca nu o sa fie prea greu sa dovedesti apoi ca totul a fost un furt de identitate. Iar colegii reputati probabil ca erau tot niste pseudo-cercetatori, ca altfel nu ar fi avut astfel de dileme. Ca o paranteza: cercetarea de informatica din Romania este foarte apropiata de matematica, fiind rareori publicata in jurnalele sau conferintele de top. Totusi exista cercetatori din Romania care publica in locuri demne de tot respectul lucrari de cercetare originale si valoroase (intr-adevar, pe subiecte mai putin "la moda"). Nu pot crede ca astfel de oameni pot confirma ceva din ce zice Mang.

In fine, sa nu mai lungesc un mesaj foarte lung deja (e amuzant cat m-a "prins" acest subiect stupid), parerea mea este ca acest om e nepotrivit pentru a fi ministru in primul rand pentru ca nu intelege deloc domeniul pe care il va coordona (cercetarea), si abia apoi datorita acuzatiilor (care vor fi probate sau nu oficial) de plagiat.

Cel mai amuzant e ca Mang nici nu contesta ca lucrarile respective ar fi plagiate. Acum spune ca nu sunt lucrarile lui!!! Cum a ajuns numele lui pe ele, cum de nu si-a dat seama, cum de sotia sa are la randul sau lucrari plagiate, toate astea sunt inexplicabile  . 

Iar referitor la povestea cu "legea lui Ohm": nu sunt nuante, impresia mea e ca multa lume din universitatile din Romania chiar crede ca asa se face cercetare (si aici trebuie avute in vedere centre universitare mai mici, dar si universitati mai mari, cu un oarecare renume, si cu afluenta mare de studenti). Astfel de oameni citesc (lectureaza, mai bine zis, ca nu inteleg mare lucru) 10 articole, fac o compilatie, si au scos o teza de doctorat / un articol "nou" / o carte. Partea urata e ca fiind spus explicit acest lucru de ministru capata un accent de "e in regula sa faci asa"  .

E corect ca de atat praf in ochi nu mai intelegi nimic. Si e clar ca daca nu esti pe subiect, si ai informatiile doar din presa, mai bine nu iti dai cu parerea. Dar ideea e sa vina cineva si sa arate totusi faptele cat de cat clar.

Referitor la alte pozitii, a mai fost o pozitie a unei asociatii EDU CER (care-l include pe Gigel Militaru), dar era legata mai ales de acuzatiile de plagiat. Ceea ce ma deranjeaza pe mine este insa mai ales faptul ca ne este prezentat plagiatul respectiv ca o varianta corecta de a face cercetare. Aici cred eu ca trebuie sa se spuna nu de catre cei care chiar fac asa ceva, si chiar de catre "oficiali". E mai mult o chestie de principiu decat ceva legat strict de cazul de fata.

Late Edit:
Din pacate m-am grabit in a spune ca nu a existat nici o reactie a unei organizatii. Liviu Ornea, profesor la Unibuc si reprezentant Ad-Astra, http://www.ad-astra.ro/ a discutat la TVR problema plagiatului lui Mang: http://tvr.ro/articol.php?id=125510 .

Felicitari Mircea pentru post, si pentru initiativa de a scrie aceasta serie de posturi! Si felicitari si pentru succesul avut cu Summify!

M-am regasit in multe din ideile scrise de Mircea. Totusi sunt cateva nuante care trebuie mentionate.

Partea PhD + partea teoretica + implementarea de cod. La mine se aplica perfect (mai ales ca pana in facultate nu ma ocupasem deloc de informatica, ci lucrasem doar la mate). Si cred ca se aplica mai ales celor care au ales sa faca Informatica Teoretica. Andrei Homescu a punctat foarte bine cateva aspecte privind cum e sa iti faci PhD intr-un domeniu aplicat. Poate ne mai zic cate ceva Mugurel si Radu Grigore...  La fel, e adevarat ca destinatiile celor care au facut PhD in informatica teoretica sunt in special universitatile si laboratoarele de cercetare; mie imi e mai greu sa spun ce se intampla cu cei care au facut PhD in informatica aplicata, pentru ca nu prea am avut de a face cu "aceasta parte a lumii".

In general e dificil sa iti atragi finantare (inclusiv in Romania, unde vrei sa traiesti si din altceva decat din salariul mizerabil de profesor). Exista o inclinatie a diverselor comisii de a da bani mai ales in anumite domenii (mai populare), dar, in general, un proiect bine scris si care "promite" ceva publicatii bune o sa fie finantat. Spre exemplu, in 2009 m-am mutat in Germania dupa ce am primit finantare pentru un proiect venit cumva din aria limbajelor formale (care nu mai e un domeniu la moda); se pare ca fundatia care dadea banii (Alexander von Humboldt) a crezut ca poate iesi ceva din acel proiect, si sper sa fie si multumita acum Dupa terminarea bursei, am gasit un job in cercetare la Universitatea din Kiel, lucrand insa intr-un domeniu ceva mai "la moda" (in Europa): combinatorics on words. In ambele cazuri finantarea a fost/este buna.

Experienta PhD-ului a fost cumva ciudata in cazul meu. In primul rand, am stiut inca din liceu ca vreau sa fac cercetare. La asta a contribuit mult mersul la olimpiade (unde m-am obisnuit ca activitatea mea principala sa fie rezolvatul de probleme ), dar si faptul ca aveam exemple de oameni care lucreaza in asa ceva in familie. Apoi, am ales sa fac PhD-ul in Romania. Probabil motivul cel mai puternic a fost comoditatea (stat in preajma familiei, prietenii, aveam casa in Bucuresti, etc.); a mai fost foarte important si faptul ca m-am inteles excelent cu supervisorul, profesorul Victor Mitrana, care este un nume cunoscut in comunitatea limbajelor formale - practic nu mi-am pus nici un moment problema de a face doctoratul cu altcineva. Am terminat repede (cat au durat cursurile obligatorii de master + 2 ani), si am avut si norocul de a avea o finantare foarte buna in perioada respectiva. A fost mai enervanta experienta sustinerii doctoratului, dar asta e alta poveste (am scris pe blogul meu in 2007, daca sunteti interesati - acum rad daca imi aduc aminte). Totusi, odata ajuns in Germania, mi-am dat seama ca e mult mai bine sa iti faci doctoratul afara (mai ales in US, Germania, Anglia, Franta). Nu stiu daca as fi avut un supervisor mai bun, poate nu ma intelegeam asa de bine cu colegii, dar cred ca mediul ar fi fost mai competitiv, as fi auzit mai repede de locurile unde e cel mai bine sa publici, as fi trimis lucrari la conferinte/jurnale mai bune, etc.; pe scurt, as fi fost fortat de mediu sa imi cresc nivelul - in Romania nu aveam alta motivatie decat cea individuala. Insa, e foarte important de spus, "afara" trebuie sa insemne facultate de top. Nu are sens sa pleci la o facultate slaba de afara doar pentru a pleca din tara (sigur, se mai poate discuta despre nivelul de viata din tarile vestice, dar asta e alta poveste). Faptul ca am avut un supervisor bun la doctorat, si probabil un set de bune practici, m-a ajutat sa ma acomodez aici fara probleme. Am impresia ca putea fi mai bine pe plan profesional sa fi plecat la PhD din tara; din punct de vedere personal, cred ca am facut foarte bine sa raman in tara atunci, si, overall, nu regret deloc decizia. Nu pot face o recomandare decisa in favoarea unei alegeri: fiecare trebuie sa se informeze cat mai bine, apoi sa faca alegerea cu capul lui, cu motivele lui.

Cam asta ar fi tot ce pot zice pe moment Si, de fapt, mai e ceva: dupa terminarea bursei postdoc am avut ca optiune principala sa raman in cercetare in Germania / Vest, si asta e in continuare optiunea mea nr. 1.

Cred ca dezbaterea e mai interesanta decat poll-ul in sine Initial am citit pe scurt intrebarea si am votat fara sa ma gandesc prea mult... pentru ca apoi, dupa ce m-am gandit, sa imi elimin votul si sa cantaresc mai bine in ce directie sa il pun. Bine ca nu au fost alegeri pentru ceva important, ca atunci nehotararea mea nu era prea buna )

Spune bine Cosmin: nu sunt nici eu un ferm sustinator al vreunei parti. Important e sa imbunatatesti sistemul de acum, nu sa il schimbi. Si atunci cand ai o demonstratie ca ceea ce aduci tu e mai bine vei avea probabil si sprijinul comunitatii.

Apropo de poll: nu mi se pare ca de fapt e o intrebare care accepta 2 raspunsuri da sau nu. Cred ca e mai mult o chestie de nuante. As zice da, surse open, daca as avea si o metoda de a implementa acest lucru fara a strica conceptul din spatele infoarena. As zice nu pentru ca imi place destul de mult infoarena asa cum e acum. Deci cred ca merge un poll atunci cand o sa fie pusa intrebarea altfel: "am metoda X, care va fi implementata in felul Y; vi se pare ok sau nu?" Am inteles din intrebarea initiala a lui Andrei ca scopul ar fi sa se imbunatateasca pregatirea. Ok, suna foarte bine; insa avem mijloacele de a face asta fara a transforma infoarena intr-un repository de surse? Avem speranta ca vor aparea vizibil surse noi, solutii noi, fara a fi acoperite de o tona de surse retrimise?

Referitor la clasament: e o masura a cat (cantitate) a lucrat fiecare. Nu e singura masura posibila, dar e ceva. Spre exemplu poate fi interesant sa vezi cati oameni au rezolvat o anumita problema, si, astfel, sa te prinzi de cat de grea este; cand ai surse open nu mai are nici o relevanta asa ceva. Nu are rost sa se anuleze aceasta metrica pana nu exista una cu o scara de aplicabilitate la fel de larga sa fie pusa in loc, indiferent de cat de irelevanta considera fiecare ca e masura actuala. Rating-ul sau performanta in concursurile infoarena nu pot sa o inlocuiasca, avand in vedere ca astfel de concursuri nu se pot organiza intr-un ritm foarte sustinut...

La o prima privire as vota "da" la intrebarea lui Wef. Pentru ca, spre exemplu, multe carti de probleme (de mate, fizica sau mai stiu eu ce) au si raspunsuri; totusi nu te uiti la raspunsuri fara a sta sa te gandesti, fara a incerca sa rezolvi individual problema. Si le dau dreptate celor care spun ca pana la urma e responsabilitatea fiecaruia felul in care se pregateste si ceea ce intelege fiecare dintr-un site de pregatire/ culegere/ lista de probleme/ ....

Exista totusi un pericol mare. Inevitabil "lumea" (in general marea masa a utilizatorilor, dar si unii dintre cei mai buni rezolvitori de probleme) o sa inceapa sa se uite in sursele de 100. Si, evident, nu o sa se uite in toate sursele de 100, ci in cele ale altor utilizatori buni. Si ajungem la un lucru scos in evidenta de Mircea Pasoi in discutia de la postul de blog Monopol.

Nu exista atitudinea sa te descurci singur (cum exista in generatia mea) cand primesti teme si probleme de la profesori. Toata lumea lucreza aceleasi lucruri si stiu aceleasi smenuri, si per total iese mai prost decat daca ai lasa pe fiecare sa-si aleaga calea.
Inteleg ca disciplina e buna, nu toata lumea are vointa necesara sa-si impinga limitele, mai trebuie si un sut in fund.

Si sutul in fund de care zicea Mircea poate consta exact in a iti bate capul cu o problema, in a descoperii intrebari care sa te ajute in rezolvarea problemei, in a pune acele intrebari colegilor sau pe forum, si asa mai departe.

Discutia poate continua cu argumente pro si contra (mai departe in viata nu mai ai surse de 100 in care sa te uiti, prin accesul liber la surse se pot raspandi si obiceiuri proaste, sau, pe de alta parte, se pot gasi idei diferite de rezolvare in surse diverse, invatam smenuri de codare, ...). Parerea mea e ca cel mai bun este status quo-ul. Surse open la cateva probleme relevante, iar apoi forumul este perfect ca cine vrea hinturi sa intrebe si sa primeasca raspunsuri. Pana la urma infoarena e departe de a fi un sistem "inchis".

PS: Mi se par interesante subiectul si discutia

Felicitari!

@Vasile Priboy: A fi la ceva distanta de sistem iti ofera o perspectiva mai buna asupra faptelor. Cred ca tocmai motivul ca un om care se afla la mare distanta de tot ceea ce se intampla in Romania s-a apucat sa scrie despre asa ceva ar trebui sa ne dea de gandit. Pun mult mai mare pret pe parerea lui Cosmin (lipsit de orice fel de interes!) decat pe parerea unor oameni care au interese in a rezolva intr-un fel sau altul problema asta. Nu trebuie sa faca el ceva... e suficient ca a deschis subiectul, ca si-a spus parerea.

Iar referitor la implicare: Cosmin si altii ca el au facut Infoarena sa fie ceea ce e astazi (adica cea mai importanta sursa de pregatire pentru majoritatea elevilor de la ONI). Sa ne uitam in arhiva de probleme daca nu credem asta. Iar posturile astea pe blog sunt chiar implicarea activa pe care o ceri tu, Vasile. 

Parerea mea este ca o limitare se impune... Insa trebuie gandit mai atent sistemul (probabil o limitare progresiva e cea mai buna idee: o limita mai permisiva initial, intarita pe parcurs, dupa un algoritm predefinit). Evident, limitari similare trebuie impuse si la alte olimpiade (nu si la concursuri private).

Probabil |w1| era de fapt |w|1 (1 indice inferior), si reprezenta numarul de 1-uri din w. Din pacate nici cel care ne-a cerut ajutorul nu stie ce se cere, si, de fapt, cred ca nici nu si-a pus problema sa incerce sa rezolve singur exercitiul (la fel si pentru ceea ce a intrebat pe alt topic).

Acum au aparut: http://acm.ro/problems.htm

Si se pare ca anul asta au pus si datele de test.

Felicitari celor 4 participanti si celor care s-au preocupat de pregatirea lor.

Felicitari!!! 

Felicitari concurentilor, si profesorilor care i-au pregatit!

Am aflat ca in urma cu cateva zile Tudor Sorin s-a stins din viata. Multi dintre noi au citit manualele sale, au invatat dupa acestea, si unora ne-a fost chiar profesor.

Sa se odihneasca in pace!

Inca o intalnire din seria anuntata mai sus: 26 iunie, FMI, sala 204, ora 15.

Multe felicitari celor 4 calificati! Le doresc sa se intoarca de la IOI cu medalii cat mai valoroase. Felicitari si celor care au selectat lotul: e nevoie de multa munca si imaginatie (pentru a face toate problemele astea) si, din pacate, si multa bataie de cap (organizare, etc.); in consecinta merita toata aprecierea.

Avand in vedere ca mai e un baraj doar, cu trei probleme probabil, cred ca nici concurentul de pe locul 8 nu mai are sanse.

Aici sunt rezultatele:
http://www.liis.ro/~lotinfo2008/rez/baraj4.xls

Noutati se gasesc pe site:
http://www.liis.ro/~lotinfo2008/

Rezultatele concursului: http://flmanea.blogspot.com/2008/06/selectie-acm-icpc-2008-2009-rezultate.html