Сводимость множеств. Креативные и продуктивные множества.

Многозначная сводимость

Доказывая неразрешимость некоторых множеств, мы часто пользовались следующим приемом: мы показывали что если бы существовал разрешающий алгоритм для данного множества, то мы имели бы разрешающий алгоритм для данного множества, например К. В общем виде этот прием называется сведением одной алгоритмической проблемы к другой. Понятию сведения можно придать точный смысл многими различными способами. Рассмотрим - многозначную сводимость.

Будем говорить что множество A многозначно сводиться к множеству B (), если существует тотальная вычислимая функция такая что

В этом случае будет говорить что А сводимо к В посредством функции f,а функцию f будем называть сводящей А к В.

Продуктивные множества

Дополнение множества К неперечислимо. Этот факт может быть выражен в более сильной форме: существует алгоритм, который позволяет по геделеву номеру x любого перечислимого подмножества W_x множества найти натуральное число из не принадлежащих W_x. А именно в качестве такого числа можно взять х. Действительно W_x . Предположим что х . Тогда х , что невозможно. Значит х , следовательно х . Это свойство множества приводит к следующему определению множество A наз-ся продуктивным, если существует одноместная вычислимая числовая функция. такая что

В этом случае функция наз-ся продуктивной для множества А.

Креативные множества

Множество A называется креативным (или творческим), если оно перечислимо, а его дополнение продуктивно. Самым простым примером креативного множества является множество К. Другим примером может служить множество

10 билет.

1. Основные понятия и определения: информация, данные, единицы информации, информационная система (ИС), информационная среда, информационные технологии (ИТ)

Информация (от лат. informatio — «разъяснение, изложение, осведомлённость») — сведения о чём-либо, независимо от формы их представления. В настоящее время не существует единого определения информации как научного термина. С точки зрения различных областей знания данное понятие описывается своим специфическим набором признаков. Понятие «информация» является базовым в курсе информатики, где невозможно дать его определение через другие, более «простые» понятия (так же, в геометрии, например, невозможно выразить содержание базовых понятий «точка», «прямая», «плоскость» через более простые понятия). Содержание основных, базовых понятий в любой науке должно быть пояснено на примерах или выявлено путём их сопоставления с содержанием других понятий. В случае с понятием «информация» проблема его определения ещё более сложная, так как оно является общенаучным понятием. Данное понятие используется в различных науках (информатике, кибернетике, биологии, физике и др.), при этом в каждой науке понятие «информация» связано с различными системами понятий.

В вычислительной технике ДАННЫЕ обычно отличают от программ. Программа является набором инструкций, которые детализируют вычисление или задачу, которая производится компьютером. Данными же традиционно называется всё, что не выступает в роли программы. Согласно принципу фон Неймана, имеющему место в большинстве современных компьютеров, одна и та же область памяти может содержать как программу (в частности, машинный код), так и иные данные, то есть и то и другое выражается в виде одинаковых информационных форм, как правило, в виде двоичного кода.

В языках высокого уровня данные воплощаются в виде переменных. Данные с точки зрения процесса (выполняемой программы) — содержимое части адресного пространства. Информация, вводимая в компьютер должна быть конкретной и однозначной. Издавна люди пользовались шифрами. Самыми простыми и удобными из них были цифровые шифры. Самая разнообразная информация - цвета, ноты, дни недели - может быть представлена в виде цифр. Для обработки компьютером любая информация кодируется с помощью цифр. Цифры представляются электрическими сигналами, с которыми работает компьютер. Для удобства различения в компьютере используют сигналы двух уровней. Один из них соответствует цифре 1, другой - 0. Цифры 1 и 0 называются двоичными. Они являются символами, из которых состоит язык, понимаемый и используемый компьютером. Т.о., любая информация в компьютере представляется с помощью двоичных цифр.

Наименьшей единицей информации является бит (от англ. bi nary digi t (bit)).

Бит- это количество информации, необходимое для однозначного определения одного из двух равновероятных событий. Один бит информации получает человек, когда он узнает, опаздывает с прибытием нужный ему поезд или нет, был ночью мороз или нет, присутствует на лекции студент Иванов или нет и т.д.

В информатике принято рассматривать последовательности длиной 8 бит. Такая последовательность называется байтом. С помощью одного байта можно записать двоичные коды 256 (2⁸) чисел от 0 до 255.

Единицы измерения информации: 1 байт=8 бит 1 килобайт (Кб) = 1024=2¹⁰ байт 1 мегабайт (Мб) = 1024 килобайт 1 гигабайт (Гб) = 1024 мегабайт 1 терабайт (Тб) = 1024 гигабайт

Например, если на странице текста помещаются в среднем 2500 знаков, то 1 Мбайт - это примерно 400 страниц, а 1 Гбайт - 400 тыс. страниц.

Стандарт ISO/IEC 2382-1 дает следующее определение: «Информационная система — система обработки информации, работающая совместно с организационными ресурсами, такими как люди, технические средства и финансовые ресурсы, которые обеспечивают и распределяют информацию»

Информационная среда - совокупность технических и программных средств хранения, обработки и передачи информации, а также социально-экономических и культурных условий реализации процессов информатизации.

Информацио́нные техноло́гии (ИТ, от англ. information technology, IT) — широкий класс дисциплин и областей деятельности, относящихся к технологиям создания, сохранения, управления и обработки данных, в том числе с применением вычислительной техники. В последнее время под информационными технологиями чаще всего понимают компьютерные технологии. В частности, ИТ имеют дело с использованием компьютеров и программного обеспечения для создания, хранения, обработки, ограничения к передаче и получению информации. Специалистов по компьютерной технике и программированию часто называют ИТ-специалистами.

Согласно определению, принятому ЮНЕСКО, ИТ — это комплекс взаимосвязанных научных, технологических, инженерных дисциплин, изучающих методы эффективной организации труда людей, занятых обработкой и хранением информации; вычислительная техника и методы организации и взаимодействия с людьми и производственным оборудованием, их практические приложения, а также связанные со всем этим социальные, экономические и культурные проблемы. Сами ИТ требуют сложной подготовки, больших первоначальных затрат и наукоемкой техники. Их внедрение должно начинаться с создания математического обеспечения, моделирования, формирования информационных хранилищ для промежуточных данных и решений.

2. Классификация задач исследования операций. По уровню информации о ситуации

Детерминированый уровень - наиболее простой уровень информации о ситуации - когда условия, в которых принимаются решения, известны полностью.

Стохастический уровень - уровень, при котором известно множество возможных вариантов условий и их вероятностное распределение.

Неопределенный уровень - уровень, когда известно множество возможных вариантов, но без какой-либо информации об их вероятностях.

По виду информационного состояния ЛПР: Если принятие решения происходит в наперед известном и не изменяющемся во времени информационном состоянии ЛПР, то задачу исследования операций называют статической, а вся процедура принятия решения может быть реализована за один этап.

Если в процессе принятия решения информационное состояние ЛПР изменяется во времени, то задачу ИО называют динамической. В этом случае зачастую наиболее целесообразной является поэтапная процедура принятия решения.

3. Рекурсивная функция. Оператор минимизации.

Рекурсивные функции очень хорошо иллюстрируют понятие алгоритма. Если рассуждать упрощенно, то для рекурсивной функции должен существовать алгоритм, вычисляющей ее значения. Вообще говоря, большая часть известных числовых функций являются рекурсивными. Полезно вспомнить, как определяются Элементарные функции. Вначале рассматривается несколько классов функций: алгебраические, тригонометрические, показательные, логарифмические. Элементарная функция определяется как Суперпозиция (или сложная функция) этих функций.

Рекурсивные функции строятся аналогичным образом.

Операция минимизации по -ой переменной функции обозначается следующим образом: , и определяется так.

Рассмотрим уравнение относительно :

. (1)

Это уравнение решается подбором, вместо переменной последовательно подставляются 0,1,2,… При этом возможны случаи.

· На некотором шаге левая часть соотношения (1) не определена. Следовательно, на наборе операция минимизации не определена.

· На каждом шаге левая часть соотношения (1) определена, но равенство не выполняется ни при каких значениях . Следовательно, на наборе операция минимизации не определена.

· Левая часть соотношения (1) определена при , но при равенство не выполняется, а при выполняется. В этом случае число считается значением операции минимизации на наборе .

Пример. [13]. Найти функции, получаемые из данной числовой функции с помощью оператора минимизации по каждой ее переменной.

Решение. Минимизируем функцию по переменной . Рассмотрим уравнение

. (2)

1. Если , , то при подстановке получаем верное равенство.

2. Если , то левая часть равенства (2) не определена.

3. Если , , то при подстановке в левой части равенства (2) появляется выражение , не имеющее смысла, и в этом случае операция минимизации не определена.

4. Если , то получаем равенство . Оно имеет смысл при , то есть , что рассмотрено в первом пункте, и при , то есть . При равенство не имеет смысла.

Таким образом,

Минимизируем функцию по переменной . Рассмотрим уравнение

.

Это уравнение на самом первом шаге, при подстановке вместо нуля теряет смысл, значит, операция минимизации по второй переменной нигде не определена.

Минимизируем функцию по переменной . Рассмотрим уравнение

. (3)

Если левая часть соотношения (3) имеет смысл и равенство (3) выполнено, то оно выполнено и при подстановке в это соотношение переменной на первом шаге, то есть при . В остальных случаях значение операции минимизации не определено.

Определение. Частично-рекурсивной функцией называется числовая функция, получаемая за конечное число шагов из простейших примитивно-рекурсивных функций с помощью операторов суперпозиции, примитивной рекурсии и минимизации.

Определение. Числовая функция называется Общерекурсивной, если она частично-рекурсивна и всюду определена.

Билет № 12

1. Новые информационные технологии в обучении: дидактические проблемы, перспективы использования. История становления информатики как науки.

СНИТ

Одним из приоритетных направлений процесса информатизации современного общества является информатизация образования - процесс обеспечения сферы образования методологией и практикой разработки и оптимального использования современных или, как их принято называть, новых информационных технологий (НИТ), ориентированных на реализацию психолого-педагогических целей обучения, воспитания.

Под средствами новых информационных технологий (СНИТ) будем понимать программно-аппаратные средства и устройства, функционирующие на базе микропроцессорной, вычислительной техники, а также современных средств и систем информационного обмена, обеспечивающие операции по сбору, продуцированию, накоплению, хранению, обработке, передаче информации.

К СНИТ относятся ЭВМ, ПЭВМ; комплекты терминального оборудования для ЭВМ всех классов, локальные вычислительные сети, устройства ввода-вывода информации, средства ввода и манипулирования текстовой и графической информацией, средства архивного хранения больших объемов информации и другое периферийное оборудование современных ЭВМ; устройства для преобразования данных из графической или звуковой форм представления данных в цифровую и обратно; средства и устройства манипулирования аудиовизуальной информацией (на базе технологии Мультимедиа и систем "Виртуальная реальность"); современные средства связи; системы искусственного интеллекта; системы машинной графики, программные комплексы (языки программирования, трансляторы, компиляторы, операционные системы, пакеты прикладных программ и пр.) и др.

Дата добавления: 2015-10-24