Lovász László

Algoritmusok bonyolultsága

Algoritmusok bonyolultságának a vizsgálata a múlt század 30-as éveiben kezdődött, elősorban a Turing-gép és az algoritmikus eldönthetetlenség fogalmának kialakulásával. A számítógépek terjedésével és kapacitásuk növekedésével ez a tudományág egyre nagyobb jelentőségre tett szert. Ebben a jegyzetben tárgyaljuk mind a bonyolultságelmélet klasszikus alapjait, mind az újabb trendek közül néhány legfontosabbnak tartottat: az információs és a kommunikációs bonyolultságot, pszeudovéletlen számok generálását, párhuzamos algoritmusokat, a kriptográfia alapjait és az interaktív bizonyításokat. Az anyag nagy része feldolgozható két félévnyi 2+2 órás tárgyban.

 


Lovász László: Algoritmusok bonyolultsága című e-könyve elérhető az Interkönyv oldalán a következő formátumokban: pdf.

Ajánlott könyvek