Описание алгоритма как формализованное знание: словарь — авторское изложение

ru · official · sha256:ba756aba5d380b66da57a4d8c7a41a1b76f02db1a81e731179ad36702f14f722RU

§1. Задача, вход, выход и предусловия Алгоритм описывается ОТНОСИТЕЛЬНО задачи. Задача формулируется независимо от способа её решения: что дано, что требуется получить и при каких условиях требование осмысленно. Одну задачу решает, как правило, несколько алгоритмов, и сравнение их между собой возможно только через общую задачу. Вход задачи — перечень предъявляемых объектов с указанием их природы. Выход — то, что описание обязуется получить. Предусловие — условие, при нарушении которого описание не обещает ничего: алгоритм вне своих предусловий не «работает хуже», он не определён. Предусловия алгоритма отделяются от предусловий задачи. Задача «найти наибольший общий делитель» осмысленна для любой пары целых, не равных нулю одновременно; алгоритм, записанный для неотрицательных чисел, несёт СВОЁ дополнительное предусловие, и это свойство изложения, а не задачи.

Referencing norms: BoundsStated, EdgeCaseLine, PreconditionLine, ProblemCard, ProblemInputLine, ProblemOutputLine, ProblemPreconditionLine, ProblemStated

ru · official · sha256:d34f261a85c8edbfb7a76f42f98eab00b27f57e8b29eae0a1da84757383c7d4dRU

§10. Варианты и условия их применимости Вариант — самостоятельное описание, решающее ту же задачу иным способом либо иным устройством того же способа. Выбор варианта фиксируется изложением: описываются шаги ОДНОГО варианта, а не общая идея нескольких. Условия применимости варианта — обстоятельства, при которых он предпочтителен либо единственно возможен: свойства входа, доступная память, требование устойчивости, ограничение на область значений. Свойства варианта называются перечислимо, чтобы сравнение двух вариантов одной задачи не требовало чтения прозы: устойчивость, работа на месте, основанность на сравнениях, детерминированность, пригодность к потоковой обработке, приспособляемость к частично упорядоченному входу.

Referencing norms: ApplicabilityLine, PropertyLine, SameProblem, VariantLine

ru · official · sha256:ca42033fefd5d2b0450474840ac7ca40ea17a7c26991086c9a1a931c9b893bcfRU

§11. Понятия и их зависимости Понятие — термин, употребляемый шагами и основаниями. Понятие несёт определение и может зависеть от других понятий. Совокупность понятий и зависимостей образует граф, в котором циклы возможны: два понятия допустимо определять взаимно, и такое определение остаётся определением. Шаг связывается с понятиями, без которых он не читается. Эта связь и есть ответ на вопрос «что здесь означает это слово»: раскрытие шага ведёт к понятию, раскрытие понятия — к его определению и к понятиям, от которых оно зависит.

Referencing norms: ConceptCard, ConceptCycle, ConceptLinkDirect, ConceptNoteLine, ConceptReachesDirect, ConceptReachesTransitive, StepConceptLine

ru · official · sha256:ce36abe2272618c45bbe8f5ce6f0b6d6d61d84388d309554adae465537b2c12cRU

§12. Источники и разграничение изложения У каждого описания называется происхождение: первая публикация алгоритма либо признанное изложение, с указанием автора, года и точного места. Байты сторонних публикаций настоящим представлением не закрепляются, если их закрепление не разрешено их условиями; названы локаторы, и закрепления не заявляется. Формулировка шагов, нумерация и выбор варианта принадлежат настоящему изложению. Утверждение о корректности и оценка сложности принадлежат источнику, если источник назван при них, и настоящему изложению в противном случае. Смешивать эти два не следует: читатель обязан знать, чьё утверждение он читает. Когда источники расходятся — используют разные определения, разные условия остановки, разные варианты одного алгоритма, — расхождение называется явно, а описание фиксирует ОДНО прочтение и говорит, какое.

Referencing norms: ConceptReferenceLine, LimitationLine, ReferenceLine, Sourced

ru · official · sha256:d2f09599b7d215e661ec74e4ab94663e50a8c9356a7f011aeac8a527aa7f0e18RU

§13. Полнота описания Описание считается полным, когда названы: задача с входом, выходом и предусловиями; выбранный вариант и условия его применимости; существенные крайние случаи; начальный шаг и достижимое завершение; формулировка каждого шага; основание каждого шага; инвариант и мера для каждого повторения; основание завершения; утверждение о корректности с его обоснованием; модель стоимости и хотя бы одна оценка; ссылка на источник; названные границы представления. Неполнота не есть ошибка: она есть измеримое состояние. Описание, у которого не названа мера при наличии цикла, отвечает на вопрос о завершении молчанием, и это молчание видно машине.

Referencing norms: Documented, InstructionAvailable

