# 概念推導導讀

299 份概念教學導讀；另有 36,000 題逐題詳解，兩者分開查找。

[搜尋全部題目與詳解 →](/zh-Hant/explore/)

1共 1 項 · 第 1／1 頁



概念導讀



## [算法正確性：非確定性相鄰交換排序的部分正確、終止與總正確](/zh-Hant/derivations/derivation-mko-algorithm-correctness-01/?from=%2Fzh-Hant%2Fderivations%2F%3Fq%3Dmko-algorithm-correctness)

在有限狀態模型 M 中，狀態是 (1,2,3) 的六個排列，初始狀態 (3,2,1)，每步可非確定性地交換任一個相鄰逆序對，Halt={(1,2,3)}。以後置條件「遞增排列且為輸入的重排」證明 M 的部分正確性、終止性與總正確性：用排名函數 inv（逆序數）證明每條執行至多 3 步，且每條極大執行停在 Halt。再以變體 M′（允許交換任何相鄰對）說明一條成功路徑與部分正確都不足以得到總正確，以變體 M″（錯誤的停止條件）說明終止不足以得到正確。

算法正確性

derivation-mko-algorithm-correctness-01





1共 1 項 · 第 1／1 頁