Здесь показаны различия между выбранной ревизией и текущей версией данной страницы.
|
tema:raboty_a._a._markova_po_teorii_algorifmov [2009/04/27 10:20] sim |
tema:raboty_a._a._markova_po_teorii_algorifmov [2009/04/27 10:37] (текущий) sim |
||
|---|---|---|---|
| Строка 27: | Строка 27: | ||
| Нормальные алгоритмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгоритма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая верхняя. Если эта формула подстановки имеет вид ** L --> D** , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгоритма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид** L --> D** , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDS считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге. | Нормальные алгоритмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгоритма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая верхняя. Если эта формула подстановки имеет вид ** L --> D** , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгоритма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид** L --> D** , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDS считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге. | ||
| Например, в ходе процесса применения алгорифма с указанной выше схемой к слову | * | | последовательно возникают слова | b * | , ba | * | , a | * | , a | b * , aba | * , baa | * , aa | * , aa | c, aac, ac | и c | | , после чего алгоритм завершает работу с результатом | | . | Например, в ходе процесса применения алгорифма с указанной выше схемой к слову | * | | последовательно возникают слова | b * | , ba | * | , a | * | , a | b * , aba | * , baa | * , aa | * , aa | c, aac, ac | и c | | , после чего алгоритм завершает работу с результатом | | . | ||
| - | |||
| // | // | ||
| - | |||
| - | |||
| - | |||
| - | |||
| **Дополнительные матерьялы** | **Дополнительные матерьялы** | ||