Note de curs, clasele 11-12, 7 decembrie 2012

From Algopedia
Jump to navigationJump to search

Programare dinamică

  • distanța Levenshtein
    • operație suplimentară: inversarea a două caractere
  • cea mai lungă subsecvență comună
    • memorie O(n) dacă se cere doar lungimea
    • trucuri pentru aflarea subsecvenței când memoria disponibilă este mai mică decât O(m * n)
  • cel mai lung subșir crescător
    • observație: este cea mai lungă subsecvență comună între V și V sortat
  • graf permutare - clică maximă
  • nu întotdeauna trebuie să ne repezim la programare dinamică
    • exemplu: dintr-un vector de 2 * n numere, doi jucători aleg pe rând câte un număr de la capăt. Cel care obține suma mai mare câștigă
    • greedy: să se găsească o strategie de câștig pentru primul jucător
    • PD: să se găsească scorul maxim pe care îl poate obține primul jucător

Teme

  • Se dau 12 bile, toate identice ca aspect, din care 11 au aceeași greutate, iar una este mai grea sau mai ușoară. Se dă o balanță cu două talere. În trei cântăriri, să se afle care este bila diferită și dacă este mai grea sau mai ușoară.
  • Să se calculeze numărul de circuite hamiltoniene într-o rețea de 4 * n orașe.