Нормальный алгоритм
Один из способов уточнения содержательного понятия алгоритма, рассматриваемых в теории алгоритмов (см. Теория алгоритмов). Схема нормального алгоритма была предложена советским логиком Л. А. Марковым. Поэтому нормальные алгоритмы называют также алгоритмами Маркова или нормальными алгоритмами Маркова.
Нормальные алгоритмы оперируют со словами конечной длины, преобразуя их друг в друга с помощью подстановок, т. е. замены одних частей слова на другие. Этот процесс очень напоминает процедуру выполнения заданий типа: "Путем замены букв в слове по одной превратить слово "слон" в слово "муха". Если бы процесс такого преобразования описывался алгоритмом Маркова, то было бы сказано, что он работает над алфавитом русского языка, а используемые им подстановки имеют вид:
, где х и у - какие-то буквы русского алфавита.
Для нормального алгоритма надо задать алфавит, над которым он работает, конечное множество допустимых подстановок, а также порядок их применения. Множество подстановок нужного нам алгоритма могло бы выглядеть, например, так:
Порядок применения подстановок задается с помощью следующего правила, одинакового для всех нормальных алгоритмов. Для исходного слова взять первую подстановку. Если ее левая часть имеется в исходном слове, то произвести замену ее первого вхождения в слово на правую часть подстановки. Если первая подстановка к исходному слову применена быть не может, то проверяется следующая по порядку подстановка. Если никакая из подстановок к исходному слову неприменима, то процесс преобразования завершен. Если некоторая подстановка оказалась использованной, то необходимо проверить, нет ли в правой части специального знака "!". Если его нет, то слово, получившееся после преобразования, снова считается исходным и весь процесс начинается заново. Если же знак "!" есть, то процесс преобразования прекращается.
Применим теперь нормальный алгоритм с приведенными подстановками для исходного слова "слон". Первая подстановка к нему неприменима, так как в исходном слове нет буквы "я". Вторая подстановка применима, и слово "слон" превращается в результате ее использования в слово "суон". Поскольку в правой части второй подстановки нет знака "!", то слово "суон" становится исходным и к нему снова надо применять первую подстановку. Но ни она, ни вторая подстановка теперь не могут быть использованы, а третья подстановка превращает "суон" в новое исходное слово - "муон". Далее процесс протекает аналогично, и вскоре в качестве исходного слова возникает слово "муха". К нему оказывается неприменимой ни одна из подстановок алгоритма, и действие алгоритма завершается.
Если бы исходное слово было другим, то алгоритм работал бы иначе. Например, слово "ветер" преобразуется им в слово "берет", а шестая подстановка из-за наличия знака "!" не дает продлиться процессу дальше и превратить "берет" в "бетет" и преобразовывать его далее.
В общей схеме нормального алгоритма нет нужды ограничиваться лишь отдельными буквами. Подстановки имеют вид: , где слева и справа стоят конечные слова произвольной длины в том алфавите, над которым работает алгоритм.
В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальные алгоритмы эквивалентны машинам Тьюринга и другим формальным моделям, уточняющим интуитивное понятие алгоритма.
- 032900 – Русский язык и литература;
- 032600 – История;
- 033200 – Иностранный язык;
- Пояснительная записка
- 032900 – Русский язык и литература;
- 032600 – История;
- 033200 – Иностранный язык;
- Программа курса
- Математические и логические основы информатики.
- II. Арифметические и логические основы персонального компьютера.
- III. Теория алгоритмов и формальных грамматик.
- IV. Программные средства персонального компьютера.
- Учебный план
- I лекции (20 часов)
- Методические указания к лекциям
- Лекция 1
- Лексические функции как пример математизации объектов лингвистики
- Функция как математическое понятие
- Функция в лексике
- Отличие лексической функции от числовой
- Обозначение
- «Склеенные» функции
- Типы лексических функций
- Возможности использования лексических функций
- Лекция 2-3 Алгебра высказываний. Логические функции. Законы булевой алгебры
- Лекция 4 Перевод чисел из одной позиционной системы счисления в другую. Арифметика в различных системах счисления.
- Лекция 5 Количество информации
- Лекция 6 Архитектура эвм
- 4. Алгоритм решения любой задачи представляется в виде последовательности слов, называемых командами, которые определяют наименование операции и слова информации, участвующие в операции.
- Устройство процессора
- Лекция 7 Алгоритм
- Нормальный алгоритм
- Лекция 9 Понятие операционных систем
- Приложение к лекции 1 Синтаксический граф
- Синтаксическое дерево
- Типы синтаксических деревьев
- Дерево подчинения
- Стилистическая диагностика Индивидуальный синтаксис писателя
- Перевод особенностей авторского стиля на формальный язык синтаксических деревьев
- Пушкинская, лермонтовская и гоголевская фразы — сходства и различия
- Компьютерный практикум.
- Частотный анализ в филологических исследованиях (на базе словарей)
- Работа с программой PhotoShop 6
- Создание шаблона титульного листа диплома в программе word. Лабораторная работа № 1. Изучение макрокоманд программы Word
- Общие навыки Включение компьютера
- Нажатие левой клавиши устройства «Мышь».
- Установка текстового курсора в нужную позицию
- Работа с оконным интерфейсом операционной системы Windows
- Переход на вкладку в окне.
- Работа с файловой системой операционной системы Windows 2000 Открытие окна Microsoft Word.
- Закрытие окна программы Microsoft Word
- Сохранение документа (файла) на диске.
- Создание новой папки.
- Открытие папки.
- Поиск нужной папки
- Открытие документа.
- Создание нового документа
- Копирование выделенного объекта.
- Вырезание выделенного объекта.
- Вставка скопированного (вырезанного) объекта.
- Работа с файловой системой операционной системы Windows 2003 Открытие окна программы Microsoft Word
- Закрытие окна программы Microsoft Word
- Создание новой папки.
- Открытие папки.
- Поиск нужной папки
- Открытие документа.
- Сохранение документа (файла) на диске.
- Создание нового документа
- Копирование выделенного объекта в буфер обмена.
- Вставка скопированного (вырезанного) объекта из буфера обмена.
- Работа в программе Word Форматирование текста Установка автоматического переноса слов.
- Установка параметров страницы.
- Нумерация страниц.
- Установка левой границы текста с помощью бегунка
- Установка параметров абзаца.
- Установка режима выравнивания.
- Установка размера шрифта (кегля).
- Выбор гарнитуры шрифта
- Установка типа шрифта
- Переход в режим набора текста курсивом (полужирным, с подчеркиванием).
- Отмена набора текста курсивом (полужирным, с подчеркиванием).
- Выделение текста (строки, слова, символа).
- Гашение выделения текста (строки, слова, символа).
- Изменение регистра букв текста
- Изменение настройки автотекста: «Делать первые буквы предложений прописными.»
- Маркировка и нумерация списка
- Установка уровня вложенности заголовка.
- Создание оглавления
- Вставка объектов Вставка рисунка из библиотеки рисунков.
- Перемещение объекта
- Выделение объекта иди группы объектов
- Вырезание выделенного объекта.
- Изменение размера картинки
- Вставка надписи.
- Выделение надписи.
- Заведение текста в надпись
- Изменение размера надписи
- Создание эффекта тени сзади надписи.
- Установка режимов обтекания текстом картинок.
- Установка режимов обтекания текстом объектов.
- Вставка подписи к рисункам
- Группировка объектов
- Рисование стрелок и отрезков прямых линий.
- Удаление объекта
- Изменение направления текста в надписи.
- Закрашивание фона надписи
- Работа с таблицами Вставка таблицы
- Выделение ячеек таблицы.
- Вызов редактора формул.
- Статистика Установка параметра проверки статистика удобочитаемости.
- Подсчет количества вхождений заданного фрагмента текста в документ.
- Выполнить сканирование и распознавание документов в программе Fine Reader 7.
- Лабораторная работа №2 Создание текстового документа в редакторе Microsoft Word.
- Лабораторная работа № 3 Набор филологических текстов.
- Лабораторная работа №4 Создание таблиц.
- Лабораторная работа № 5 Вставка объектов (рисунков и надписей) в текст.
- Система высшего и центрального управления в Российской империи в первой половине XIX в.
- Лабораторная работа 6. Набор математических объектов и формул.
- Лабораторная работа № 7 Анализ удобочитаемости текста. Выбор тематической и удобочитаемой литературы с помощью команд программы Microsoft Word.
- § 1. Сущность методов осуществления целостного педагогического процесса и их классификация
- Задание 3 .Выбор удобочитаемого тематического текста из сети Интернет с помощью команд программы Microsoft Word.
- Лабораторная работа № 8 Расчет простых и сложных процентов
- Основные определения.
- Задача №1:
- Задания для самостоятельной работы:
- Лабораторная работа № 9 Расчеты итоговых сумм выплат при покупках в кредит
- Основные определения.
- Лабораторная работа № 10 Частотный анализ поэтических текстов по начальной букве
- Лабораторная работа №11 Частотный анализ поэтических текстов по всем буквам.
- Лабораторная работа № 12 Частотный анализ при обработке исторических фактов и географических названий.
- Строка заголовков столбцов
- Лабораторная работа № 13 Частотный анализ в филологических исследованиях (на базе словарей)
- Лабораторная работа № 14 Создание иллюстративных материалов к уроку с помощью программы Power Point –2000 с использованием Internet ресурсов.
- Лабораторная работа №15 Работа с программой PhotoShop 6
- Лабораторная работа № 16 Обработка материалов тестовых опросов в программе excel
- Лабораторная работа № 17 Создание шаблона титульного листа диплома в программе word.