Skutečná RAM - Real RAM

Zvláště ve výpočetní technice výpočetní geometrie, a skutečná RAM (stroj s náhodným přístupem ) je matematický model počítače, který dokáže přesně vypočítat reálná čísla místo binárního pevný bod nebo plovoucí bod čísla používaná většinou skutečných počítačů. Skutečnou paměť RAM formuloval Michael Ian Shamos v jeho 1978 Ph.D. disertační práce.[1]

Modelka

Část „RAM“ názvu skutečného modelu RAM znamená „stroj s náhodným přístupem ". Toto je model výpočtu, který se podobá zjednodušené verzi standardní počítačové architektury. Skládá se z uložený program, a paměť počítače jednotka skládající se z pole buněk a a centrální procesorová jednotka s omezeným počtem registry. Každá paměťová buňka nebo registr může uložit skutečné číslo. Pod kontrolou programu může skutečná RAM přenášet reálná čísla mezi pamětí a registry a provádět aritmetické operace s hodnotami uloženými v registrech.

Povolené operace obvykle zahrnují sčítání, odčítání, násobení a dělení, stejně jako srovnání, ale ne modulus nebo zaokrouhlování na celá čísla. Důvodem, jak se vyhnout zaokrouhlování celých čísel a operacím modulu, je to, že umožnění těchto operací by mohlo poskytnout skutečné paměti RAM nepřiměřené množství výpočetního výkonu, což by jí umožnilo vyřešit PSPACE - kompletní problémy v polynomiálním čase.[2]

Při analýze algoritmů pro skutečnou RAM se obvykle předpokládá, že každá povolená operace bude trvat konstantní čas.

Implementace

Softwarové knihovny jako LEDA byly vyvinuty, které umožňují programátorům psát počítačové programy, které fungují, jako by běžely na skutečné RAM. Tyto knihovny představují skutečné hodnoty pomocí datové struktury které jim umožňují provádět aritmetiku a srovnání se stejnými výsledky, jaké by vyprodukovala skutečná RAM. Například v LEDA jsou reálná čísla reprezentována pomocí leda_real datový typ, který podporuje k-té kořeny pro jakékoli přirozené číslo k, racionální operátory a operátory porovnání.[3] Časovou analýzu základního algoritmu reálné RAM pomocí těchto skutečných datových typů lze interpretovat jako počítání počtu volání knihovny potřebných daným algoritmem.[4]

Související modely

Skutečná RAM se velmi podobá té pozdější Stroj Blum – Shub – Smale.[5] Skutečná RAM se však obvykle používá pro analýzu konkrétních algoritmů v výpočetní geometrie, zatímco stroj Blum – Shub – Smale místo toho tvoří základ pro rozšíření teorie NP-úplnost k výpočtu reálného čísla.

Alternativou ke skutečné RAM je slovo RAM, ve kterém se předpokládá, že jak vstupy do problému, tak hodnoty uložené v paměti a registrech jsou celá čísla s pevným počtem bitů. Slovo RAM model může provádět některé operace rychleji než skutečná RAM; například umožňuje rychle celočíselné třídění algoritmy, zatímco třídění na skutečné RAM musí být prováděno pomaleji srovnávací třídění algoritmy. Některé problémy s výpočetní geometrií však mají vstupy nebo výstupy, které nelze přesně vyjádřit pomocí celočíselných souřadnic; viz například Konfigurace Perles, uspořádání bodů a úseček, které nemá celočíselné souřadnice.

Reference

  1. ^ Shamos, Michael Ian (1978), Výpočetní geometrie, Ph.D. disertační práce, Yale University.
  2. ^ Schönhage, Arnold (1979), „O síle strojů s náhodným přístupem“, Sborník ze šestého mezinárodního kolokvia o automatech, jazycích a programování (ICALP '79), Přednášky z informatiky, 71, Springer, str. 520–529, doi:10.1007/3-540-09510-1_42, ISBN  978-3-540-09510-1, PAN  0573259.
  3. ^ Melhorn, Kurt; Näher, Stefan (1999). Platforma LEDA kombinatorických a geometrických výpočtů. Cambridge University Press. Citováno 12. listopadu 2019.
  4. ^ Mehlhorn, Kurt; Schirra, Stefan (2001), "Přesný výpočet s leda_real„Teoretické a geometrické aplikace“ (PDF), Symbolické algebraické metody a ověřovací metody (Dagstuhl, 1999), Springer, str. 163–172, doi:10.1007/978-3-7091-6280-4_16, ISBN  978-3-211-83593-7, PAN  1832422.
  5. ^ Blum, Lenore; Shub, Mike; Smale, Steve (1989), „K teorii výpočtu a složitosti reálných čísel: NP-úplnost, rekurzivní funkce a univerzální stroje“, Bulletin of the American Mathematical Society, 21 (1): 1–46, doi:10.1090 / S0273-0979-1989-15750-9, Zbl  0681.03020.

externí odkazy