Model obliczeń - Model of computation

Aby zapoznać się z modelami komputerowymi symulującymi złożone systemy, zobacz Model obliczeniowy .

W informatyce , a dokładniej w teorii obliczalności i teorii złożoności obliczeniowej , model obliczeniowy to model, który opisuje, w jaki sposób obliczane są dane wyjściowe funkcji matematycznej, biorąc pod uwagę dane wejściowe. Model opisuje sposób organizacji jednostek obliczeń, pamięci i komunikacji. Złożoność obliczeniowa o algorytm może być zmierzone dane model obliczeń. Korzystanie z modelu pozwala na badanie wydajności algorytmów niezależnie od odmian, które są specyficzne dla poszczególnych implementacji i konkretnej technologii.

Modele

Modele obliczeniowe można podzielić na trzy kategorie: modele sekwencyjne, modele funkcjonalne i modele współbieżne.

Modele sekwencyjne obejmują:

Modele funkcjonalne obejmują:

Modele współbieżne obejmują:

Niektóre z tych modeli mają zarówno warianty deterministyczne, jak i niedeterministyczne . Modele niedeterministyczne nie są przydatne do obliczeń praktycznych; są wykorzystywane w badaniu złożoności obliczeniowej algorytmów.

Modele różnią się siłą wyrazu; na przykład każda funkcja, która może być obliczona przez maszynę skończoną, może być również obliczona przez maszynę Turinga , ale nie odwrotnie.

Zastosowania

W dziedzinie analizy algorytmów w czasie wykonywania powszechne jest określanie modelu obliczeniowego w kategoriach dozwolonych operacji prymitywnych, które mają koszt jednostkowy, lub po prostu operacji kosztu jednostkowego . Powszechnie używanym przykładem jest maszyna o dostępie swobodnym , która ma koszt jednostkowy dostępu do odczytu i zapisu do wszystkich komórek pamięci. Pod tym względem różni się od wspomnianego modelu maszyny Turinga.

Kategorie

Istnieje wiele modeli obliczeń, różniących się zbiorem dopuszczalnych operacji i kosztem ich obliczeń. Należą do następujących szerokich kategorii:

Zobacz też

Bibliografia

Dalsza lektura