ru · official · sha256:308214fc88e34260ab9f8a0251b6d29920d8fbe97ac4661f9313aedfd3e45d07RU

§14. Описание и исполнение Настоящий словарь описывает предполагаемые действия. Ни один его элемент не утверждает, что действие выполнено, что вход предъявлен или что результат получен. Инструкция, построенная из описания, есть ответ на вопрос об устройстве алгоритма и не является протоколом вычисления. Там, где в репозитории существует исполнимый вычислитель того же алгоритма, описание называет его связью. Связь означает, что вычислитель реализует описанный вариант; она не означает, что вычислитель проверял описание либо что описание порождено из вычислителя.

Referencing norms: ImplementationLine

ru · official · sha256:7e8055cad882c63cc907ea841ccade21e00afe1e094f127d68e7a1089984df89RU

§2. Параметры, роли объектов, состояние и операции Параметр — именованная величина описания, значение которой в описании не названо: размер входа, основание системы счисления, порог перехода к другому способу. Роль — назначение объекта в описании: делимое, делитель, накопитель, указатель, граница диапазона. Состояние — то, что меняется по ходу выполнения и о чём говорят шаги: остаток, текущий индекс, содержимое очереди, накопленное частное. Операция — элементарное действие над состоянием, которое описание считает неделимым и не раскрывает дальше. Что считать неделимой операцией — выбор изложения, и он называется явно, потому что от него зависит модель стоимости (§9). Сравнение двух элементов, сложение двух чисел ограниченной разрядности и обращение к элементу массива по индексу — типичные неделимые операции; они неделимы по соглашению, а не по природе.

Referencing norms: OperationItem, ParameterItem, RoleItem, StateItem

ru · official · sha256:c81421aa7c1dc89632738a531f72130e490254420974290c55013af833cf6b41RU

§3. Шаги описания и их роды Шаг — единица описания, пронумерованная целым числом. Номер служит адресом: на шаг ссылаются переходы, инварианты, основания и раскрытия. Порядок номеров сам по себе порядком выполнения НЕ является — порядок задают переходы (§4). Различаются шесть родов шага. Подготовка вводит начальное состояние. Действие изменяет состояние. Ветвление проверяет условие и передаёт управление по одному из исходов. Повторение обозначает возврат к ранее выполненному шагу. Рекурсивный вызов передаёт управление тому же или другому описанию с изменённым входом. Результат объявляет выход и завершает выполнение. Род шага — свойство описания, а не текста его формулировки. Одна и та же фраза «повторять, пока остаток не станет равен нулю» может быть записана ветвлением с возвратом либо повторением; изложение выбирает одну запись и называет её.

Referencing norms: ExpandableByDetail, ExpansionLine, InstructionLine

ru · official · sha256:4ee3e24d723c0301b64458beaf2b277acb16e05b6aacced6c3c9d67ea9d2a50bRU

§4. Переходы: последовательность, ветвление, повторение и вызов Переход соединяет два шага и несёт род и условие. Последовательный переход выполняется без условия. Переход по истине и переход по лжи исходят из одного ветвления и несут взаимно исключающие условия. Переход возврата обозначает повторение. Переход вызова обозначает передачу управления другому описанию. Условие перехода записывается текстом и относится к состоянию, названному в §2. Условие, не выразимое через названное состояние, есть дефект описания: читатель не сможет проверить, какая ветвь выбрана. Совокупность шагов и переходов образует ГРАФ ОПИСАНИЯ. Этот граф допускает циклы и допускает вызовы самого себя. Он не является графом доказательства: доказательство удостоверяет состоявшийся вывод и ациклично по построению, а граф описания говорит о предполагаемых действиях, ни одно из которых не выполнено.

Referencing norms: AuxiliaryLine, BranchingStep, ConditionLine, ExpandableByCall, FlowLine, LoopingStep

ru · official · sha256:c14c1d42449507eba8081d9be000174bc16785e9d844489d44989e08752c74e7RU

§5. Достижимость, циклы и рекурсия Шаг достижим, если он есть начальный шаг описания либо в него ведёт переход из достижимого шага. Недостижимый шаг есть дефект описания и обнаруживается сравнением объявленных шагов с достижимыми. Шаг лежит на цикле, если он достижим из самого себя по переходам. Наличие цикла — не дефект: цикл есть форма повторения. Дефектом является цикл без меры убывания (§6). Описание рекурсивно, если некоторый его шаг передаёт управление тому же описанию. Рекурсия описания и цикл описания — разные формы повторения, и обе требуют своего обоснования завершения.

Referencing norms: CoveredEdge, CoveredEntry, CyclicStep, ReachesDirect, ReachesTransitive, RecursiveAlgorithm, RecursiveStep

ru · official · sha256:5b8d7b76662ff424dc17b919a3601ebc815a0bfeb40a663c25592a2457e2f55cRU

