Informatica teoretică@FMI-150 : Ziua a doua

Ieri a fost in mare o zi de semantică și metode formale. Azi pare să fie o zi de limbaje formale, automate și combinatorică pe cuvinte.

Programul zilei de azi:

Florentin Ipate (UB)- Model learning and test generation using cover automata.

SAMSUNG

„Why use automata learning in model-based testing ?” Cu un răspuns la această intrebare și-a motivat Florentin prezentarea, care imbină tehnicile de verificare formală (cu accent deosebit pe  testare) și teoria automatelor.

Invățarea este o tehnică folosită pentru a rezolva problema exploziei numărului de stări intr-un model bazat pe stări al sistemului care trebuie testat. Tehnica conduce la construcția unor modele aproximative.

Prezentarea (mărturisesc că citisem lucrarea) e incadrată in paradigma lui Angluin de invățare a unui limbaj (regulat) cu un invățător.

„In testare suntem interesați de secvențe scurte”. Această idee naturală motivează ideea lui Florentin de a defini o „aproximație” pentru un limbaj regulat, care acceptă dintr-un limbaj regulat L exact acele secvențele din L, pentru cuvinte de lungime cel mult K – unde K e un parametru al algoritmului. Aproximarea nu prescrie ce se intămplă cu cuvinte de lungime mai mare decât K și conduce la conceptul de cover automata.

O idee simplă dar extrem de frumoasă. Metoda  de invățare a lui Angluin poate fi adaptată la automate cover. Avantajul constă intr-un număr de stări considerabil mai mic pentru automatul cover. Metoda are aplicații practice in testare.

Cum am spus, ideea din prezentare mi-era deja cunoscută. Totuși am invățat destule lucruri noi din prezentare. Pe lăngă legătura cu testarea (pe care n-o știam), răspunsuri la intrebarea „cum alegem parametrul K” (răspunsul: cu ajutorul unor metrici venind din analiza acoperirii), existența unor aspecte tehnice in adaptarea algoritmului lui Angluin, sau cum adaptez membership queries/counterexamples in contextul practic de testare.

Și un anunț foarte interesant la sfărșitul prezentării: ICTAC 2014 are loc la București (deadline 16 Martie 2014).

Marian Gheorghe (Sheffield)- Modeling and verification with membrane systems.

SAMSUNGMarian și-a inceput prezentarea cu o prezentare a domeniului sistemelor cu membrane (P-sistemelor), situându-l  in contextul mai larg al calculului natural, cu legături către verificare formală. O variantă a paradigmei calculului cu membrane (așa-numitele kernel P-systems) pot fi folosite pentru a exprima o soluție a problemei firing squad.

Pe de altă parte colaborarea cu Florentin Ipate a condus la rezultate privind formalisme pentru legătura dintre P-sisteme și metodele de testare.

In sfârșit, modele probabiliste pentru P-sisteme și modele inrudite au aplicații in biologi, la modelarea gene regulatory networks.

Cristina Tirnăucă (Santander)- The role of hypergraphs in association rule discovery.

SAMSUNG

Pe Cristina o cunoscusem până acum doar prin intermediul prezentării de pe videolectures, pe care o privisem pentru că  interesele mele de cercetare au legătură și  cu invățarea gramaticală (domeniu in care ea și-a susținut teza). Cristina a vorbit despre un interes mai recent de cercetare, domeniul data mining, făcând o introducere in domeniul descoperirii regulilor de asociere, modelării lor cu clauze Horn, eliminării redundanței intre reguli. Partea centrală a prezentării a fost legată de rolul hipergrafurilor, in principal al problemei hypergraph transversal in descoperirea regulilor de asociere.

Cristina și-a terminat prezentarea cu o „aplicație” a tehnicilor de data mining la conferința in desfășurare ! 🙂

Robert Mercaș (Kiel) Repetitions in partial words

SAMSUNG

