Clasele 9-10 lecția 30 - 20 mai 2015

Reduceri

Generalități

Reducerea este mecanismul prin care transformăm o problemă în altă problemă. Mai exact, prin reducere arătăm că, dacă cunoaștem (sau, ipotetic, dacă am cunoaște) un algoritm pentru problema X, atunci îl putem (l-am putea) folosi pentru a rezolva problema Y.

Exemplu (trivial): Se dă un vector de N numere. Există două numere egale? Această problemă este cunoscută în literatură ca element distinctness problem. Observăm că ea se reduce la sortare astfel:

• sortăm numerele
• verificăm dacă există vreun număr egal cu succesorul său

De aici deducem că element distinctness are un algoritm $O(n\log n)$, deoarece atât costă sortarea, iar pasul (2) costă $O(n)$.

În general, dacă presupunem că avem o cutie magică pentru problema X, care durează $O(f(n))$, atunci reducerea unei probleme Y la X are următorii trei pași:

1. Primind o intrare I_Y pentru problema Y, o transformăm într-o intrare I_X pentru problema X.
2. Apelăm de k ori cutia magică pentru X
3. Transformăm soluția S_X pentru problema X într-o ieșire S_Y pentru problema Y.

Dacă pașii (1) și (3) costă respectiv $O(g(n))$ și $O(h(n))$, atunci soluția pentru problema X are costul total $O(g(n)+kf(n)+h(n))$.

Aplicații

Reducerile sunt bune în trei situații:

1. Pentru a găsi algoritmi: dându-se un algoritm pentru X, pot produce un algoritm pentru Y
2. Pentru a clasifica problemele una relativ la alta: dacă X este ușoară, și Y este ușoară
3. Pentru a demonstra că unele probleme sunt „grele”: dacă Y este NP-completă și Y se reduce la X, atunci și X este NP-completă.

Reducerile ne dau uneori algoritmi optimi, dar nu întotdeauna. Ele ne ajută însă să înțelegem ce putem și ce nu putem calcula, sau când are și când nu are sens să căutăm un algoritm cu o anumită complexitate.

Să analizăm câteva exemple.

Selecția și găsirea medianului

Selecția: Dându-se un vector V cu n elemente și un număr k, să se găsească al k-lea element în vectorul sortat.

Găsirea medianului: Dându-se un vector V cu n elemente, să se găsească al n/2-lea element în vectorul sortat.

Este evident că găsirea medianului se reduce la selecție: dacă am o cutie neagră S(V, n, k) pentru găsirea celui de-al k-lea element, o pot apela cu S(V, n, n/2) pentru găsirea medianului. Reducerea se face în O(1) și este limpede că cutia neagră nu are cum să meargă mai bine de O(n). Așadar, găsirea medianului este cel mult la fel de grea ca selecția.

Mai puțin evidentă este reducerea inversă: selecția se reduce la găsirea medianului. Algoritmul funcționează recursiv astfel:

  Select(V, n, k) { // 0 <= k < n
    if (n == 1) {
      return V[0]; // presupunem că și k = 0
    }
    int m = Median(V, n);
    Partiționează(V, n, m);
    if (k < n / 2) {
      return Select(V[0..n/2), n / 2, k);
    } else {
      return Select(V[n/2..n/2), n / 2, k - n / 2);
    }
  }

Întrucât știm că găsirea medianului se poate face în $O(n)$ determinist (cu algoritmul median-din-5), obținem pentru selecție complexitatea definită recurent

$T(n)=T(n/2)+O(n)\implies T(n)=O(n)$

Cu alte cuvinte, cele două probleme sunt echivalente ca dificultate. Rezultatul este oarecum surprinzător, căci mediana este un caz particular al selecției (pentru k = n/2).

De asemenea, remarcăm că algoritmul propus pentru selecție nu este cel mai eficient. Quickselect este mult mai bun în practică.

Sortarea se reduce la înfășurătoarea convexă

• Preambul: de ce sortarea este $O(n\log n)$
• Definiția înfășurătorii convexe

Să spunem că un prieten pretinde că a găsit un algoritm în $O(n)$ pentru înfășurătoarea convexă. Cum îl putem convinge rapid că a greșit? Îi arătăm că, dacă acest algoritm ar exista, l-am putea folosi ca să sortăm în $O(n)$. Cu alte cuvinte, arătăm că sortarea se reduce la înfășurătoarea convexă.