§6. Инварианты и меры убывания Инвариант — утверждение о состоянии, истинное при каждом прохождении названного шага. Инвариант привязывается к шагу, а не к описанию целиком: утверждение, истинное всюду, есть свойство задачи, а не цикла. Мера убывания — величина, принимающая значения из вполне упорядоченного множества и строго убывающая при каждом повторении. Мера отвечает на вопрос о завершении; инвариант отвечает на вопрос о правильности. Смешение их — частая ошибка изложения. Описание с повторением обязано называть меру. Описание без повторения меры не требует, и её отсутствие у такого описания дефектом не является.

Referencing norms: InvariantAtLine, InvariantLine, MeasureGiven, MeasureLine, MeasureRequiredByCycle, MeasureRequiredByRecursion

ru · official · sha256:dc3cefa4943e32a57c8ebde4063b8bfa5a4fc926b63b9f69206fc2c5d227e37dRU

§7. Основания шагов и основание завершения Основание шага — утверждение, из которого следует ДОПУСТИМОСТЬ шага: определение, теорема, лемма, инвариант, построение или соглашение изложения. Шаг без основания есть предписание без причины; такое описание способно быть верным, но объяснить себя оно не может. Основание завершения — утверждение о том, почему выполнение прекращается: убывание меры на вполне упорядоченном множестве, исчерпание конечного множества, достижение объявленного условия остановки. Для приближённых методов основанием завершения служит критерий остановки, и он называется вместе с условиями, при которых сходимость гарантирована. Род основания указывается явно, потому что от него зависит, где искать доказательство. Определение и соглашение доказательства не требуют. Теорема и лемма его требуют, и оно остаётся в источнике: настоящее представление применяет формулировку известного результата, а не проверяет его доказательство.

Referencing norms: AdmissibleStep, GroundLine, Terminates, TerminationLine

ru · official · sha256:c28c0596f0b13e60ab44359c602150b76b59f6c450afedb5392939ebc5cc151fRU

§8. Корректность и её обоснования Утверждение о корректности говорит, что описание получает объявленный выход при выполненных предусловиях. Оно сопровождается обоснованием и условиями действия: утверждение о корректности, верное лишь при дополнительном условии, обязано это условие называть. Доказательства известных результатов остаются в источниках. Настоящее представление удостоверяет ПРИМЕНЕНИЕ принятых определений и результатов к предъявленному описанию; оно не удостоверяет доказательства самих результатов и не заменяет их проверки. Утверждение, доказательство которого остаётся в источнике, помечается явно и предъявляется вместе с выводом. Умолчание здесь недопустимо: читатель обязан видеть, где кончается проверенное машиной и начинается принятое на веру источника.

Referencing norms: CorrectnessGroundLine, CorrectnessLine, CorrectnessStated, ProofInSourceLine

ru · official · sha256:275d09a5f4fb54b491118ef3012f00c6a3925b467290e4452d92936f428e432cRU

§9. Модель стоимости и оценки Оценка сложности осмысленна только относительно модели стоимости: что считается единицей работы и что считается размером входа. Модель называется до оценок; оценка без модели не проверяема. Различаются оценки худшего случая, среднего случая, лучшего случая и амортизированные, а также оценка дополнительной памяти и оценки по числу отдельных операций — сравнений, обменов, обращений к памяти. Каждая оценка несёт условие своего действия: распределение входа для среднего случая, ограничение на алфавит, допущение о равномерности данных. Оценка есть свойство описания, а не измерение: она не получена запуском и на конкретной машине не проверялась.

Referencing norms: CostLine, CostModelLine, CostStated

ru · official · sha256:a10f9c0308565f6e8441a26def39ff39fb032c058a5a3ebc2d3ee752bbcaa70bRU

ОПИСАНИЕ АЛГОРИТМА КАК ФОРМАЛИЗОВАННОЕ ЗНАНИЕ: СЛОВАРЬ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он вводит словарь, которым в Arxo описывается алгоритм — не выполнение алгоритма на предъявленных данных, а его устройство: задача, шаги, переходы, основания, завершение, стоимость, варианты и связи с понятиями и источниками. Настоящее изложение не является нормативным актом и не имеет силы источника права ни в одной юрисдикции. Оно не воспроизводит и не переводит ни один учебник: словарь составлен для настоящего репозитория, а происхождение каждой конкретной формулировки алгоритма называется в описывающем его пакете отдельно. Граница предмета названа сразу. Описание алгоритма говорит, ЧТО следует делать и ПОЧЕМУ это допустимо; оно не выполняет описанного и не утверждает, что выполнение состоялось. Вопрос «как разделить 156 на 12» и вопрос «как устроено деление столбиком» — разные вопросы, и второй отвечается без первого.