REKLAMA

Złożoność obliczeniowa. Czyli P (chyba) ≠ NP i dlaczego RSA nie da się złamać.

Kiedy przeglądałem ostatnio Internet, natknąłem się na postawione przez kogoś pytanie: czy algorytmika jest częścią matematyki? Odpowiedzi były bardzo skrajne – od twierdzących do kategorycznie zaprzeczających. Tymczasem przecież cała informatyka jest jedną z dziedzin matematyki; trudno więc, by algorytmika – będąc jednym z najbardziej kluczowych działów informatyki – nie wzbudziła również zainteresowania matematyków...

Zagadnienia poruszane w tym artykule:

  • Algorytmy;
  • Czas realizacji zadania;
  • Maszyna Turinga;
  • Wariacje;
  • Przykłady;
  • Kompletność;
  • Złożoność algorytmu dodawania;
  • Notacje O, Ω i Θ;
  • Klasy złożoności;
  • No więc dlaczego RSA nie da się złamać?
  • Czym jest P i NP?

Artykuł pochodzi z magazynu "Programista" nr 8/2018 (75). Jest to wydanie z przełomu października i listopada 2018. Szczegółowy spis treści: https://programistamag.pl/programista-8-2018-75/

Autorem artykułu jest Wojciech Sura. Programuje od przeszło dziesięciu lat w Delphi, C++ i C#, prowadząc również prywatne projekty. Obecnie pracuje w polskiej firmie PGS Software S.A., zajmującej się tworzeniem oprogramowania i aplikacji mobilnych dla klientów z całego świata.

>>FRAGMENT TEGO ARTYKUŁU DO POBRANIA<<