試験でのアルゴリズムの表現について

質問

現在進学を考えている情報系の大学院の入学試験の問題に、

「・・・のアルゴリズムを設計せよ。」

「・・・のアルゴリズムを設計し、プログラムを書け。」

などといった形式での出題があります。（解答は紙上だと思います。）

このような出題文があったとき、どのような言語によってアルゴリズムを表現することが適切または一般的なのでしょうか？

候補としては

・言葉で書く
・既存のプログラミング言語で書く
・擬似言語やフローなどで書く

などが考えられますが、どれも試験で書くには一般性が薄いように思われますが、いかがでしょうか。

要は、

・「このような規約に従って」という注釈を入れなくても一般的に従われる規約があるのか
・そのような規約はどこで定義されているのか

この二つが知りたいのです。

ぜひご教授よろしくお願いします。

回答No.1

Tacosan · ベストアンサー

単に「アルゴリズムを書け」という問題なら, 相手に通じさえすればどういう書き方でもいいと思う. 疑似言語で書くなりフローで書くなりするのが安全だとは思うけど.
一方「プログラムを書け」というのは問題として不適切だと思う. 少なくとも「用いるプログラム言語」は指定しておくべきだろう. そうでないとしたら受験生にとって不親切だし, 採点者にとっても不親切だ.

まあ, 気になったら試験監督に聞いてやってください.

補足

ご回答ありがとうございます。

私も「言語が指定されていないプログラムを書く」という点が引っかかっておりました。やはりこのような出題の場合、出題側の不備ではないかということで本番では試験監督の方に聞いてもいいのでしょうか。

ただ、擬似言語等で相手に分かりやすく書こうとしても、前提として使ってよい演算の定義があいまいではないでしょうか？

今ちょうど悩んでいるのが、「配列の要素数」や「配列の中の最大要素の値」を返す手続きをわざわざサブルーチンとして表すべきなのか、それともlength(A)、max(A)などと表現して、自由に使ってよいのかという点です。
（例えばCでは要素数を取得するためにはsizeof演算子を使いますよね？しかし今使っている教科書（アルゴリズムイントロダクション）ではlength(A)を使える前提として、max(A)は使えないとしています。）

やはりどこまでの処理を、どのように表現するかは、数学などと一緒で多くの問題を解いていくうちに体得していくしかないのでしょうか？

それとも基準といったものがあるのでしょうか？

回答No.3

Tacosan

「アルゴリズムイントロダクション」だとどんな基準だったかなぁ.... 最初の方に書いてあったかもしれん. 「O(1) でできるかどうか」とか, そんなところかなぁ?

「プログラムを書け」だと, 今なら普通は C か Java か, その辺かなぁ. Lisp (Scheme) はありだと思うけど, APL はダメだろ～な～.

補足

重ねてありがとうございます。

＞「O(1) でできるかどうか」
なるほど。計算時間が判断基準となるのではということですね。

アルゴリズムイントロダクションでは、RAM（ランダムアクセスマシン）モデルの説明で「算術演算、データ移動命令、制御命令を持つ」としています。多分これらの命令だけを使ってアルゴリズムを作れということでしょう。

ただし、擬似コードのオブジェクト関係の説明で「例えば配列は、それが含む要素数を示す長さの属性値lengthを持つオブジェクトとして取り扱う」と述べられています。

これはアルゴリズムイントロダクション上で配列が与えられたとき、length(A)の値がどこかに記憶してあって、その取得がO(１)でできるということの言い換えだと考えれば、なんとなく納得できそうです。

計算時間についてもう少し検討してみます。

回答No.2

DoubleHead

大学院の試験なんですよね？

この人はどのように表現するか？というのを見る、
という側面もあるんじゃないですか？
その試験は。

つまり、いままで何を学んできたのか？
学んだことを自分なりに消化して自分のものにしているか？
自分なりのやり方を確立しているか？
他人に(試験管に)わかりやすく表現できるか？
ということも同時に問われてるわけですね。

私は現役のプログラマ(SE)ですが
設計書をどのようにして書くか、
はプロジェクトによって違うことはよくあることです。
(もちろん社内規約などが存在することも多いですが)
ですが、ほぼ共通しているのは
他の人(上司、顧客、実際にプログラムを書くプログラマ、あとでメンテナンスする後任者など)
にわかりやすく、間違いや誤解がないように伝えられるか
が重視されるということです。
Javaの書き方で書くのも結構です。
ですが、もし、10年後にJavaが廃れて扱える人が少なくなって(まぁ、ありえませんがね)
しまったとき、それを読める人はいますか？

配列のサイズを得る場合を表現したいのなら

配列Xのサイズを得て変数Aに代入する。

または擬似言語風に

A ← 配列変数Xの配列のサイズ

とでも書けばCだろうとJavaだろうとかまいませんよね。

もしくはもっとはしょって
１．以下の処理Sを配列Xの配列の要素全てに対して繰り返す。
２．処理Sとは ・・・・・
なんて書いてもいいかもしれません。

自分がJavaが得意ならばJava風に書いて押し切ってもいいかもしれません。
それが試験管への自分のアピールです。
(それで合格になるかどうかは知りませんが)

京大の数理解関所のある教授の下で働いていた経験がありますが
テスト用紙に１＋１＝？ と書かれて２とだけ書くのは
大学入試までのレベル
大学院や社会では
なぜ２になるのか、
２である必要はあるのか、
そしてそれを他人に説明できるか
が重要だとかなんとか、そんな感じのことを誰かが言ってた気がしますし
たぶんそれはそのとおりだと思います。

お礼

ご回答ありがとうございます。

＞つまり、いままで何を学んできたのか？
＞学んだことを自分なりに消化して自分のものにしているか？
＞自分なりのやり方を確立しているか？
＞他人に(試験管に)わかりやすく表現できるか？
＞ということも同時に問われてるわけですね。

ご指摘の点、まことに耳が痛いです。

自分のやり方を確立することは現在院試の勉強によって強化しているところなのですが、「相手に分かりやすく表現する」というのは、相手と自分が共有している前提を理解していないとできないと思います。

私は現在所属している学科とは少し毛色の違う専攻を希望しており、そのため専攻の文化や採点者の観点などがこれまでの経験とは違うものであると考えています。
ですので自分と採点者さんはどこまでの常識を共有していて、どのようにしたら自分の考えをわかりやすく伝えられるかということがまだはっきりしない状態です。

ですので私がどれだけわかりやすいように書いたコードも、採点者さんの持っている前提に照らせて論外であり唾棄されるのではないかということが怖いのです。

このたびこちらで質問させていただいたのは、特に未知であるアルゴリズムの分野に関して、広く一般的な見解をいただき、「一般の常識」という名を借りて採点者さんと私が共有していると思われる前提の幅を広げるためでありました。

その意味で、

＞設計書をどのようにして書くか、
＞はプロジェクトによって違うことはよくあることです。

など実際の現場の方の経験を伺えたのは貴重でした。

ありがとうございます。