Informatica teoretică@FMI-150 : duminică, ultima zi

Programul zilei de azi:

Ioan Tomescu. Connected graphs of diameter two having minimum and maximum degree distance.

SAMSUNGO ramură interesantă de cercetare a teoriei  grafurilor este situată la confluența cu chimia: de multe ori proprietățile topologice ale grafului asociat unei substanțe organice, măsurate prin  diverși invarianți oferă predicții privind proprietățile fizico-chimice ale substanței respective.

Pentru a da doar un exemplu de astfel de parametru, indicele Wiener asociat unui graf G=(E,V) se  definește prin formula

W(G)=\frac{1}{2}\cdot \sum_{v\in V(G)} D(v), unde

D(v)=\sum_{w\in V(G} d(v,w) și, in fine, d(v,w) este distanța intre cele două noduri (numărul minim  de muchii care trebuie traversat pentru a ajunge de la v la w. Conform Wikipedia indicele Wiener este corelat, de exemplu, cu punctul de topire al alcanilor. Cum chimia n-a fost tocmai o iubire de-a mea cred  această afirmație pe cuvânt 🙂

In prezentarea sa profesorul Tomescu a oferit o privire de ansamblu asupra cercetărilor sale pe tema determinării valorilor extreme (maxime și minime) ale diverșilor indici ai grafurilor in grafuri de diametru mărginit. N-am, evident, cum să rezum aici numeroasele rezultate prezentate, așa că mă voi mărgini să dau doar un exemplu, unul legat de așa-numita degree distance intr-un graf, definită prin

D^{\prime}(G)=\sum_{v\in V(G)} deg(v)\cdot D(v).

Dl. Profesor Tomescu  arătat că pentru grafuri de diametru doi avem

D^{\prime}(G)\geq 3n^2-7n+4, cu egalitate pentru „graful stea” cu n noduri. Pe de altă parte

D^{\prime}(G)\leq \frac{2n^{4}}{27}+O(n^{3}),

cojectura sa că factorul 2 in inegalitate poate fi eliminat fiind demonstrată recent de niște matematicieni sud-africani.

Vreau să inchei cu remarca că indici de genul celor de mai sus sunt utili și in analiza rețelelor sociale, un subiect mult mai drag mie decât chimia 🙂

Ioana Leuștean. A propositional logic related to the Pierce-Birkhoff conjecture.

Ioana-1

Prezentarea Ioanei, una foarte densă pentru mine, a tratat o problemă aflată la intersecția algebrelor cu mai multe valori (cunoscute drept MV-algebre) cu domeniul geometriei (algebrice) a polinoamelor.

Conjectura Pierce-Birkhoff (de care mărturisesc că nu auzisem) afirmă că orice funcție f:{\bf R}^{n}\rightarrow R care este continuă și polinomială pe componente (eng. piecewise polynomial) poate fi scrisă ca un maxim de minime de funcții polinomiale, in formule

f(x)=max \{ min_{j} \{ g_{i,j}(x) \} \}.

In algebra booleană max corespunde operației logice ȘI (\wedge) iar min operației SAU (\vee). Prin urmare formula de mai sus poate fi privită ca o analogă (cu mai multe valori) pentru forma normală conjunctivă a unei funcții booleene.

Conjectura Pierce-Birkhoff rezistând incercărilor de demonstrare, Ioana a prezentat mai multe rezultate inspirate de această problemă deschisă obținute restrângând domeniul/codomeniul funcției f implicate.

Andrei Păun. Cell simulation using a new discrete technique.

SAMSUNGDupă grafuri și algebre cu mai multe valori a venit rândul modelelor de calcul cu inspirație biologică. Prezentarea lui Andrei, al cărui titlu a diferit intrucătva față de cel din program – listat mai sus – a acoperit:

– rezultate teoretice privind proprietățile P-sistemelor simport-antiport.

– rezultate de aceeași natură pentru P-sisteme cu impulsuri, modele care idealizează funcționarea rețelelor neuronale.

– rezultate experimentale privind folosirea P-sistemelor ca o metodă de simulare a interacțiilor intre proteine, comparând această metodă cu cele bazate pe ecuații diferențiale ordinare, respectiv simulări de tip Gillespie.

In loc de concluzie. Două zile și jumătate de prezentări  din care (deși temele  nu  prea corespund intereselor mele de cercetare) am aflat destule lucruri noi. M-am intâlnit cu o mulțime de oameni pe care ii cunoșteam doar după nume/prin lucrări și reintâlnit cu alții pe care ii cunoșteam de multă vreme 🙂

O intâlnire care a concentrat o parte semnificativă a celor care au mai rămas să facă informatică teoretică in România precum și un număr de oameni care au ales să urmeze această direcție de cercetare in afara țării.

Și o surpriză pentru mine: blogul meu e mai citit decât mă așteptam 🙂

Anunțuri
Acest articol a fost publicat în evenimente, informaticã teoreticã, Timişoara, Uncategorized. 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