Аппаратные и программные



Download 3,23 Mb.
Pdf ko'rish
bet85/179
Sana24.02.2022
Hajmi3,23 Mb.
#234030
TuriУчебное пособие
1   ...   81   82   83   84   85   86   87   88   ...   179
3.2.4 Полнота по Тьюрингу 
В теории вычислимости
2
исполнитель (множество вычисляющих 
элементов) называется тьюринг-полным, если на нём можно реализовать 
любую вычислимую функцию. Другими словами, для каждой вычислимой 
функции существует вычисляющий её элемент (например, машина Тьюринга) 
или программа для исполнителя, а все функции, вычисляемые множеством 
вычислителей, являются вычислимыми функциями (возможно, при некотором 
кодировании входных и выходных данных). Название пошло от Алана 
Тьюринга, который придумал абстрактный вычислитель - машину Тьюринга и 
дал определение множества функций, вычислимых посредством машин 
Тьюринга. Большинство широко используемых языков программирования - 
тьюринг-полные. Это касается как императивных языков, таких как Паскаль, 
так и функциональных (Haskell) и языков логического программирования 
(Prolog). Полными по Тьюрингу являются также грамматики общего вида. 
Примерами неполных по Тьюрингу формализмов являются конечные автоматы, 
примитивно рекурсивные функции, контекстно-свободные и регулярные 
грамматики. 
3.2.5 Модель вычислений
Модель вычислений, вычислительная модель (model of computation, MOC) 
– набор законов взаимодействия элементов вычислительной системы.
Модель вычислений – набор правил организации вычислительного 
процесса, в рамках которых возможен его формальный анализ.
Модель вычислений – набор формальных правил, в рамках которых 
организована взаимосвязь и поведение множества составляющих атомарных 
частей модели некоторой вычислительной системы.
2
Теория вычислимости – это раздел современной математики и теории вычислений, возникший в 
результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена 
вычислимым и невычислимым функциям и сравнению различных моделей вычислений. Сейчас поле 
исследования теории вычислимости расширилось - появляются новые определения понятия вычислимости и 
идёт слияние с математической логикой, где вместо вычислимости и невычислимости идёт речь о доказуемости 
и недоказуемости (выводимости и невыводимости) утверждений в рамках каких-либо теорий. 


138 
Модель вычислений – строго определенная парадигма (набор правил), 
описывающая протекание вычислительного процесса, способы обмена 
данными, взаимодействия между отдельными функциональными элементами.
Модель вычислений – недвусмысленный формализм для представления 
спецификаций проекта и проектных решений.
Модель вычислений – математическая модель, демонстрирующая 
пользователю вычислительные возможности вычислителя и правила их 
использования. 
Теория вычислимости и теория сложности вычислений трактует модель 
вычисления не только как определение множества допустимых операций, 
использованных для вычисления, но также и относительных издержек их 
применения. Охарактеризовать необходимые вычислительные ресурсы время 
выполнения, объём памяти, а также ограничения алгоритмов или компьютера 
можно только в том случае, если выбрана определённая модель вычислений. В 
модельно-ориентированной инженерии модель вычислений и её выбор дают 
ответ на вопрос, как ведёт себя система в целом, если известно поведение её 
отдельных частей. При асимптотической оценке сложности вычислений модель 
вычислений определяется через допустимые примитивные операции, для 
каждой из которых известна её цена. 
Известен целый ряд моделей вычислений, зависящих от набора 
применяемых операций и их вычислительной сложности. Они распадаются на 
следующие большие категории: абстрактные машины (абстрактные 
вычислители), используемые для доказательства вычислимости и получения 
верхней границы вычислительной сложности алгоритма и модели принятия 
решений, используемые для получения нижней границы сложности 
вычислений для алгоритмических задач. 
Примеры языков принадлежащих различным моделям вычислений: 
• Си, Pascal, Ada – императивная модель или модель Фон-Неймана; 
• VHDL, Verilog – модель дискретных событий; 
• Prolog, Рефал – сентенциональная модель; 
• XML – иерархическая модель данных; 
• SQL – реляционная модель; 
• Lisp – функциональная модель [40]. 

Download 3,23 Mb.

Do'stlaringiz bilan baham:
1   ...   81   82   83   84   85   86   87   88   ...   179




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish