49379 (572324), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

При манипуляциях с лентой используют следующие обозначения:

Л - движение ленты влево;

П - движение ленты вправо;

С - нет движения ленты.

Машина Тьюринга называют стандартной, если при сдвиге ленты может предварительно изменять состояние воспринимаемой ячейки.

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

Машина Тьюринга считается заданной, если заданы:

• её внешний и внутренний алфавиты;

• программа;

• начальная конфигурация;

• символы обозначающие пустую ячейку и заключительное состояние.

В универсальной Машине Тьюринга, как и во всякой тьюринговой машине, информация изображается символами, расположенными одновременно на магнитной ленте. При этом универсальная машина Тьюринга может располагать лишь фиксированным конечным внешним алфавитом. Между тем она должна быть приспособлена к приёму в качестве исходной информации всевозможных состояний устройства управления и конфигураций, в которых могут встречаться символы из разнообразных алфавитов со сколь угодно большим числом различных символов.

Это достигается путём кодирования конфигураций и программы любой данной машины Тьюринга в символах входного (внешнего) алфавита универсальной машины. Само кодирование должно выполняться следующим образом:

1 различные символы должны заменяться различными кодовыми группами, но один и тот же символ должен заменяться всюду, где бы он ни встречался, одной и той же кодовой группой;

2 строки кодовых записей должны однозначным образом разбиваться на отдельные кодовые группы;

3 должна иметь место возможность распознать, какие кодовые группы соответствуют различным сдвигам, т.е. каждой из букв Л, П, С в отдельности, и различать кодовые группы, соответствующие символам внутреннего алфавита и символам внешнего алфавита.

Таким образом, машина Тьюринга может рассматриваться как одна из программ для универсальной машины Тьюринга.

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

Современные электронные вычислительные машины строятся как универсальные: в запоминающее устройства наряду с исходными данными поставленной задачи вводятся также и программа её решения. Однако в отличие от машины Тьюринга, в которой внешняя память бесконечна, в любой реальной вычислительной машине она конечна.

4. Опишите основные форматы представления графических данных

В повседневной жизни мы обычно сталкиваемся с двумя типами изображений: рисунками и фотографиями. Компьютерная графика работает с теми же типами иллюстраций. Только фотография здесь именуется растровой графикой, а рисунок - векторной графикой.

Векторная графика (изображения в форматах CDR, AI) - это рисунок, созданный с помощью графических объектов, которые можно описать математическими формулами. Эти картинки, которые пользователь создает в специализированной программе(например, CorelDraw или Abode Illustrator), устроены на манер детского конструктора. Каждое векторное изображение состоит из массы объектов: кривых и прямых линий, хотя на глаз выглядит как единая, цельная картинка. Чтобы убрать или изменить любой объект, достаточно несколько раз щелкнуть мышью.

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

В издательском деле векторная графика используется в основном при подготовке рекламных объявлений, требующих красивого текстового оформления - ведь компьютерные шрифты тоже является векторными объектами…

Растровая графика (изображения в форматах JPG, BMP, TIFF,GIF, PNG) - самый популярный формат для хранения уже готовых изображений. Растровая графика более реалистична по сравнению с векторной, её нетрудно создать - достаточно отсканировать любое понравившееся изображение. Однако редактировать, изменения такую картинку не так-то просто. Ведь растровая картинка для компьютера существует как некий единый объект.

Поговорим о форматах растровых изображений. Ведь каждый из них имеет свои особенности и предназначен для достижения совершенно определённых целей.

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

JPG - В том случае, когда размер картинки куда важнее качества изображения используется формат JPG, позволяющий сжать исходную картинку в десятки раз. При этом формат JPG позволяет использовать различные степени сжатия, балансируя на грани между качеством и объёмом.

GIF - третий из форматов - лидеров растровой графики был специально для Интернета и до сих пор с успехом используется в Сети. Формат GIF позволяет пользователю ограничить палитру используемых цветов - взамен сотен тысяч и миллионов остаётся лишь 64, 128 или 256… Хорошей полноценной фотографии такие эксперименты на пользу не идут - цвета даже при максимальной палитре в этом формате становятся грубыми, само изображение - зернистым… Именно в этом формате создаётся большинство "украшалочек" для страниц Интернет - кнопки, рекламные заставки, элементы фона и так далее.

Понятно, что для каждого типа графики необходимо использовать разные редакторы. Растровой графикой ведают Adobe Photoshop и Corel Photo-Paint, а для векторной необходимо обзавестись CorelDraw или Adobe Illustrator. Существуют и универсальные пакеты - например, Jasc Paint Shop Pro, - однако их возможности несколько скромнее.

К числу домашних программ нельзя отнести ни Photoshop, ни CorelDraw, хотя пользователи могут установить этих монстров на домашние компьютеры, где эти программы благополучно бездействуют. А если и работают, то не вполсилы даже, а так, процентов на десять…

5. Список используемой литературы

1. Информатика: Базовый курс / С.В. Симонович и др. - СПб.: Питер, 2001-640с.

2. Информатика: Учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. - 2-е изд., стер. - М.: Издательский центр "Академия", 2003. - 816c.

3. Степанов А.Н. Информатика: Учебник для вузов.4-е изд. - СПб.: Питер, 2005-684с.

4. Латонин Л.А., Макаренков Ю.А. Николаева В.В., Столяр А.А. Математическая логика под редакцией Столяра А.А. издательство Минск высшая школа 1991г.

5. Леонтьев В.П. Новейшая энциклопедия персонального компьютера 2003. М.: ОЛМА-ПРЕСС, 2003. - 920с.: ил.

Характеристики

Список файлов ответов (шпаргалок)