Subiectul repetițiilor și al generalizărilor lor este unul bine studiat in domeniul combinatoricii pe cuvinte. Un rezultat clasic al domeniului este faptul că așa-numitul șir Thue-Morse definit prin

01101001100101101001011001101001\ldots,

punctul fix al morfismului (0 \rightarrow 01), (1 \rightarrow 10) (aplicat punctului inițial 0) este aperiodic. El conține pătrate, dar nu conține suprapuneri, factori de genul axaxa, cu a\in \{0,1\} și x\in \{0,1\}^{*}.

Robert generalizează teoria de mai sus considerând cuvinte parțiale, in care literele pot fi inlocuite cu un simbol * („don’t care”). Prezentarea lui a atins o mulțime de rezultate privind repetiții in cuvinte parțiale (lipsa de repetiții, numărul de litere pe care trebuie să aibă alfabetul pntru a evita pătrate, cuburi, patternuri pe care le putem evita peste peste alfabete binare, ternare, patrate „mari”, repetiții „abeliene”). Evident că nu pot comprima toată această informație in câteva rânduri. Mă mărginesc să vă invit să consultați numeroasele lucrări ale lui Robert pe această temă.

Florin Manea (Kiel) – Hidden structures in words.

SAMSUNGPrezentarea lui Florin a continuat tema combinatoricii pe cuvinte (incepută de Robert).

Florin a pornit de la următoarea teoremă a lui Fine și Wilf:

Let w be a word on an alphabet A having periods p and q. If   |w|\geq p+q=gcd(p,q) then w has period gcd(p,q).

The value p+q=gcd(p,q) is the smallest one that makes the theorem true.

Un alt mod de a exprima teorema de mai sus este că dacă două cuvinte periodice au un prefix comun de lungime suficient de mare atunci cele două perioade sunt la rândul lor puteri ale unei perioade comune.

Dacă in rezultatul de mai sus cuvintele erau periodice, intr-o lucrare recentă Czeiszler, Kari și Seki au considerat o generalizare a cadrului de mai sus intr-un cadru motivat de  analogia cu ce se intâmplă in șirurile ADN: complementul unui șir w (de exemplu, complementul lui CAC este GTG) conține aceeași informație ca și w și intr-un anumit sens poate fi considerat „același cuvânt”.  Czeiszler și coautorii (și pe urmele lor Manea și coautorii) consideră extensii ale teoremei Fine-Wilf când in loc de repetiția aceluiași cuvânt avem de-a face cu forme mai sofisticate de „periodicitate”.

Dacă prima parte a rezultatelor prezentate de Florin erau „structurale” un alt grup de rezultate (favoritele sale, după propria mărturisire) au o natură algoritmică. Un exemplu: Algoritmul 2 din această lucrare decide dacă un cuvânt arbitrar este o „pseudo-repetiție” a unui cuvânt in timp O(n \log(n)), O(n) pentru cazuri cu o structură specială.

Masa rotundă

A abordat in prima sa parte subiecte legate de  istora informaticii la Universitatea din București: au vorbit profesorii Dragoș Vaida, Ioan Tomescu, Virgil Căzănescu, Marian Gheorghe, Cristian Calude.

Nu voi ilustra ce s-a spus decât prin următoarea intâmplare din inceputurile informaticii, povestită de profesorul Dragoș Vaida:

Ce se intâmplă când (cum se intâmpla in trecut) timpii pe care ii puteai folosi pentru a rula progame iți erau alocați ? Si când ți s-a atribuit același interval de timp pentru a rula programe pe două calculatoare diferite, dar nu ai decât un program pe care să-l rulezi ? Anul era 1964, „nu venise incă Ceaușescu in România”, calculatoarele fiind CIFA2 și CIFA 3). Inceputul calculului paralel in România 🙂

Cele două calculatoare au returna, evident, rezultate diferite 🙂

Anunțuri
Acest articol a fost publicat în evenimente, informaticã teoreticã. Pune un semn de carte cu legătura permanentă.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s