• Fie V = (x₁, ..., x_n) vectorul de sortat
• Construim setul de puncte S = { (x₁, x₁²), ..., (x_n, x_n²) }
• Pe acest set rulăm algoritmul (fictiv) în O(n).
• Căutăm punctul cu coordonată x minimă, tot în O(n).
• De la punctul minim parcurgem înfășurătoarea convexă și obținem numerele în ordine sortată.

Cheia acestei reduceri este că punctele din S stau pe o parabolă, deci formează un poligon convex.

Ce concluzie tragem de aici? Dacă am putea găsi înfășurătoarea convexă în O(n), am putea sorta în O(n). Întrucât știm că nu putem sorta în O(n), rezultă că nu există niciun algoritm de înfășurătoare convexă în O(n).

Mecanismul este util în general ca să nu investim efort inutil căutând algoritmi rapizi pentru o problemă, când putem demonstra că ei nu există.

Găsirea medianului (offline) se reduce la sortare

Iată un exemplu când reducerea nu ne ajută prea mult. Este evident că găsirea medianului se poate rezolva prin sortare: sortăm vectorul și returnăm al n/2-lea element. Dar ce aflăm de aici? Doar că putem găsi medianul în $O(n\log n)$. În realitate, cum am văzut, există algoritmi în $O(n)$.

Sortarea se reduce la găsirea medianului (online)

Problema medianului online: Se dă un vector cu n elemente. La fiecare element citit, trebuie să afișăm medianul de până atunci. Nu putem citi următorul element până nu tipărim medianul de până atunci.

O soluție naivă pentru această problemă rulează în $O(n^{2})$: la fiecare moment, apelăm cutia neagră de găsire a medianului.

Există o soluție drăguță cu efort total $O(n\log n)$. Găsiți-o!

Acum ne întrebăm: are sens să căutăm o soluție cu efort total O(n)? Răspunsul este nu. $O(n\log n)$ este optimul pe care îl putem obține și demonstrăm aceasta prin reducerea sortării la găsirea medianului online, astfel:

• Fie V = (x₁, ..., x_n) vectorul de sortat
• Fie M(V, n) o cutie magică pentru găsirea medianului online
• În această cutie introducem 4n numere, respectiv:
  • -∞ de n ori
  • vectorul V
  • +∞ de 2n ori
• Colectăm răspunsurile cutiei la elementele 2n + 1, 2n + 3, ..., 4n - 1
• Răspunsurile ne dau vectorul sortat

(Exemplu care arată de ce este așa).

Așadar, dacă am putea răspunde în timp mai bun de $O(n\log n)$ la problema medianului online, am putea sorta în timp mai bun de $O(n\log n)$.

3SUM se reduce la 3COLLINEAR

3SUM: Dat fiind un vector V cu n elemente, există trei elemente în vector a căror sumă este 0?

3COLLINEAR: Date fiind n puncte în plan, există trei puncte coliniare?

• Algoritm pătratic pentru 3SUM. Găsiți unul fără tabele hash!
• Există o conjectură că nu există o soluție mai bună de $O(n^{2})$
• Reducerea 3SUM la 3COLLINEAR

Alte variante ale lui 3SUM care toate se reduc la 3SUM:

• a + b + c = S
• a + b = c
• a + b + c = 0 în trei vectori diferiți

Element distinctness se reduce la closest pair

• Demonstrație că element distinctness cere $O(n\log n)$ comparații (în modelul bazat pe comparații -- nu în hash table, vector de frecvență sau alte abordări)

Closest pair: Se dau n puncte în plan. Care este distanța minimă între oricare două din ele?

• Eventual discuție despre soluția în $O(n\log n)$ pentru closest pair.

Dorim să arătăm că nu are sens să căutăm un algoritm mai bun de $O(n\log n)$ pentru closest pair. Pentru aceasta, reducem element distinctness la closest pair.

• Fie V = (x₁, ..., x_n) vectorul de numere
• Fie CP(S, n) o cutie magică pentru găsirea celei mai mici distanțe între puncte din S
• În această cutie inserăm punctele S = { (x₁, 0), ..., (x_n, 0) }
• Dacă CP răspunde cu 0, atunci există două elemente identice în V
• Dacă CP răspunde cu o valoare strict pozitivă, atunci toate elementele din V sunt distincte

Alte exemple mai grele

• RMQ -> LCA -> RMQ restricționat
• înmulțire de matrice -> ridicare la pătrat de matrice
• closest pair -> diagrame Voronoi
• cuplaj bipartit -> flux
• 3-SAT -> 3-COLOR