7
第 ２ 章
ア ル ゴ リ ズ ム の 構 築 言 語 と し て の ET
１ ． プ ロ グ ラ ム の 背 後 に あ る ア ル ゴ リ ズ ム
例 え ば 、 プ ロ グ ラ ム を Ｃ 言 語 で 記 述 し た 場 合 、 ル ー ル に 相 当 す る よ う な 、 比 較 的 独 立 し た 部 分 と い う の が 存 在 し な い 。 し た が っ て 、 問 題 を 解 く ア ル ゴ リ ズ ム は 一 挙 に 作 ら な け れ ば な ら な い 。 そ の た め C や Basic な ど の プ ロ グ ラ ミ ン グ は 、 か な り 難 し い も の に な る 。
そ こ で 、C や Basic な ど の 手 続 き 型 言 語 の プ ロ グ ラ ミ ン グ の 構 造 を 考 え て み よ う 。 例 え ば 、２ つ の 数 の 最 大 公 約 数 を 求 め る と い う 問 題 に 対 す る C や Basic の プ ロ グ ラ ム を 思 い 浮 か べ な さ い 。こ れ ら は よ く 似 て い て 、「 ユ ー ク リ ッ ド の 互 除 法 」と い う 同 じ ア ル ゴ リ ズ ム を 用 い て 書 か れ て い る こ と が 多 い 。 つ ま り 、 こ の プ ロ グ ラ ム の 背 後 に は 、 ユ ー ク リ ッ ド の 互 除 法 と い う ア ル ゴ リ ズ ム が あ っ て 、 そ れ か ら 具 体 的 な プ ロ グ ラ ム の 記 述 が 得 ら れ て い る と 考 え る こ と が で き る 。
２ ． ２ 段 階 の プ ロ グ ラ ミ ン グ
一 般 に 、 問 題 と プ ロ グ ラ ム の 間 に は 、 具 体 的 な プ ロ グ ラ ミ ン グ 言 語 に は 依 存 し な い ア ル ゴ リ ズ ム と い う も の が 存 在 し て い る と 考 え る こ と が で き る 。 そ こ で 、 ア ル ゴ リ ズ ム に よ っ て 、 プ ロ グ ラ ミ ン グ を ２ つ の 段 階 に 分 け て 考 え よ う 。 １ つ は 問 題 か ら ア ル ゴ リ ズ ム を 作 り 出 す 段 階 で あ り 、 も う １ つ の 段 階 は 、 そ の ア ル ゴ リ ズ ム に 基 づ い て 、 具 体 的 な デ ー タ 構 造 な ど を 決 定 し 、 あ る 言 語 を 用 い て プ ロ グ ラ ム を 書 く 段 階 で あ る 。
し か し 、 現 実 に は 、 ⓐ ア ル ゴ リ ズ ム を ど の よ う な 言 語 で 記 述 す る の が 最 適 な の か 、 あ る い は ⓑ 問 題 か ら そ の ア ル ゴ リ ズ ム を ど の よ う に し て 導 く の か 、 あ る い は ⓒ そ の ア ル ゴ リ ズ ム か ら プ ロ グ ラ ム を い か に 作 り だ す か 、 と い う こ と に つ い て は 、 充 分 に 解 明 さ れ て い る と は い え な い 。
２つの数の最大公約数を 求める。
問 題 C プログラム
Basicプログラム
Fortranプログラム
２つの数の最大公約数を 求める。
２つの数の最大公約数を 求める。
問 題
問 題 C C プログラムプログラム Basicプログラム Basicプログラム
Fortranプログラム Fortranプログラム
？
ユークリッドの互除法 ２つの数の最大公約数を
求める。
問 題 C プログラム
Basicプログラム
Fortranプログラム アルゴリズム
ユークリッドの互除法 ユークリッドの互除法 ２つの数の最大公約数を
求める。
２つの数の最大公約数を 求める。
問 題
問 題 C プログラムC プログラム
Basicプログラム Basicプログラム
Fortranプログラム Fortranプログラム アルゴリズム
アルゴリズム
8
従 来 の プ ロ グ ラ ミ ン グ の 入 門 書 は 、 ア ル ゴ リ ズ ム は 自 然 言 語 や 数 式 な ど を 用 い て 説 明 さ れ て き た が 、 問 題 か ら ア ル ゴ リ ズ ム を 作 る 方 法 は 体 系 的 に は 与 え ら れ て い な か っ た と 考 え ら れ る 。 ア ル ゴ リ ズ ム を 作 り 出 す こ と は 個 人 の 直 感 に 任 さ れ 、 そ れ を 特 定 の プ ロ グ ラ ミ ン グ 言 語 を 用 い て 記 述 す る こ と が プ ロ グ ラ ミ ン グ 学 習 の 主 要 部 分 に な っ て い る こ と が 多 い 。
３ ． Ｅ Ｔ で ア ル ゴ リ ズ ム を 記 述 す る
本 書 で は 、 ア ル ゴ リ ズ ム を 記 述 す る 言 語 と し て ET を 推 奨 す る 。 そ の と き 、 ２ つ の 数 の 最 大 公 約 数 を 求 め る 問 題 に 関 し て い え ば 、 次 の よ う に な る で あ ろ う 。
与 え ら れ た 問 題 は 、 ２ つ の 数 の 最 大 公 約 数 を 得 る こ と(図 の 左)で あ る 。 こ れ に 対 し て 、 そ れ を ユ ー ク リ ッ ド の 互 除 法 と い う ア ル ゴ リ ズ ム で 解 く の で あ る が 、 そ れ を 明 確 に 記 述 し た も の が ET の ２ つ の ル ー ル(図 の 中 央)で あ る 。 そ し て 、 そ れ を C 言 語 で 記 述 す る と 、 右 側 の プ ロ グ ラ ム を 得 る 。
ユ ー ク リ ッ ド の 互 除 法 と い う ア ル ゴ リ ズ ム を 自 然 言 語 で 記 述 し た 場 合 、「 ２ つ の 整 数 が あ っ た と き 、 大 き い ほ う の 数 を 小 さ い ほ う の 数 で 割 っ た 余 り を 、 大 き い ほ う の 数 に 置 き 換 え る 。 こ の 操 作 を 繰 り 返 し 、 片 方 の 数 が ０ に な る と 、 も う 片 方 の 数 が 求 め る 最 大 公 約 数 と な る 」 と 表 現 さ れ る 。 こ の よ う に 、 自 然 言 語 で ア ル ゴ リ ズ ム を 記 述 す る と 、 大 ま か な 動 き が と ら え や す い 場 合 も あ る が 、 厳 密 で 明 快 な 議 論 や 機 械 的 処 理 に は 充 分 で な い 場 合 が 多 い 。
9
ま た 、ユ ー ク リ ッ ド の 互 除 法 と い う ア ル ゴ リ ズ ム を 、図 中 の 右 の よ う に C 言 語 で 記 述 し た と す る 。 こ の 場 合 、int a(整 数 型)な ど の 型 宣 言 、scanf(入 力)や printf(出 力)な ど の 命 令 語 、%d(10進 数 の 表 示)な ど の 変 換 文 字 列 と い う よ う に 細 部 に わ た っ て 記 述 し な け れ ば な ら な い 。 さ ら に 、C の プ ロ グ ラ ム で は 、A と B の 最 大 公 約 数 を 、B と 「A÷B の 余 り 」 の 最 大 公 約 数 を 求 め る 方 法 に 置 き 換 え る 部 分 と 、余 り が ０ の と き A を 最 大 公 約 数 と す る 部 分 が 融 合 し て 、do~while 文 と printf 文 の 中 に ま と め て 表 現 さ れ て い る 。C の プ ロ グ ラ ム を み て も 、 ２ つ の 部 分 を 分 離 す る の は 困 難 で あ る 。
一 方 、 Ｅ Ｔ は ユ ー ク リ ッ ド の 互 除 法 の ア ル ゴ リ ズ ム を ２ つ の 独 立 し た 部 品(ル ー ル)で 構 成 す る こ と が で き る 。A と B の 最 大 公 約 数 を 、B と 「A÷B の 余 り 」 の 最 大 公 約 数 を 求 め る 方 法 に 置 き 換 え る 部 分 は 、
(gcd *A *B *X),{(> *B 0)} --> (:= *C (mod *A *B)),(gcd *B *C *X).
と 書 く こ と が で き 、 余 り が ０ の と き A を 最 大 公 約 数 と す る 部 分 は 、 (gcd *A 0 *X) --> (= *X *A).
と 書 く こ と が で き る 。 こ の よ う に 、ET は 自 然 言 語 よ り も ア ル ゴ リ ズ ム を 厳 密 に 書 く こ と が で き 、 Ｃ 言 語 な ど の 手 続 き 型 言 語 よ り も 細 部 に と ら わ れ ず に 、 各 部 を 独 立 性 高 く 記 述 す る こ と が で き る 。 そ の た め 、 Ｅ Ｔ は ア ル ゴ リ ズ ム を 記 述 す る た め の 言 語 と し て 、 自 然 言 語 や C 言 語 な ど よ り も 向 い て い る と 考 え ら れ る 。
４ ． ア ル ゴ リ ズ ム の 構 築 言 語 と し て の Ｅ Ｔ
ET を ア ル ゴ リ ズ ム 構 築 の た め の 言 語 と し て み な し 、 最 終 的 に C 言 語 の プ ロ グ ラ ム を 得 る 場 合 、 プ ロ グ ラ ミ ン グ は 次 の ２ 段 階 に な る 、 第 一 の ス テ ッ プ は 、 問 題 か ら ET の ル ー ル の 集 合 か ら な る ア ル ゴ リ ズ ム を 構 築 す る こ と で あ り 、 も う １ つ の ス テ ッ プ は 、ET で 書 か れ た ア ル ゴ リ ズ ム か ら 、C の プ ロ グ ラ ム を 得 る こ と で あ る 。
問 題
入れ替え可能
Ｃ言語のプログラム
それぞれ別々 に作る
ルール ルール ルール
寄せ集めて 融合する
融合したものは 組み換えしにくい アルゴリズム構築 プログラム記述
問 題
入れ替え可能
Ｃ言語のプログラム Ｃ言語のプログラム
それぞれ別々 に作る
ルール ルール ルール ルール ルール ルール
寄せ集めて 融合する
融合したものは
組み換えしにくい
アルゴリズム構築 プログラム記述
10
ET で ア ル ゴ リ ズ ム を 構 築 す る と き 、 問 題 を も と に し て 、 そ れ ぞ れ の ル ー ル を 独 立 に 作 る こ と が で き る 。ル ー ル を 積 み 重 ね て い く こ と が 、ア ル ゴ リ ズ ム を 作 る こ と に な る 。ま た 、 一 度 作 っ た ル ー ル を 別 な ル ー ル に 入 れ 替 え て 、ア ル ゴ リ ズ ム を 改 善 す る こ と も 容 易 で あ る 。 そ の よ う に し て 、 独 立 に 記 述 ・ 蓄 積 さ れ た 複 数 の ル ー ル が 達 成 す る 動 き を 、 ひ と ま と ま り の 手 続 き と し て 表 現 す る こ と に よ っ て 、Ｃ 言 語 で 記 述 さ れ る １ つ の プ ロ グ ラ ム が 得 ら れ る 。 も し 、ET の ル ー ル を 経 な い で 、C 言 語 で 直 接 的 に プ ロ グ ラ ム を 書 こ う と す る と 、 プ ロ グ ラ ム で 書 く べ き 「 動 き 」 を ど う や っ て 思 い つ く の か と い う 手 が か り に 乏 し い 。 そ し て 、 プ ロ グ ラ ム を ひ と ま と ま り の 手 続 き と し て 作 ら な け れ ば な ら な い の で 、 も し エ ラ ー が 生 じ た と き に は 、 プ ロ グ ラ ム 全 体 を 見 て 修 正 し な け れ ば な ら な い 。 こ の よ う に 、C 言 語 に よ る プ ロ グ ラ ム 記 述 は 、 完 成 し た ア ル ゴ リ ズ ム を 計 算 機 に 伝 え て 、 計 算 を 実 行 さ せ る た め に は 適 し て い る が 、 問 題 か ら 最 適 な ア ル ゴ リ ズ ム を 作 り 出 す た め に は 便 利 で は な い 。 ま た 、 Ｃ 言 語 で 記 述 し た プ ロ グ ラ ム は 一 体 化 し た 手 続 き な の で 、 い っ た ん 作 っ た プ ロ グ ラ ム を 改 善 の た め に 組 み 換 え る こ と は 難 し く な る 。
５ ． プ ロ グ ラ ミ ン グ 言 語 と ア ル ゴ リ ズ ム の 構 築 言 語 と の 使 い 分 け
私 た ち は 、 １ 章 で は ET は プ ロ グ ラ ミ ン グ 言 語 で あ る と い う 観 点 で ET の こ と を 述 べ て き た 。本 章 で は 、ET を ア ル ゴ リ ズ ム の 構 築 言 語 と し て 位 置 付 け て い る 。本 書 で は 、ET の こ れ ら の ２ つ の 見 方 を 並 存 さ せ な が ら 話 を 進 め る 。ET は ア ル ゴ リ ズ ム を 記 述 し て 実 行 す る こ と が で き る と い う 点 で プ ロ グ ラ ミ ン グ 言 語 で あ る と と も に 、 問 題 か ら ア ル ゴ リ ズ ム を 構 築 す る 過 程 で 効 果 的 に 使 う こ と が で き る ア ル ゴ リ ズ ム 構 築 言 語 で も あ る 。
プ ロ グ ラ ミ ン グ で 難 し い の は 、 完 成 さ れ た ア ル ゴ リ ズ ム を プ ロ グ ラ ミ ン グ 言 語 で 記 述 す る こ と で は な く 、 問 題 か ら ア ル ゴ リ ズ ム を 作 り だ す こ と で あ る 。ET を 通 し て 、 ア ル ゴ リ ズ ム の 構 築 と は 何 か に 関 し て 理 解 を 深 め る の が 本 書 の 中 心 的 な ね ら い で あ る 。
