Note de curs, clasele 9-10, 19 aprilie 2013

Căutări pe stringuri

automate finite
nu toate limbajele pot fi decise de automate finite: L = { 0ⁿ1ⁿ | n >= 0 }
- demonstrație intuitivă: pot construi un automat pentru 0 <= n <= 4, dar mi-ar trebui un automat cu număr infinit de stări pentru n infinit.
exemplu pentru P = abacaba
după construirea automatului, algoritmul rulează orbește în O(n)
construirea automatului se face în O(m³ * |Σ|)
există un algoritm în O(m * |Σ|), dar avem deja algoritmul KMP în O(m).

nu mai depinde de mărimea alfabetului
în loc de o matrice δ[m][|Σ|], folosește doar un vector π[m]
intuitiv, când următorul caracter nu se mai potrivește, algoritmului KMP nu-i mai pasă ce caracter anume urmează la intrare
starea următoare în care trece patternul depinde doar de pattern
de aceea, KMP face ceva mai multe comparații decât un automat finit „perfect”, dar asimptotic este tot O(n)
mai exact, π[q] = max { k | P_k este sufix al lui P_q }
cod pentru construirea lui π și pentru căutarea propriu-zisă

Se dau două șiruri A și B, ambele cu câte n caractere. Să se spună dacă A este permutare circulară a lui B.
Se dă un șir A cu n caractere. Să se afle care dintre cele n permutări circulare ale lui A este minimă lexicografic.

Arbori de joc, exemplificați pe X și 0
Scorurile pozitive sunt bune pentru X, iar cele negative sunt bune pentru 0
Deci nivelurile alternează între „mini” (0 caută cel mai mic scor) și „max” (X caută cel mai mare scor)
Arborele minimax are 9! noduri (vreo 30.000 după eliminarea simetriilor)
La alte jocuri, arborele este (mult) prea mare pentru a putea fi analizat complex
Mergem în adâncime cât de mult putem, iar la ultimul nivel analizăm poziția cu o euristică statică
Euristica ia în calcul materialul, dar și poziționalul (pioni avansați, controlul centrului, regele expus, dacă tocmai am dat șah)
Exemplu pe arbore
- Demonstrație că nu ajung întotdeauna în cel mai bun nod pentru mine, ci în cel mai bun nod presupunând că ambii jucători joacă perfect.
Pseudocod pentru minimax. Depinde de trei funcții:
- euristica statică
- generarea tuturor mutărilor legale într-o poziție dată
- efectuarea unei mutări legale pe tablă
Algoritmul negamax: valoarea unei poziții este maximul valorilor fiilor, luate cu semn schimbat
- Nu mai trebuie să trateze separat cazurile în care albul, respectiv negrul, este la mutare