Устройство машины Тьюринга
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
- Учебно-методический комплекс дисциплины для обучающегося «Информатика» для всех специальностей
- Силлабус дисциплины для студентов
- 1. Информация о дисциплине
- 2. Краткое описание дисциплины.
- 3. Пререквизиты дисциплины
- 4. Постреквизиты дисциплины
- 5. Календарно-тематический план.
- 6. Литература для изучения
- 7. Критерии оценки
- 8. Требования преподавателя
- 2. Тезисы лекций
- Тема 1. Информатика – предмет и задачи. Основные категории и понятия информатики
- Роль информатики в информационном обществе
- Тема 2. Начала общей теории информации. Понятие информации.
- Тема 3. Арифметические основы информатики. Формы представления информации. Системы счисления. Действия в различных системах счисления.
- Тема 4. Логические основы информатики
- Тема 5 . Архитектура персонального компьютера. Информационно-логические основы построения
- Тема 6. Алгоритмические основы информатики
- 6.1 Понятие алгоритма, его основные свойства
- 6.2. Машина Тьюринга и машина Поста
- Устройство машины Тьюринга
- Описание машины Тьюринга
- Тема 7.Основные конструкции программирования. Структурное программирование. Процедурное программирование. Объектно-ориентированное программирование.
- Тема 8. Состояние и тенденции развития программного обеспечения
- Тема 9. Операционные системы. Роль операционной системы в организации работы пользователя на персональном компьютере. Операционные системы и их основные функции
- Классификация ос
- Тема 10. Операционная система ms-dos
- Тема 11. Операционные системы Windows. Концепция операционных систем Windows.
- Объекты Windows
- Тема 12. Сервисное программное обеспечение. Общие сведения об архивации файлов. Программы-архиваторы.
- Программы архивирования данных
- Тема 13. Прикладные программные продукты. Классификация прикладного программного обеспечения.
- Тема 14. Тестовый процессор ms Word
- 14.1. Система обработки текстов (основные возможности, классификация). Ms Word. Элементы экрана.
- Установка основных параметров шрифта
- 14.2. Оформление текста. Работа с таблицей. Вставка файла, рисунка. Редактор формул ms Equation.
- Математические операторы и операторы сравнения
- Тема 15. Табличный процессор ms Excel
- 15.1. Назначение основные возможности Excel. Элементы экрана
- Добавление пиктограмм в одно из пиктографических меню
- Рабочие таблицы Excel предназначены для анализа данных, представленных в строках и столбцах. Они хранятся в файлах, которые называются рабочими книгами.
- Правка Перейти адрес клетки переход в нужную клетку
- 15.2. Режим вычисления. Оформление таблиц. Оформление таблиц. Печать. Диаграмма.
- 15.3. Работа с большими таблицами. Справочная система ms Excel.
- Тема 16. Использование спп Power Point для создания бизнес плана. Информационные системы (ис). Создание презентации. Оформление.
- Тема 17. Основы технологии работы в субд ms Access
- Тема 18. Сеть Internet и ее применение. Основные понятия Internet. Программа Internet Explorer. Поиск информации. Поисковые системы. Почта.
- Тема 19. Компьютерные вирусы и приемы борьбы с ними (понятие компьютерного вируса, средства защиты, методика защиты).
- Лабораторная работа №4 Создание прайс-листа счёта
- Лабораторная работа №5 Статистические расчеты Microsoft Excel.
- Пуск – Программы - Microsoft Access
- 2.1.1 Запрос, отбирающий данные из одной таблицы по условию
- 2.2 Запросы, которые отбирают данные из нескольких таблиц
- 2.3 Модификация данных с помощью запросов
- 2.3.1 Запросы, которые изменяют значение группы записей
- Тема: Создание форм
- 3.1 Создание форм для просмотра и ввода данных
- 3.2.Создание форм с подчиненной формой
- Краткое описание семинарских и практических занятий (планы, задания для проведения семинарских и практических занятий, срсп, срс)
- Задания для самопроверки и подготовки к экзамену, в том числе тесты
- В) объединение
- 6. Перечень основной и дополнительной литературы, в том числе на электронных носителях
- Дополнительная литература
- Справочная литература
- Нормативная литература
- Интернет-источники
- Глоссарий