Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Тема 8.1 Определение класса финитно-поставленных задач.
|
|
Класс однотипных задач называется классом финитно-поставленных задач, если существует конечный алфавит А, словами которого можно закодировать условие и ответ любой задачи этого класса.
Класс финитно-поставленных задач можно свести к задаче вычисления значений некоторой функции на множестве N.
Пусть f(n) определена на N, закодируем все слова с помощью конечного алфавита А={а1, …аn} следующим образом: берем каждый символ и ставим ему в соответствие его порядковый номер.
, тогда если 
- слова, то
где р – все простые числа
При этом натуральное число является кодом, если оно делиться на все простые числа, начиная с 2 и заканчивая этим числом. Тогда если к – некоторый класс финитно-поставленных задач и существуют конечные алфавиты, словами которого можно закодировать условие и ответ, то задача сводиться к определению кода на множестве N.
Общий метод решения задач в данном случае имеет вид:
Задача → кодируем условие на N()→ вычисляем (
)→ декодируем ответ.
Функция 
- называется кодовой.
|
|