Контрольная работа: Формирование запроса в поисковике. Расчеты в MS EXCEL. Машина Тьюринга
Все эти различные виды документов, располагающихся на отдельных листах Excel, могут объединяться в рамках более сложной структуры - книги. Книга - это основной тип документа. Книга состоит из нескольких листов, каждый из которых может представлять из себя отдельный документ. Механизм связей Excel безотказно работает в пределах не только одного листа, но и целой книги. Изменения, внесенные в один из листов, приведут к автоматическому изменению диаграммы и значений в других листах-таблицах.
Кроме взаимосвязи ячеек друг с другом, Excel предоставляет пользователям другое мощное оружие - богатейшие возможности сортировки. Вы можете выбрать сортировку по строкам или столбцам, задавать последовательность, в которой Excel будет представлять элементы вашей таблицы и выполнять множество других операций.
…Безусловно, описание функций и возможностей далеко не исчерпывают всего богатства Excel.
Есть ли у Excel альтернатива? В мире - сколько угодно. Россия, увы, может предпочесть разве что табличный модуль Лексиком-XL. Описывать отдельно эту программу нет необходимости. Скажем лишь, что разница между Excel и XL куда более значительна, чем между MicrosoftWord и Лексиконом.
Стоимость программы: 200 - 250 долларов (в базовой поставке MicrosoftOffice)
3. Опишите машину Тьюринга
Машина Тьюринга подобна машине Поста, но функционирует несколько иначе. В дальнейшем они стали называться машинами Тьюринга.
В общем случае такая машина состоит из следующих частей:
1 Информационной ленты, представляющей собой бесконечную (неограниченную) память машины. В качестве информационной ленты может служить магнитная или бумажная бесконечная лента, Разделённая на отдельные ячейки. В каждой ячейке можно поместить один символ, в том числе и ноль;
2 "Считывающей и пишущей головки" - специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль головки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в определённой ячейке ленты;
3 Управляющего устройства, которое в каждый рассматриваемый момент находится в некотором "состоянии". Состояние устройства управления часто называют внутренним состоянием машины. Одно из таких состояний называется заключительным и управляет окончанием работы машины.
В отличие от машины Поста машина Тьюринга может работать в произвольном конечном алфавите и выполнять некоторое конечное число приказов. При этом Машина Тьюринга, может сдвигать ленту на одну ячейку вправо или влево, оставляя содержимое ячеек неизменным, или могут изменять состояние воспринимаемой ячейки, оставляя ленту неподвижной.
При манипуляциях с лентой используют следующие обозначения:
Л - движение ленты влево;
П - движение ленты вправо;
С - нет движения ленты.
Машина Тьюринга называют стандартной, если при сдвиге ленты может предварительно изменять состояние воспринимаемой ячейки.
Совокупность всех команд, которые может выполнять машина, называется её программой.
Машина Тьюринга считается заданной, если заданы:
• её внешний и внутренний алфавиты;
• программа;
• начальная конфигурация;
• символы обозначающие пустую ячейку и заключительное состояние.
В универсальной Машине Тьюринга, как и во всякой тьюринговой машине, информация изображается символами, расположенными одновременно на магнитной ленте. При этом универсальная машина Тьюринга может располагать лишь фиксированным конечным внешним алфавитом. Между тем она должна быть приспособлена к приёму в качестве исходной информации всевозможных состояний устройства управления и конфигураций, в которых могут встречаться символы из разнообразных алфавитов со сколь угодно большим числом различных символов.
Это достигается путём кодирования конфигураций и программы любой данной машины Тьюринга в символах входного (внешнего) алфавита универсальной машины. Само кодирование должно выполняться следующим образом:
1 различные символы должны заменяться различными кодовыми группами, но один и тот же символ должен заменяться всюду, где бы он ни встречался, одной и той же кодовой группой;
2 строки кодовых записей должны однозначным образом разбиваться на отдельные кодовые группы;
3 должна иметь место возможность распознать, какие кодовые группы соответствуют различным сдвигам, т.е. каждой из букв Л, П, С в отдельности, и различать кодовые группы, соответствующие символам внутреннего алфавита и символам внешнего алфавита.
Таким образом, машина Тьюринга может рассматриваться как одна из программ для универсальной машины Тьюринга.
При изучении моделей вычислений обычно проводят различие между детерминированными и недетерминированными машинами Тьюринга. В детерминированной машине Тьюринга общий ход вычислений полностью определяется машиной Тьюринга (программой), начальным символом и начальными вводами с ленты. В недетерминированной машине Тьюринга на каждой стадии вычислений существуют альтернативы, т.е. она может работать в одном из нескольких режимов. При этом класс задач, решаемых на детерминированных машинах Тьюринга за полиноминальное время, называют классом Р, а класс задач, решаемых на недетерминированных машинах Тьюринга за полиноминальное время, - классом NP.