はじめに

解答はあくまで私が解いたものであり、正解を保証するものではありません。

途中で解答を書くのに飽きて雑になっているところがあります。問題文が不完全な場合があります。

山梨大学は編入試験を含め、入試問題を公開しています。神。 山梨大学過去問集へのリンク

傾向と対策

コンピュータ理工科は成績証明書：口述試験：筆記試験の配点の比が1:1:8となっています(ただし、口述試験単体でも否だと、他の点数に関わらず不合格になります)。

出題範囲

当たり前っちゃ当たり前ですが、基本情報や応用情報技術者試験と重なっている部分も多く、それらの試験の対策をしたことがあると解きやすいと思います。

プログラミング

• 他の学校に比べ、難易度は高めだと思います。プログラミングの基礎知識、というよりはアルゴリズム寄りです。基本的なデータ構造やアルゴリズムはもちろん、計算量やプログラミング的な思考力が問われます。一方で、コンパイルの処理やオブジェクト指向について説明させる問題が出題されることもあり、多くの知識が求められます。
• 二分木に関する問題が頻出です。再帰処理に対する理解が必要です。
• ポインタを扱うリスト構造も頻出です。ポインタの理解が必要です。
• その他、ハッシュテーブルや動的計画法、ヒープ構造など、様々なアルゴリズムが出題されているため、対策が難しくなっています。
  • bit全探索や、部分和問題についての動的計画法あたりはAtCoder茶色以上のレベル感です。
• 行きがけ順、帰りがけ順、分離チェイン法など、語句を知っておく必要があります。
• たまにソフトウェア工学に関する問題(オブジェクト指向、テスト)が出題されます。

計算機アーキテクチャ

• 出題範囲が広く、暗記の量が多いです。また、読解力が求められる問題も多く出題されています。

情報数学

• 命題、集合、関係、行列、確率などの特に離散数学に関する問題が出題されます。
• 命題：数学的帰納法での証明問題や、命題に関する基礎的な問題が出題されます。
• 行列：固有値と固有ベクトル、行列式、逆行列、行列の積などに関する問題が出題されます。
• 確率：基本的な確率の問題です。ベイズの定理や重複組合せが出題されることもあります。
• 関係：反射律、対称律、同値関係あたりの定義は覚えておいたほうが良いです。
• 集合：一度包除原理を使った問題が出題されましたが、基本的には高校数学レベルです。
• グラフ理論：令和5年度、突如2部グラフと2彩色グラフに関する証明問題が出ました。
• その他、情報エントロピーやハフマン符号化に関する問題が出題されています。

基本的に情報数学は他の科目に比べて優しいですが、稀に破天荒な問題が出題されることがあります。

令和5年度

1. 筆記試験 プログラミング、計算機アーキテクチャ、情報数学の3科目を出題し、2科目の選択解答 としました。試験時間は80分です。試験問題は別紙の通りです。
2. 口述試験 コンピュータ理工学に関する専門分野の基礎的事項、意欲、コミュニケーション力、思 考力に関する口述試験を行いました。試験時間は10分です。

プログラミング

問1

ソートアルゴリズムの安定性とは何かを説明しなさい。

安定性とは、同じ値を持つ要素があった場合、ソート前とソート後でそれらの順番が入れ替わるかどうかのことである。ソート前とソート後で順番が変わらない場合、安定なソートであり、変わる場合、不安定なソートである。

「挿入ソート」，「マージソート」，「クイックソート」の3つのアルゴリズムについて、安定かどうかを答えなさい。

• 挿入ソート：安定
  • 数字を挿入するときに、確定部分を前から順番に見ていって、挿入する数字よりも大きい数字があったら、その数字の前に挿入するようにすると安定なソートになる。逆に、確定部分を後ろから見ていき、挿入する数字よりも小さい数字があったら、その数字の後ろに挿入するようにすると不安定なソート(同じ数字は逆順)になる。
• マージソート：安定
  • 要素を分割したときに、同じ値を持つ要素があった場合、左側の要素を優先してマージするようにすると安定なソートになる。逆に、右側の要素を優先してマージするようにすると不安定なソートになる。
• クイックソート：不安定
  • ピボットの選択により、同じ値を持つ要素の順番が変わることがあるため、不安定なソートになる。

データ数が$n$のとき、「挿入ソート」，「マージソート」，「クイックソート」の3つのアルゴリズムの平均計算量、最悪計算量、最良計算量のオーダーを答えなさい。

• 挿入ソート

  • 平均計算量：$O(n^2)$
  • 最悪計算量：$O(n^2)$
    • 逆順の配列をソートする場合
  • 最良計算量：$O(n)$
    • 整列済みの配列をソートする場合

• マージソート

  • 平均計算量：$O(n\log n)$
    • マージする際に、$n$回比較する。それを$\log n$回繰り返すので、$O(n\log n)$となる。
  • 最悪計算量：$O(n\log n)$
  • 最良計算量：$O(n\log n)$
    • 数列がどのような形をしていても、比較回数は変わらない。

• クイックソート

  • 平均計算量：$O(n\log n)$
    • 厳密な導出は結構難しいので、省略
  • 最悪計算量：$O(n^2)$
    • ピボットが常に最大値または最小値の場合
  • 最良計算量：$O(n\log n)$
    • ピボットの選択により、$n$回比較する。それを$\log n$回繰り返すので、$O(n\log n)$となる。

問2

キー値が 0 から 15 までの整数値を取るとき，キー値の集合からハッシュ表を作成することを考えます．レコードはキー値のみで他にデータはないものとします．ハッシュ表のサイズ L を 5 とし，ハッシュ表の各要素は 0~4 の番地を持つものとします．ハッシュ関数 h(x)を h(x) = 3x mod L とします．

ハッシュ値が 2 で衝突するような 3 つの異なるキー値を挙げなさい．

$3x \mod 5 = 2$となるような$x$を求めると、$x=4,9,14$。

空のハッシュ表に，(a)の 3 つのキー値を分離チェイン法（チェイン法，分離連鎖法）によって格納する様子を図示しなさい．ただし，キー値が格納されているところだけの様子が分かればよく，その他の部分は書き入れる必要はありません．

チェイン法は、結合リストを用いて同じ番地に複数のデータを入れる。(図は省略)

空のハッシュ表に，(a)の 3 つのキー値を開番地法（空き番地法，オープンアドレス法）によって格納する様子を図示しなさい．ただし，代替ハッシュは線形走査法（線形探査法）で求めなさい．また，キー値が格納されているところだけの様子が分かればよく，その他の部分は書き入れる必要はありません．

オープンアドレス法は、衝突が起きた場合に、ひとつ後ろの番地に格納する方法である。その場所も衝突していた場合は、さらにひとつ後ろの番地に格納する。これを繰り返す。(図は省略)

問3

データ数を n とする時，平衡２分探索木に格納されたデータの中から，特定のデータを探索する作業の平均計算量のオーダーを答えなさい．平衡２分探索木は「どのノードの左右部分木の高さの差も 1 以下」という条件を満たす２分探索木です．

木の高さのオーダーは$O(\log n)$であるため、平均計算量のオーダーも$O(\log n)$となる。

次のプログラムは，２分探索木の実装の一部です．空欄（ア）～（ウ）に当てはまる，再帰を用いたコードを記述しなさい．

pの子のうち、高い方の高さに1を加えたものが高さである。

1
2
3
4
5

int height(BinaryNode* p){
    // p が指しているノードを根とする木の高さを返す．
    if ( p == NULL ) return 0;
    return 1 + ( ( height(p->left) > height(p->right) ) ? height(p->left) : height(p->right) );
}

全てのノードについて検証をしなければならないということに注意。再帰関数に慣れていないと難しい。 あるノードの子を根とする木が平衡２分探索木のバランス条件を満たしていて、かつ、そのノードの左右部分木の高さの差が1以下であるとき、そのノードを根とする木は平衡２分探索木のバランス条件を満たしている。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

bool is_balanced(BinaryNode *p)
{
    // p が指しているノードを根とする木が平衡２分探索木のバランス条件を満たしているかどうかを返す．
    if (p == NULL)
        return true;
    if (is_balanced(p->left) && is_balanced(p->right))
        return (abs(height(p->left) - height(p->right)) <= 1);
    else
        return false;
}

main 関数の「エ」の時点での２分探索木を図示しなさい．この２分探索木を前順（行きかけ順，preorder）ならびに中順（通りがけ順，inorder）でなぞったときのノードの訪問順序を答えなさい．

二分探索木は次のようになる

1
2
3
4
5
6
7

      5
   /     \
  2       7
 / \     /
1   3   6
     \
      4

• 行きかけ順(preorder): 5, 2, 1, 3, 4, 7, 6
• 通りがけ順(inorder): 1, 2, 3, 4, 5, 6, 7
• (帰りかけ順(postorder): 1, 4, 3, 2, 6, 7, 5)

情報数学

問1

$𝑛$ 個の元からなる集合 $𝐴$ には $2^n$ 個の部分集合があることを数学的帰納法を用いて証明しなさい．

• $n=0$のとき。$2^0=2$である。$A$の部分集合は$\phi$の1つである。よって、$n=0$のとき成立する。
• $n=k$のとき、$A= \lbrace a_1,a_2,\cdots a_k \rbrace $の部分集合は$2^k$個あると仮定する。$n=k+1$のとき、$A= \lbrace a_1,a_2,\cdots a_k,a_{k+1} \rbrace $の部分集合は、$a_{k+1}$を含まない部分集合は$2^k$個ある。$a_{k+1}$を含む部分集合は、$a_{k+1}$を含まない部分集合に$a_{k+1}$を加えたものである。よって、$2^k+2^k=2^{k+1}$個ある。よって、$n=k+1$のときも成立する。

問2

2 個の赤球と 18 個の白球が入った袋から，太郎，花子がこの順で 1 回ずつ球を取り出すとき，太郎が赤球を取り出す事象を 𝑇，花子が赤球を取り出す事象を 𝐻 とします．なお，取り出した球は袋に戻さないものとします．次の問いに答えなさい．

太郎が赤球を取り出した後，花子も赤球を取り出す確率 𝑃(𝑇∩ 𝐻) を求めなさい．

$$ \frac{2}{20} \times \frac{1}{19} = \frac{1}{190} $$

太郎が赤球を取り出す確率 𝑃(𝑇) と花子が赤球を取り出す確率 𝑃(𝐻) は等しいことを証明しなさい．

• 太郎が赤球を取り出す確率は$\frac{2}{20}=\frac{1}{10}$である。
• 花子が赤球を取り出す確率は、
  • 太郎が赤球を取り出した後、花子が赤球を取り出す確率は$\frac{2}{20} \times \frac{1}{19} = \frac{1}{190}$である。
  • 太郎が白球を取り出した後、花子が赤球を取り出す確率は$\frac{18}{20} \times \frac{2}{19} = \frac{18}{190}$である。
• よって、花子が赤球を取り出す確率は$\frac{1}{190} + \frac{18}{190} = \frac{19}{190} = \frac{1}{10}$であり、太郎が赤球を取り出す確率と等しい。

問3

1. (i)$\rightarrow$(ii)について

$|C|=2$であるから、$C$の要素を$0,1$としたときに、頂点の集合$L,R$を次のように定める。$L=\lbrace v\in V|f(v)=0 \rbrace,R=\lbrace v\in V|f(v)=1 \rbrace$とする。このとき、$L,R$は$L\cup R=V$かつ$L\cap R=\phi$である。すなわち、$L\subseteq V$かつ$R=V\setminus L$であり、各辺$(v,w)\in E$に対して、$v\in L,w\in R$または$v\in R,w\in L$である。よって、$G$は二部グラフである。

2. (ii)$\rightarrow$(i)について

$f:V\rightarrow C$を次のように定める。$f(v)=0$ if $v\in L$、$f(v)=1$ if $v\in R$とする。このとき、各辺$(v,w)\in E$に対して、$f(v)\neq f(w)$である。よって、$G$は2彩色可能である。

3. (i)$\rightarrow$(iii)について

対偶を示す。「$G$に奇数の長さの閉路が存在する$\rightarrow$$G$が2彩色不可能である」を示す。 長さが奇数の閉路が頂点$v_1,v_2,\cdots,v_{2k+1}$を通るとする。$f(v_1)=0$とする。このとき、$f(v_2)=1,f(v_3)=0,\cdots,f(v_{2k+1})=0,f(v_1)=0$となる。$f(v_1)=f(v_{2k+1})$となり、$G$は2彩色不可能である。

4. (iii)$\rightarrow$(i)について

長さが偶数の閉路の通る頂点を$v_1,v_2,\cdots,v_{2k}$とする。$f(v_1)=0$とする。このとき、$f(v_2)=1,f(v_3)=0,\cdots,f(v_{2k})=0,f(v_1)=0$となる。$f(v_1)\ne f(v_{2k})$となり、閉路は2彩色可能である。また、閉路でない頂点は明らかに2彩色可能である。よって、$G$は2彩色可能である。

令和4年度

1. 筆記試験 プログラミング、計算機アーキテクチャ、情報数学から２科目を選択して解答してもら いました。解答時間は80分です。試験問題は別紙の通りです。
2. 口述試験 コンピュータ理工学に関する専門分野の基礎的事項、意欲、コミュニケーション力、思 考力を試問しました。試験時間は10分です。

プログラミング

問1

素数判定のプログラムの穴埋め

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

bool isPrimeA(const int N)｛
    for(int i=2; i*i<=N; ++i) {
        if(N%i==0) return false;
    ｝
    return true;
｝

bool isPrimeB(const int N)｛
    for(int i=2; i<N; ++i) {
        if(N%i==0) return false;
    ｝
    return true;

isPrimeAとisPrimeBについて、それぞれのプログラムの最悪計算量を求めなさい。

入力が素数であった場合に計算量が最悪となる。

• isPrimeAの最悪計算量は$O(\sqrt{N})$である。
• isPrimeBの最悪計算量は$O(N)$である。

isPrimeAの方が効率が良い。

問2

部分和問題を解くプログラムについて、以下の問いに答えなさい。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# include <iostream>
using namespace std;

bool isSubsetSum(const int a[], const int N, const int W){
    for(int bit = 0; bit < (1<<N); ++bit){
        int sum = 0;
        for(int i = 0; i < N; ++i){
            if(bit & (1<<i)) sum += a[i];
        }
        if(sum == W) return true;
    }
    return false;
}

int main(){
    const int N = 4, W = 19;
    const int a[] = {3,5,7,9};

    if(isSubsetSum(a,N,W)) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

関数boolisSubsetSum( )内の//(A)の行の｢bit&(1くくi)｣は,この部分和問題を解くためのどのような処理をおこなっているか.この中の｢&｣および｢くく｣の機能の説明を含めて, 150字程度で説明しなさい．

<<は左シフト演算子、&はAND演算子である。(1<<i)は下からi番目のビット(一番下を0番目とする)のみが1である数を表し、bit & (1<<i)はbitの下からi番目のビットが1であるかどうかを判定する。i番目のビットが立っているときに、a[i]を部分和の用いるとすると、bitが$0$から$2^N-1$まで変化することで、全ての部分和を求めることができる。

このプログラムの最悪時間計算量を求めなさい．

部分和問題の答えがNoだったときに、for文が2^N回実行される。よって、計算量は$O(2^N)$である。

このソースコードのアルゴリズムの時間計算量よりも効率の良い、$O(NW)$の時間計算量のアルゴリズムを説明しなさい。

動的計画法を説明する。

bool型の二次元配列dpを用意し、dp[i][j]の値を「i番目($a_0,a_1,\cdots a_{i-1}$)までの数からいくつかを選んで和をjにすることができるか」の判定問題の答えとする。 dp[0][0]はtrueとする。dp[i][j]の値は、dp[i-1][j]の値とdp[i-1][j-a[i]]の値を用いて、dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]]として求めることができる。dp[N][W]の値がtrueであれば、部分和問題の答えはYesである。

問3

都県名の一覧を処理するソースコードについて、答えなさい。

このソースコードをコンパイルして実行したときの,標準出力への出力をすべて書き出しなさい．

この実装では、リスト構造を用いている。 func1ではvのnextをpのnextに変更し、pのnextをvにしている。すなわち、pの次の要素をvに変更している。

func2では、nの次が指しているポインタをcurとし、curのprefを表示している。curはcurのnextに変更し、curのnextがnであれば終了する。

func3では、n以外のリストの要素を全削除している。

以上のことを踏まえると、

1
2
3
4
5

Tokyo->
Kanagawa->Tokyo->
Saitama->Kanagawa->Tokyo->
Nagano->Saitama->Kanagawa->Tokyo->
Nagano->Yamanashi->Saitama->Kanagawa->Tokyo->

となる。

main( )関数内の｢//(A)｣の行で呼び出されるfunc1( )について,このときに渡される実引数に基づく実行の様子を説明しなさい.必要であれば,図を用いてかまわない．

略

このソースコードで都県名の一覧に用いられているデータ構造の代わりに配列の使用を考える.設問(b)の処理においては,時間計算量の観点から,配列の方が効率が悪い.その理由を150字程度で説明しなさい．

このソースコードのアルゴリズムでは、どの場所に挿入するのも$O(1)$で行うことができるが、配列は挿入する場合、挿入する場所以降の要素を全てずらす必要があるため、最悪で$O(N)$の計算量がかかる。

情報数学

問1

2種の記号AとBの発生確率がそれぞれ$0.8$と$0.2$である記憶のない情報源Sを考える.このとき,以下の設問に答えなさい.計算には $\log_2 10=3.322$を用いてよい.また,答えは小数点以下第4位を四捨五入して表しなさい．

$S$のエントロピーを求めなさい．

$$ H(S) = -\sum p_i \log_2 p_i = -0.8 \log_2 0.8 - 0.2 \log_2 0.2 \simeq 0.722 $$

$\log 0.2 = \log (2/10) = \log 2 - \log 10 = -2.322 $、$\log 0.8 = \log (8/10) = \log 8 - \log 10 = -0.322$であることに注意。

$S$を2次に拡大してからハフマン符号化した場合に生成される符号を示しなさい。また、1情報源記号あたりの平均符号長を求めなさい。(b)

$S$を$2$次に拡大し、ハフマン符号化すると、以下のようになる($AB$と$BA$は逆でも良い)。

また、1情報源記号あたりの平均符号長は、$0.64\times 1 + 0.16\times 2 + 0.16\times 3 + 0.04\times 3 = 1.56$となる。

AとBの発生確率が偏っているので,ランレングス符号化を行う.ただし,Aは長さ4までのランを考え,Bは長さ1のランのみを考える.すなわち,下記の5種類のランを考える.これをハフマン符号化し,生成される符号を示しなさい.また, 1情報源記号当たりの平均符号長を求めなさい． (c)

1情報源記号あたりの平均符号長は、$0.4096\times 1 + 0.1024\times 3 + 0.128\times 3 + 0.16\times 3 + 0.2\times 3 = 2.08$となる。

(c)の符号化は(b)の符号化に比べて,どれだけ符号化の効率(1情報源記号当たりの平均符号長に対するエントロピーの比)が改善されているか答えなさい．

$(b)$のエントロピーは$1.444$、$c$のエントロピーは$2.468$である。

エントロピーは「一つの情報源に対してどれほどの情報量があるか」を示す指標であるから、エントロピーを平均符号長で割ることで、一つの記号あたりの情報量を示すことができる。

• $b$の場合、$1.444/1.56 = 0.925$
• $c$の場合、$2.468/2.08 = 1.186$

これらの差である$0.261$bit(binary unit)分だけ、符号化の効率が改善されている。

問2

固有値の問題。詳細は省略する。 $$ A=\begin{pmatrix} 2 & 1 & -1 \\ 1 & 0 & -1 \\ 1 & -1& 0 \end{pmatrix} $$

$A$の固有値と固有ベクトルは、 $$ \lambda_1 = 1, \lambda_2 = -1, \lambda_3 = 2 $$ $$ v_1 = (1,0,1)^T, v_2 = (0,1,1)^T, v_3 = (3,1,1)^T $$ である。

$$ x = (-1,-3,-1)^T = 2v_1-2v_2-v_3 $$ と表されるので、 $$ A^n x = 2 \cdot 1^n v_1 - 2 \cdot (-1)^n v_2 - 2^n v_3 $$ よって、 $$ A^n x = \begin{pmatrix} 2-3\cdot 2^n \\ -2\cdot (-1)^n - 2^n \\ 2 - 2 \cdot(-1)^n - 2^n \end{pmatrix} $$

令和3年度

プログラミング

問1

なんと、アルゴリズムではなくコンパイルの仕組みが出ています。？？？？？？？？？

• (ア)：プリプロセス
  • マクロの展開やヘッダファイルなどを処理する。
• (イ)：構文解析
  • 字句解析では、ifやelseやセミコロン、括弧などを解析する。
  • 構文解析では、字句解析をもとに構文構造をまとめる。
• (ウ)：アセンブリファイル
• (エ)：オブジェクトファイル
• (オ)：ライブラリファイル

実行ファイルの実行速度を高速化するために、コンパイラは様々な最適化を行う。

• 関数のインライン展開：関数呼び出しを関数の中身に置き換える。
• 定数の畳み込み：定数同士の計算を、計算結果に置き換える。
• ループの展開(アンローリング)：ループ処理の内容を展開する。
• 無用命令の削除：冗長で無用な命令を削除する。
• 定数伝搬：変数を定数で置き換える。
• 共通部分式の削除：同じ計算を複数回行う場合、一度計算した結果を変数に格納しておき、再利用する。
  • 例えば、a = b + c; d = b + c;というコードがあった場合、b + cを一度計算しておき、a = b + c; d = a;とする。
• ループ内不変式の移動：ループ内で変化しない変数の計算をループの外に移動する。

問2

二分木をC言語を用いて実装する。

• 着目ノードの左の部分技のすべてのノードの値は、着目ノードの値より小さく

• 着目ノードの右の部分木のすべてのノードの値は、着目ノードの値より大きい

• その声質から、木の最も右のノードが木に保持される値の最大値、ミットも左のノードの値が最小値である。

• 入力データが1,2,3,4,5,6,7,8のとき、1が根で、右の子が2、2の右の子が3、3の右の子が4、4の右の子が5、5の右の子が6、6の右の子が7、7の右の子が8となる。

• 入力データが4,6,2,8,1,5,3,7,-1のとき

1
2
3
4
5
6
7

    4
   / \
  2   6
 / \ / \
1  3 5  8
       /
      7

• ある整数がノードに含まれるかどうかの処理の計算量は、木の高さに依存する。
  • 最良の場合、木の高さが$O(\log n)$であるから、$O(\log n)$
  • 最悪の場合、木の高さが$O(n)$であるから、$O(n)$

問3

大きさ3の配列vを入力とし、次の条件を満たすようなvの要素を返す。

• 一つ以上の他の要素よりも大きいかまたは等しい。
• 一つ以上の他の要素よりも小さいかまたは等しい。

要するに、中央値を求めれば良い。中央値を求める問題を10問も解かされる謎の問題。

CかC++で実装せよ。

いくつか方法はある。

• バブルソートのようにスワップしながらソートし、真ん中の値を返す。
• 各v[i]について、それぞれ条件を満たすかを調べる。
• 最大値と最小値を求め、v[0]+v[1]+v[2]から最大値と最小値を引く。

一番実装が楽そうなのは3番目の方法。変な方法ではあるが、特に指定されていないので問題ないと思われる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int func(int v[3]) {
    int max = v[0];
    int min = v[0];
    int sum = 0;
    for (int i = 1; i < 3; i++) {
        if (v[i] > max) {
            max = v[i];
        }
        if (v[i] < min) {
            min = v[i];
        }
        sum += v[i];
    }
    return sum - max - min;
}

情報数学

問1から3のうち、2問選択して解答する。

問1

$r(n+3)$と$r(n)$の差が$3$の倍数であることを証明せよ。 $$ r(n) = \sum_{i=1}^{m} d_i \quad (d_iは10進数表記でi番目の桁の数字を表し、mはnの桁数) $$

方針として、$n$を$3$で割ったあまりと、各位の数の和を$3$で割ったあまりが等しいことを証明すれば良い。

$$ \begin{align} n &\equiv \sum_{i=1}^{m} 10^{i-1}d_i \pmod 3 \\ &\equiv \sum_{i=1}^{m} (3\times 333\cdots 3 + 1)^{i-1}d_i \pmod 3 \\ &\equiv \sum_{i=1}^{m} 1^{i-1}d_i \pmod 3 \\ &\equiv \sum_{i=1}^{m} d_i \pmod 3 \\ &\equiv r(n) \pmod 3 \end{align} $$

よって、$n \equiv r(n) \pmod 3$、つまり$n$を$3$で割ったあまりと、各位の数の和を$3$で割ったあまりが等しい。 $n$を$3$で割ったあまりを$a$と置けば、$n = 3k+a$と整数$k$を用いて表せる。 $n+3=3k+a+3=3(k+1)+a$であるから、$n+3$を$3$で割ったあまりも$a$である。 したがって、$r(n+3) - r(n) \equiv a - a \equiv 0 \pmod 3$である。

問2

ある会社は、A,B,C社から同じ製品を2:3:5の比率で購入している。A,B,C社の製品にはそれぞれ2.5%,1.5%,1.0%の割合で不良品が含まれている。

(a) 購入した製品の中から1つを選んだとき、不良品である確率を求めよ。

• A社の製品を選び、かつ不良品である確率は$\frac{2}{10}\times \frac{25}{1000} = \frac{1}{200}$
• B社の製品を選び、かつ不良品である確率は$\frac{3}{10}\times \frac{15}{1000} = \frac{9}{2000}$
• C社の製品を選び、かつ不良品である確率は$\frac{5}{10}\times \frac{10}{1000} = \frac{1}{200}$
• したがって、不良品である確率は$\frac{1}{200} + \frac{9}{2000} + \frac{1}{200} = \frac{29}{2000}$

(b) 購入した製品の中から1つを選んだら不良品であった。この不良品が、A社、B社、C社の製品である確率をそれぞれ求めよ。

ベイズの定理を用いる(個人的に、特にベイズの定理という名前を認識して使う必要はないと思う)。

• A社の製品である確率は$\frac{1}{200} \div \frac{29}{2000} = \frac{10}{29}$
• B社の製品である確率は$\frac{9}{2000} \div \frac{29}{2000} = \frac{9}{29}$
• C社の製品である確率は$\frac{1}{200} \div \frac{29}{2000} = \frac{10}{29}$
  • (ここで、$\frac{10}{29} + \frac{9}{29} + \frac{10}{29} = \frac{29}{29} = 1$であることを確認できる。)

問3

固有値に関する問題。詳細は省略する。 $$ A=\begin{pmatrix} 3 & -2 & -1 \\ 0 & 1 & -1 \\ 2 & 1 & 5 \end{pmatrix} $$

(a) 行列$A$の行列式を求めよ。

$24$

(b) 行列$A$の固有値を求めよ。

$\lambda_1 = 2, \lambda_2 = 3, \lambda_3 = 4$ $a_1= (-1,-1,1)^T, a_2 = (-3,-2,4)^T, a_3 = (-1,-1,3)^T$

(c) 対角化する行列$P$とその逆行列$P^{-1}$を求めよ。

$$ P = \begin{pmatrix} -1 & -3 & -1 \\ -1 & -2 & -1 \\ 1 & 4 & 3 \end{pmatrix} $$

$$ P^{-1} = \frac{1}{24}\begin{pmatrix} 6 & 9 & 3 \\ -2 & 17 & 3 \\ -2 & -7 & 3 \end{pmatrix} $$

このとき、$P^{-1}AP = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 4 \end{pmatrix}$ である。

令和2年度

プログラミング

問1

二分木について、「親から子へ」「左から右へ」の順番を原則に答えよ (a) 深さ優先探索、幅優先探索をしたとき、訪問する順番を答えよ。

• 深さ優先探索: A,B,D,E,H,I,C,F,G,J
• 幅優先探索: A,B,C,D,E,F,G,H,I,J

(b) in-order, pre-order, post-orderで木を巡回したとき、訪問する順番を答えよ。

• pre-order(行きがけ順、前順): A,B,D,E,H,I,C,F,G,J
• in-order(通りがけ順、中順): D,B,H,E,I,A,F,C,J,G
• post-order(帰りがけ順、後順): D,H,I,E,B,F,J,G,C,A

• stackを使っているので、右を先に探索するためには、左、右の順番でpushする必要がある。

問2

d[]には-10000から10000までの整数が格納される。d[]の最大値と最小値を求めるプログラムを作成する。

1
2
3
4
5
6
7

int d[100], minimum, maximum, i;
// dに値を格納する処理
mininmum = 10000; maximum = -10000;
for (i = 0;i < 100;i++){
    if (d[i] > maximum) maximum = d[i];
    else if (d[i] < minimum) minimum = d[i];
}

(a) 上記のプログラムでは最大値と最小値が正しく求められない場合がある。その場合を示せ。

elseが使われているため、maximumとminimumが同時に更新されることがなくなっている。 すなわち、d[0],d[1],d[2],...,d[99]が常に増え続けるよう(ただしd[0]!=-10000)な入力に対してはminimumが更新されず、10000のままとなってしまう。

(b) 上記のプログラムを修正し、最大値と最小値を正しく求めるプログラムを作成せよ。

単に、else ifをifに変えるだけで良い。

(c) d[]の中に最小あるいは最大を取る値が複数個含まれていた場合に、最小値や最大値の値がそれぞれ何個含まれているかを求めるプログラムを作成せよ。

ループを$2$回回せば良い。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int d[100], minimum, maximum, i, count_min, count_max;
// dに値を格納する処理
mininmum = 10000; maximum = -10000;
for(i = 0;i < 100;i++){
    if (d[i] > maximum) maximum = d[i];
    if (d[i] < minimum) minimum = d[i];
}

count_min = 0; count_max = 0;
for(i = 0;i < 100;i++){
    if (d[i] == maximum) count_max++;
    if (d[i] == minimum) count_min++;
}

問3

(a) 値がコメントのようになるように(1),(2),(3),(4)を埋めよ。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void rotate(int *x, int *y, int *z){
    int tmp;
    // (1)
    // (2)
    // (3)
    // (4)
}

int main(void){
    int a=7, b=61, c=199;
    // a=7, b=61, c=199
    rotate(&a, &b, &c);
    // a=61, b=199, c=7
    rotate(&a, &b, &c);
    // a=199, b=7, c=61
}

a,b,cがb,c,aの順番になれば良い。

1
2
3
4
5

int tmp;
tmp = *x;
*x = *y;
*y = *z;
*z = tmp;

(b) 関数定義において引数をポインタとする実装方法の特徴と有効な使い方について簡単に説明せよ。また、この実装方法の危険性についても説明せよ。

ポインタを用いると、値をコピーせずに、関数内で値を変更することができる。また、値をコピーする必要がないため、メモリの節約になる。ただし、ポインタはアドレスを指すため、誤ってアドレスの変更やアドレスの指す値の変更をしてしまうと、予期せぬ動作をする可能性がある。

情報数学

問1

次の3つの命題を仮定したとき、これらの命題から得られる結論をすべて求めよ。

• $P_1$: ソクラテスは、人である。
• $P_2$: 人はいつか死ぬ。
• $P_3$: ベニクラゲは死なない。

整理すると、

• ソクラテス$\rightarrow$人間
• 人間$\rightarrow$死ぬ
• ベニクラゲ$\rightarrow$死なない

また、これらの対偶も成り立つので、

• 人間ではない$\rightarrow$ソクラテスではない
• 死なない$\rightarrow$人間ではない
• 死ぬ$\rightarrow$ベニクラゲではない

これらを組み合わせると、

1
2

ソクラテス -> 人間 -> 死ぬ -> ベニクラゲではない
ベニクラゲ -> 死なない -> 人間ではない -> ソクラテスではない

よって、$P_1,P_2,P_3$の他に、

• ソクラテスは死ぬ
• ソクラテスはベニクラゲではない
• 人間はベニクラゲではない
• ベニクラゲは人間ではない
• ベニクラゲはソクラテスではない
• 死なないならばソクラテスではない

の6つの結論が得られる。

問2

$R$を集合$A$上の同値関係とする。各要素$a\in A$に対して$a$と同値関係にある要素の集合を同類値と呼び、$[a]$と表す。すなわち$[a]= \lbrace x|(a,x)\in R \rbrace$である。このとき、次を証明せよ。

同値関係の定義は、関係が反射律、対称律、推移律を満たすことである。

(a) $A$の各要素$a\in A$に対して、$a\in[a]$である。

同値類は反射律を満たすから、$(a,a)\in R$である。よって、$a\in[a]$である。

(b) $[a]=[b]$のとき、かつこのときに限り、$(a,b)\in R$である。

$\rightarrow$の証明： (a)の結論より、$ a \in [a]$である。また、$[a]=[b]$であるので、$a \in [b]$である。よって、$(a,b)\in R$である。

$\leftarrow$の証明： $R$は同値関係であるため、$(a,b)\in R$のとき$a,b$は同値である。よって、$[a]=[b]$である。

(c) $[a]\ne [b]$ならば、$[a]$と$[b]$は互いに素である。

対偶を示す。$a,b$が互いに素ではないとき、$a,b$は同値である。よって、(b)より$[a]=[b]$である。

問3

固有値に関する問題。詳細は省略する。 $$ A=\begin{pmatrix} 0 & 1 & 2 \\ -4 & 1 & 4 \\ -5 & 1 & 7 \end{pmatrix} $$

行列式は$10$

固有値と固有ベクトルは、$1$に対して$(1,-1,1)^T$、$2$に対して$(1,0,1)^T$、$5$に対して$(1,1,2)^T$である。

平成31年度

プログラミング

問1

$n$子の整数より構成される配列$x$から整数$t$を探索する関数searchを作る。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int search(int t, int* x, int n){
    int lower, upper, middle;
    lower = 0;
    upper = n01;
    while(lower <= upper){
        middle = (lower + upper) /2;
        if(x[middle] < t)
            lower = middle; //(1)
        else if (t < x[middle])
            upper = middle; //(2)
        else
            return middle;
    }
    return -1;
}

(a)このプログラムが正しく動作するのに、xは昇順と降順どちらである必要があるか(ただし、狭義単調増加、狭義単調減少を指す)。

プログラムでは、二分探索を行っている。x[middle]がtより小さいときに、下限lowerがmiddleにおきかわっている。middleより前を見る必要がない、ということだから、xは昇順である必要があることがわかる。

(b)入力によって、プログラムが停止しない場合がある。例えば、x={1,2,3}で、t=3のときに停止しない。プログラム中の(1),(2)の部分を変更して、このような場合にも停止するようにせよ。

lower = middle + 1、upper = middle - 1とすればよい。(要検証)

(c)xが(a)とは逆の順序である場合に、(1),(2)の部分を修正してプログラムが動作するようにせよ。

(b)で、(1)と(2)を逆にすればよい。

(d) このプログラムの計算量が$O(\log n)$になることを説明せよ。

一回で半分になるので、ループはおよそ$\log_2 n$回実行される。

問2

(a) ヒープに関する説明の穴埋め問題

• ヒープは、要素の「あつまり」を表す ?型のデータ構造である。抽象的機能として、要素の並びを保持し、挿入と削除が可能な優先度付きキューの実装の一つと位置づけられる。一般に以下の2つの性質を持つ2分木と定義され、性質1より最小要素は必ず根頂点に格納される。
• 性質1：略
• 性質2：略

(b)n子の整数より構成される配列xに対し、以下の<対応付け規則>から構成される2分木をxの2分木と呼ぶ。配列x={20,18,13,19,24,15,28,40}(この順番どおりに格納されている)の2分木を図示しなさい。

• 規則1:x[0]を根頂点とする。
• 規則2:$0\leq i \leq (n-1)/2$を満たす整数$i$に対し、x[2*i+1]をx[i]の左の子とする。
• 規則3:$0\leq i \leq (n-2)/2$を満たす整数$i$に対し、x[2*i+2]をx[i]の右の子とする。

具体例を考えれば良い。

• x[0]が根である。
• x[0]の左の子がx[1]で、右の子はx[2]である。
• x[1]の左の子がx[3]で、右の子はx[4]である。
• x[2]の左の子がx[5]で、右の子はx[6]である。
• 以下同様

これは単に、上から下へ、左から右に、順番に並べたものと一致する。

1
2
3
4
5
6
7

          20
        /    \
      18      13
     /  \    /  \
   19   24  15  28
  /
40

(c) 次ページのC言語のプログラムは、配列xの各要素を移動する関数shiftを表している。(b)の配列x={20,18,13,19,24,15,28,40}について、shift(0,x,8)実行したときのxを答えなさい。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void shift(int i, int* x, int n){
    int parent, child, temp;
    parent = i;
    child = 2*parent + 1;
    while(child < n){
        if(x[child] < x[parent]){
            temp = x[child];
            x[child] = x[parent];
            x[parent] = temp;
            parent = child;
            child = 2*parent + 1;
        }else{
            break;
        }
    }
}

• 初期はx={20,18,13,19,24,15,28,40}でparent = 0, child = 1

• x[1] < x[0]なので、x={18,20,13,19,24,15,28,40}でparent = 1, child = 3

• x[3] < x[1]なので、x={18,19,13,20,24,15,28,40}でparent = 3, child = 7

• x[7] < x[3]なので、変化はなくx={18,19,13,20,24,15,28,40}で終了

• (d) (c)の結果のxを、二分木をヒープにするには、プログラムにどのような処理を追加すればよいか。

任意の配列xではなく、少なくとも(c)で回答したxについてヒープになれば良い。 余談ではあるが、任意のxについてヒープにする必要があると勘違いをし、非常に悩んだ。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void shift(int i, int* x, int n){
    int parent, child, temp;
    parent = i;
    child = 2*parent + 1;
    while(child < n){
        if(child+1<n)if(x[child] > x[child + 1])child ++;
        if(x[child] < x[parent]){
            temp = x[child];
            x[child] = x[parent];
            x[parent] = temp;
            parent = child;
            child = 2*parent + 1;
        }else{
            break;
        }
    }
}

問3

省略

情報数学

問1

40名のクラスについて、選択科目A,B,Cの履修状況は以下のとおりである。

• A,B,Cのそれぞれの履修者は18名
• 少なくともAとBを履修している者は9名
• 少なくともAとCを履修している者は8名
• 少なくともBとCを履修している者は5名
• 一課目以上履修している学生は35名

(a)1科目も履修していない学生 (b)A,B,Cの3科目をすべて履修している学生 (c)A,Bのみを履修している学生 (d)A,Cのみを履修している学生 (e)Aのみを履修している学生、をそれぞれ求めなさい。

ベン図を書いて、パズルチックに解く。あるいは、包除原理を用いる。 3要素の場合の包除原理は以下の通り。 $$ |A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C| $$ これを今わかっている情報に当てはめる。 $$ 35 = 18 + 18 + 18 - 9 - 8 - 5 + |A\cap B\cap C| $$ よって、$|A\cap B\cap C| = 3$である。

なお、この程度の数字の大きさであれば、適当に数を当てはめていって辻褄が合うようなものを探すという方法でも良いだろう。

あとは、単純な足し算や引き算で求められ、$(a)5,(b)3,(c)6,(d)5,(e)4$

問2

$R$を集合$A$上の二項関係とする。 (a) $R$が同値関係であるときに満たされる$3$つの性質について、空欄を埋めなさい。

• 任意の$a\in A$に対して$aRa$が成立するとき、$R$は反射的である。
• 任意の$a,b\in A$に対して$aRb\Rightarrow bRa$が成立するとき、$R$は対称的である。
• 任意の$a,b,c\in A$に対して$aRb\land bRc\Rightarrow aRc$が成立するとき、$R$は推移的である。

(b) 整数$m>1$について、$2$つの整数$x,y$に対して、$x-y$が$m$で割り切れるとき、$x$と$y$は$m$は法として合同であると言い、$x\equiv y\pmod{m}$と表す。この関係が、整数の集合$\mathbb{Z}$上の同値関係であることを示しなさい。

• 反射的であること
  • 任意の$x$について、$x-x=0$は$m$で割り切れるので、$x\equiv x\pmod{m}$である。
• 対称的であること
  • 整数$k$を用いると$x-y=mk$と表され、$y-x=-mk$は$m$で割り切れるので、$y\equiv x\pmod{m}$である。
• 推移的であること
  • 整数$k,l$を用いると$x-y=mk,y-z=ml$と表され、$x-z=(x-y)+(y-z)=m(k+l)$は$m$で割り切れるので、$x\equiv z\pmod{m}$である。

問3

行列$A$に関して答えなさい

$$ A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 2 \\ 1 & 2 & 0 \end{pmatrix} $$

(a) $A$の逆行列は存在するか。存在するならば、求めなさい。

$|A|=-1\ne 0$なので、$A$は正則である。よって、$A^{-1}$が存在する。

$$ A^{-1} = \begin{pmatrix} 4 & -2 & -1 \\ -2 & 1 & 1 \\ -1 & 1 & 0 \end{pmatrix} $$

(b) $A$を隣接行列としてもつ多重グラフ$G=(V,E)$を描きなさい。ただし、頂点集合$V={v_1,v_2,v_3}$とする。

問4

(a) 正$4$面体サイコロの、出目を確率変数$X$とすると、確率分布表は以下の通りである。

$X$	$1$	$2$	$3$	$4$
$P(X=x)$	$\frac{1}{4}$	$\frac{1}{4}$	$\frac{1}{4}$	$\frac{1}{4}$

2つのサイコロを振り、2つの出目の和を$Y$とすると、$Y$の確率分布表と、期待値を求めなさい。

• $Y=2$は$(1,1)$
• $Y=3$は$(1,2),(2,1)$
• $Y=4$は$(1,3),(2,2),(3,1)$
• $Y=5$は$(1,4),(2,3),(3,2),(4,1)$
• $Y=6$は$(2,4),(3,3),(4,2)$
• $Y=7$は$(3,4),(4,3)$
• $Y=8$は$(4,4)$

期待値は、 $$ E[Y]= 2\cdot \frac{1}{16} + 3\cdot \frac{1}{8} + 4\cdot \frac{3}{16} + 5\cdot \frac{1}{4} + 6\cdot \frac{3}{16} + 7\cdot \frac{1}{8} + 8\cdot \frac{1}{16} = \frac{40}{8} = 5 $$

(b) $n$人いるとき、少なくとも$2$人が同じ誕生日である確率を求めなさい。ただし、$1<n<365$であり、閏年は考えないとする。

少なくともは、余事象を考えるとやりやすい。すなわち、$n$人とも誕生日が異なる確率を求め、それを$1$から引けばよい。

$$ 1-\frac{365}{365}\cdot \frac{364}{365}\cdot \frac{363}{365}\cdots \frac{365-n+1}{365} = 1-\frac{365!}{(365-n)!365^n} $$

平成30年度

プログラミング

問1

次の算術式を逆ポーランド記法(後置記法)で表しなさい。
(a) $((A+B)\times C)\div (D-(E\div F))$
(b) $(A+B)\div (C-D)+(E-F) \div G$

逆ポーランド記法とは、演算子を後ろに置く記法である。例えば、$A+B$は$AB+$と表される。括弧や乗算除算の順序に注意する。

• (a): $A B + C \times D E F \div - \div$
• (b): $A B + C D - \div E F - G \div +$

問2

逆ポーランド記法で書かれた四則演算の算術式を計算することを考える。スタックを用いる方法を説明しなさい。

スタックを用いる方法は、以下の通りである。

• 前から順に、処理をしていく。
• 被演算子(数値)が現れたら、スタックに積む。
• 演算子が現れたら、スタックから2つ取り出し、演算子に関する計算を行い、結果をスタックに積む。

問3

次の手続きを実行したとき、手続きが終了するまでに、比較「x <= 5000」が何回行われるかとその理由とともに答えなさい。

1
2
3
4
5
6

x = 0;
y = 0;
while(x<=5000){
    x = x+y;
    y = y+1;
}

具体的な処理をみていく。

• 初期値はx=y=0
• x<=5000であり、xにyが加算され、yに1が加算される。x=0,y=1
• x<=5000であり、xにyが加算され、yに1が加算される。x=1,y=2
• x<=5000であり、xにyが加算され、yに1が加算される。x=3,y=3
• x<=5000であり、xにyが加算され、yに1が加算される。x=6,y=4

このコードはxが5000以下の間、xに0,1,2,3,...を加算し続けるプログラムである。 y=101まで足されたときに、x=5050となり、x<=5000がfalseとなる。よって、比較は103回行われる(0から加算を始めていること、5000を超えたときにも比較が一度行われることに注意)。

問4

双方向リスト構造に関する問題(詳細は省略)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

if (root = p){ /*削除対象のセルがリストの先頭のとき*/
    (1) root = root.next;
    if (root != nil) //リストに要素があるとき
        (2) p.next.prev = nil;
}else if (tail = p){ /*削除対象のセルがリストの末尾のとき*/
    tail = tail.prev;
    if ( (3) tail != nil) //リストに要素があるとき
        (4) p.prev.next = nil;
}else{
    (5) p.prev.next = p.next;
    (6) p.next.prev = p.prev;
}

問5

根付き木に関する問題(詳細は省略)。

1
2
3
4
5

v = (1) FirstChild[Parent[v]];
while( v != nil ){
    write Info[v];
    v = (2) NextBrother[v];
}

vが親の第1子であるとは限らないため、一度親を参照し、その第1子を参照する必要がある。

問6

次の主手続きを実行した後の変数$x$と$y$のの値をその理由とともに答えなさい。ただし、手続きaddsub(x,y)の仮引数xは値呼び出し、仮引数yは参照呼び出しを家庭留守。

1
2
3
4

//主手続き
x = 10;
y = 5;
addsub(y,x);

1
2
3

//手続き addsub(x,y)
x = x+y;
y = x-y;

引数(x,y)が逆になっていてややこしいので、addsub(a,b)を考える。

1
2
3

//手続き addsub(a,b) aはコピー、bは参照
a = a+b;
b = a-b;

a=5,b=10だから、a=15,b=5となる。aはコピーなので、yには影響しない。bは参照なので、xに影響する。 よて、x=5,y=5となる。

問7

オブジェクト指向設計における、継承とポリモルフィズムの考え方を説明し、それらを利用する利点を述べなさい。

継承とは、特定のオブジェクトの機能を引き継いで使用することであrう。同じ機能を持つオブジェクトが複数ある場合、それらの機能を共通化することで、プログラムの見通しを良くすることができる。

ポリモーフィズムとは、目的が同じ機能だが、処理内容が異なる場合に、同じ名前をつけて処理を行うことである。ポリモーフィズムにより操作方法を統一することで、プログラムの見通しを良くすることができる。

情報数学

問1

(a) $p,q$を命題とする、$p\rightarrow q$が真であることを証明するための、直接法、対偶法、背理法を説明しなさい。

• 直接法：$p$を真と仮定して、$q$が真であることを示す。
• 対偶法：$\lnot q$を仮定して、$\lnot p$が真であることを示す。
• 背理法：$p \land \lnot q$を仮定して、矛盾が生じる(偽となる)ことを示す。

(b) 命題関数$P(n)$を「最初の$n$個の正の奇数の和は$n^2$である」とする。全ての正の奇数$n$に対して$P(n)$が真であることを数学的帰納法を用いて証明しなさい。

なぜか正の奇数$n$に限定されているが、$n$が正の偶数の場合も成り立つので、$n$が正の整数のときに成り立つことを示せば良い。

• $n=1$のとき、始めの1個の正の奇数の和は$1$であり、$1^2=1$であるから、$P(1)$は真である。
• $n=k$のとき、最初の$k$個の正の奇数$1,3,5,…,2k-1$の和は$k^2$であると仮定する。$n=k+1$のとき、最初の$k+1$個の正の奇数$1,3,5,…,2k-1,2k+1$の和は、$k^2+2k+1=(k+1)^2$であるから、$P(k+1)$は真である。
• 以上より、数学的帰納法より全ての正の整数$n$に対して$P(n)$が真であることが示された。よって全ての正の奇数$n$に対して$P(n)$が真であることが示された。

問2

行列に関する問題(詳細は省略)。

$$ A = \begin{pmatrix} 1 & 0 & 1 & 2 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 0 \end{pmatrix} $$

$|A|=2$

$$ A^2 = \begin{pmatrix} 2 & 3 & 6 & 2 \\ 2 & 1 & 1 & 2 \\ 3 & 2 & 2 & 2 \\ 3 & 3 & 2 & 0 \end{pmatrix} $$

v1からv3への長さ3のパスの本数は、$A^3$の1行3列目の要素と等しい。よって、12本である。

問3

2つの箱A,Bがあって、箱Aには赤玉1個と白玉5個、箱Bには赤玉5個と白玉1個がある。

(a) 任意に箱を選んで1個の玉を取り出したとき、その玉が赤色である確率を求めなさい。

$$\frac{1}{2}\times\frac{1}{6}+\frac{1}{2}\times\frac{5}{6}=\frac{1}{2}$$

(b) 任意に箱を選んで1個玉を取り出し元の箱に戻し、もう一度同じ箱から取り出す、二回連続で取り出した玉が赤色である確率を求めなさい。

$$\frac{1}{2}\times\frac{1}{6}\times\frac{1}{6} + \frac{1}{2}\times\frac{5}{6}\times\frac{5}{6}=\frac{13}{36}$$

(c) 任意に箱を選んで1個取り出したら赤玉であった。その玉を元の箱に戻し、もう一度同じ箱から取り出して赤玉である確率を求めなさい。

• 赤→白の順で取り出す場合 $\frac{1}{2}\times\frac{1}{6}\times\frac{5}{6}+\frac{1}{2}\times\frac{5}{6}\times\frac{1}{6}=\frac{5}{36}$
• 赤→赤の順で取り出す場合 $\frac{1}{2}\times\frac{1}{6}\times\frac{1}{6}+\frac{1}{2}\times\frac{5}{6}\times\frac{5}{6}=\frac{13}{36}$

よって、ベイズの定理より $$ \frac{\frac{5}{36}}{\frac{5}{36}+\frac{13}{36}}=\frac{5}{18} $$

平成29年度

プログラミング

問1

(a) ホワイトボックステストについて答えなさい。

• 命令網羅：全ての命令(条件分岐を除く)を最低1回は通すようにするテスト。
• 判定条件網羅(分岐網羅)：それぞれの判定条件の結果が真となるケース、負となるケースを作成し、全ての分岐を最低1回は通すようにするテスト。
• 複数条件網羅：全ての判定条件の組み合わせにおける全ての可能な組み合わせを網羅し、かつ全ての命令を一度は実行する。

(b)

次の２つを用意すればいい。命令網羅であるため、命令がない②を通る必要はない。

• 1 -> 3 -> 5 -> 6 -> 8
• 1 -> 4 -> 5 -> 7 -> 8

問2

オブジェクト指向プログラミング言語に関する説明文を埋めなさい。

クラスは階層構造をもってそのｎ属性や操作を継承できる。継承して新たに定義されたクラスを元のクラスの下位クラス(サブクラス)とよび、その元のクラスを上位クラス(スーパークラス)とよぶ。このような階層構造をもつクラスの間の県警には、「自動車-トラック」のような「is-a」関係と、「自動車-タイヤ」のような「has-a」関係がある。

問3

以下のCで書かれた関数f_a,f_b,f_cのそれぞれについて、引数にN=6が渡されたとときの戻り値を求めよ。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int f_a(int N){
    int count = 1;

    for(int i = 3; i <= N; i+=2){
        for (int j = 3; j<=i; j+=2){
            if(i==j)++count;
            if(i%j==0)break;
        }
    }
}

int f_b(int N){
    if(N<=1)return N;
    else return f_b(N-1)+f_b(N-2);
}

int f_c(int N){
    return (N+7)>>3<<3;
}

• f_a(6)：関数の目的がよくわからないが、i=3,5のときにi==jになるので、戻り値は3となる。
• f_b(6)：フィボナッチ数列を計算している。f_b(0),f_b(1),...と順番に計算していくとわかりやすい。戻り値は8。
• f_c(6)：6+7=13を2進数にすると1101であり、右に3ビットシフトすると1で、左に3ビットシフトすると1000である。戻り値は8。

問4

(a)initList(&list, N, data)によって作成されるリスト構造、(b)func1()とfunc2()のそれぞれの時間計算量について説明しなさい。

• (a) Node構造体は次のNodeを指すnextとprevのポインタと要素valueを持っている。先頭と末尾が連結している双方向リストを生成するinitList(&list, N, data)により、listのnextがdata[0]をvalueに持つノード、その次がdata[1]をvalueに持つノード、…と続き、最後のノードのnextがlistを指すようになる。また、prevは前の要素を指し、最初のノードのprevは最後のノードを指すようになる。(図は省略)。

• (b) func1()はlistの先頭から末尾まで順番に要素を取り出し、vと等しい要素があればnに加算している。これは、リストに含まれるvの個数をカウントする関数であり、計算量はノードの長さをNとすると$O(N)$。func2()はlistが空ではない場合に、listの一つ前の要素を削除する関数である。計算量は$O(1)$。(図は省略)。

情報数学

問1

(a) 3変数$x,y,z$からなる方程式$x+y+z=10$を考える。。$x,y,z$が非負整数とすると、この方程式の解である$(x,y,z)$の組の個数はいくつか。

$10$個のボールと$2$個の仕切りを一列に並べる場合の数と等しい。よって、$_{10+2}\mathrm{C}_{2}=66$通り。

(b) 2変数$x,y$と実定数$\alpha,\beta$に関した、$x+y=1$と$\alpha,\beta>0$が成り立っている。
(1) $x,y$が実数であるとき、$\alpha x + \beta xy$の最大値とそのときの$x$を求めなさい。
(2) $x,y\in \lbrace 0,1 \rbrace$であるとき、$\alpha x + \beta xy$の最大値とそのときの$x$を求めなさい。

(1) $y=1-x$を代入し、平方完成すれば良い。 $$ \begin{align} \alpha x + \beta xy &= \alpha x + \beta x(1-x) \\ &= \alpha x + \beta x - \beta x^2 \\ &= -\beta x^2 + (\alpha + \beta)x \\ &= -\beta \left(x^2 - \frac{\alpha + \beta}{\beta}x + \frac{(\alpha + \beta)^2}{4\beta^2} \right) + \frac{\beta(\alpha + \beta)^2}{4\beta^2} \\ &= -\beta \left(x - \frac{\alpha + \beta}{2\beta} \right)^2 + \frac{(\alpha + \beta)^2}{4\beta} \\ \end{align} $$ よって、$\beta>0$より、$x=\frac{\alpha + \beta}{2\beta}$のとき、$\alpha x + \beta xy$は最大値$\frac{(\alpha + \beta)^2}{4\beta}$をとる。

(2) 場合分けする。

• $x=0,y=0$のとき、$\alpha x + \beta xy=0$
• $x=0,y=1$のとき、$\alpha x + \beta xy=0$
• $x=1,y=0$のとき、$\alpha x + \beta xy=\alpha$
• $x=1,y=1$のとき、$\alpha x + \beta xy=\alpha + \beta$

よって、$\alpha x + \beta xy$の最大値は$\alpha + \beta$であり、そのときの$x$は$1$である。

問2

無向グラフ$G=(V,E)$で、$2$頂点$u,v\in V$を結ぶパスが存在することを$uRv$で表す。このとき、$R$は同値関係であることを示しなさい。

• 反射律：明らかにパス$[u]$が存在するので、$uRu$が成り立つ。
• 対称律：$uRv$が成り立つとき、$u$から$v$へのパス$[u,a_1,a_2,…,a_n,v]$が存在する。このとき、$v$から$u$へのパス$[v,a_n,a_{n-1},…,a_1,u]$が存在するので、$vRu$が成り立つ。
• 推移律：$uRv$かつ$vRw$が成り立つとき、$u$から$v$へのパス$[u,a_1,a_2,…,a_n,v]$と$v$から$w$へのパス$[v,b_1,b_2,…,b_m,w]$が存在する。このとき、$u$から$w$へのパス$[u,a_1,a_2,…,a_n,v,b_1,b_2,…,b_m,w]$が存在するので、$uRw$が成り立つ。
• よって、$R$は同値関係である。

問3

次のようなテストを受験し、合格する必要がある。

• 無限の数の問題が用意されており、一問ずつ出題され、解答を行う。
• 各問に正解すると得点1を得て、不正解すると得点-1を得る。
• 得点の合計が3になるとテストに合格となり、受験が終了する。
  各問に正解する確率が$2/3$とするとき、次の設問に答えなさい。
  (a) 5問に解答した時点で、テストに合格する確率はいくらか。
  (b) 6問に解答した時点で、得点の合計が2である確率を求めなさい。
  (c) テストに合格するまでに8問以上に解答する必要がある確率を求めてください。

$i$問目を解いたときに$j$点を獲得している場合の数を求める。

$i$問目まで解いたときに$j$点を獲得している場合の数$A_{ij}$は、次の漸化式で計算できる。

• $A_{0j}=0 \quad (全てのj)$
• $A_{i2} = A_{i-1,1} \quad (全てのi)$
• $A_{ij}=A_{i-1,j-1}+A_{i-1,j+1} \quad (その他の場合)$

(a) 表より、$A_{5,3}=3$である。また、4問正解して1問不正解だから、 $$ \left( \frac{2}{3} \right)^4 \times \left( \frac{1}{3} \right)^1 \times 3 = \frac{16}{81} $$

(b) 表より、$A_{6,2}=9$である。また、6問正解して2問不正解だから、 $$ \left( \frac{2}{3} \right)^4 \times \left( \frac{1}{3} \right)^2 \times 9 = \frac{16}{81} $$

(c) 余事象は、$7$問目までに合格する確率であり、その確率は、表を見ながら、 $$ \left( \frac{2}{3} \right)^3 \times \left( \frac{1}{3} \right) ^0 \times 1 + \left( \frac{2}{3} \right)^4 \times \left( \frac{1}{3} \right) ^1 \times 3 \\ + \left( \frac{2}{3} \right)^5 \times \left( \frac{1}{3} \right) ^2 \times 9 = \frac{152}{243} $$ よって、答えは $$ 1 - \frac{152}{243} = \frac{91}{243} $$

平成28年度

問題が見つかりませんでした！

平成27年度

プログラミング

問1

浮動小数点で表現された多くの数を加算する。加算結果に含まれる誤差をもっとも小さくなるようにするには、以下のいずれの方法が良いかを、その理由とともに100～150字程度で述べなさい。

1. 数を絶対値の小さい順に整列し、絶対値の小さい数から始めて順に絶対値の大きい数へと加算してゆく。
2. 絶対値の大きい数から始めて順に絶対値の小さい数へと加算してゆく。

2の絶対値を大きい数から順に加算する方法が良い。\

浮動小数点型は、絶対値の大きな数と小さな数を加算したときに、下の方の桁の精度が崩れ、誤差が生じる情報落ちが起こる。絶対値の大きな数から順に加算しておくと、符号が異なり絶対値が近い数同士の加算が行われる可能性があり、その結果が絶対値の小さな数であれば情報落ちの度合いが小さくなる。

以下のコードを試してみるとよくわかる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>

main()
{
    float a, b, c, d, s, t;

    a = 0.1111;
    b = 0.1111;
    c = 123456.0;
    d = -123456.0;

    s = 0.0;
    t = 0.0;
    s += a; s += b; s += c; s += d;
    t += d; t += c; t += b; t += a;

    printf("%f\n", s);
    printf("%f\n", t);
    // s = 0.218750
    // t = 0.222200
}

問2

N=10としたとき、次の関数fa(),fb(),fc(),fd()の実行結果を求めなさい。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

int fa(int N){
    int i,j,kcount;

    count = 0;
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            for(k=1;k<=N;k++){
                count=count+1;
            }
        }
    }
    return count;
}

int fb(int N){
    int count;
    if(N==0)return 1;
    else{
        count = fb(N-1) + fb(N-1);
        return count;
    }
}

int fc(int N){
    int i,j,count;

    count = 0;
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            count=count+1;
        }
        if(i%2==1){
            count=count+1;
        }
    }
    return count;
}

int fd(int N){
    int i,j,count;

    count=0;
    i=1;
    while(i<=N){
        count = count +1;
        j = 1;
        while(j<=N){
            count=count+1;
            j=j*2;
        }
        i++;
    }
    return count;
}

• fa()：$N^3 = 1000$
• fb()：$2^N = 1024$
• fc()：if文を無視すれば、$N^2$であり、$i=1,3,5,7,9$のときにそれぞれ$10$回加算されるので、$100+5\times 10=150$
• fd()：$j$は$2,4,8,16$と変化していき、$16$になったときにwhileを抜ける。これを$N$回繰り返しているため、$4\times 10+10=50$

問3

以下のような完全二分木$T$を考える。(問題文省略)

1 2 3 4 5

3 / \ 4 6 / \ 7 5

(a)

• 根：3
• 節点6の親：3
• 節点4の兄弟：6
• 木の高さ：2
• 木の大きさ：5

(b)

• inoder：7->4->5->3->6
• (preorder：3->4->7->5->6)
• (postorder：7->5->4->6->3)

(c)

• 根のみからなる木$T$はヒープ木である。
• ヒープ木$T$の「$T$の根以外を、根とする部分木」はまたヒープ木である。
• ヒープ木$t$の根の数値は、その全ての「$T$の根以外を、根とする部分木」の根の数値よりも「小さい」。

(d)

1
2
3
4
5

    2
   / \
  4   3
 / \ /
7  5 6

(e)

$N\log N$回

(f)

節点は、その節点の持つ値、子の節点へのポインタが2つ、親へのポインタが1つ、計4つのデータを持つ。よって、16byte。

(g)

配列を用いて、$i$番目の要素の親は$\lfloor i/2 \rfloor$番目の要素、左の子は$2i$番目の要素、右の子は$2i+1$番目の要素と表現することで、4byteで済む。

問4

$N=10^9$個の数からなる一次元配列が与えられる。その中から、$p$個の数をその値の小さいものから順に取り出すとき、どのようなアルゴリズムを用いると、最も効率よく$p$個の数を取り出すことができるか。
(a)$p=1$のとき (b)$p=10^8$のとき

(a)

配列をAとする。m=A[0]とおき、for文でAを走査し、mより小さい値があればmをその値に置き換える。これをAの最後まで繰り返す。このとき、mにはAの最小値が格納されている。計算量は$O(N)$。

(b)

昇順にソート(マージソートやヒープソートなどの最悪計算量が$O(N\log N)$のソート)を行い、Aの最初の$p$個の要素を取り出す。計算量は$O(N\log N)$。 (a)のように、最小値を求める方法を用いると、計算量は$O(Np)$とり、$\log N < p$であるから、前者の方が効率的である。

情報数学

問1

集合$A$上の二項関係$R$を直積集合$A\times A$の部分集合として定義する。また、$x,y\in A$に対して、$(x,y)\in R$であるとき$xRy$と表記する。いま、自然数全体の集合を$A=\mathbb{N}$とし、次の$\mathbb{N}$上の二項関係$D={(x,y)|x,y\in \mathbb{N},xはyの約数}$を考える。

(a) $xDy$を満たす$(x,y)$の組を具体的に3つあげなさい。

• $(1,1),(1,2),(1,3)$

(b) 順序$R$とは、$A$の任意の要素$x,y,z$に対して反射律、推移律、反対称律を満たす二項関係のことである。$D$が順序であることを示しなさい。

• 反射律：明らかに$x$は$x$の約数であるから、$xDx$である。
• 推移律：$xDy$かつ$yDz$であるとき、整数$a,b$を用いて$ax=y,by=z$と表せる。このとき、$abx=z$であるから、$x$は$z$の約数である。よって、$xDz$である。
• 反対称律：$xDy$かつ$yDx$であるとき、整数$a,b$を用いて$ax=y,by=x$と表せる。このとき、$abx=x$であるから、$ab=1$である。よって、$x=y$である。

集合$A$と$A$上の順序$\preceq$ の対を順序集合と呼び、$\left<A,\preceq\right>$と表記する。$A$のある要素$a$と、$A$の任意の要素$x,y,z$に対して、以下の条件が成り立つとき、$x$を$a$の直後の要素という。
(1) $a\preceq x$
(2) $a\prec z \preceq x$ならば$z=x$
ただし、$x \preceq y$かつ$x\ne y$であるとき$x\prec y$と表記する。 順序集合$\left<N,D\right>$では、任意の$k\in \mathbb{N}$に対して、$k$の直後の要素が無限に存在することが知られている。$k$の値を具体的に定め、その直後の要素の例を$3$つあげなさい。

$k=1$のとき、$2,3,5$は$k$の直後の要素である。

問2

包除原理を使えば良い。英語、中国語、ドイツ語をそれぞれ履修している人の集合を$A,B,C$とする。

$$ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C| $$ わかっている情報を代入すると、

$$ |A\cup B\cup C|=50+35+25-15-15-10+|A\cap B\cap C| = 70+|A\cap B\cap C| $$

どれも履修していない人数が$5$人だから、$|A\cup B\cup C|=75$である。よって、$|A\cap B\cap C|=5$である。

あとは、適当に足し算引き算していけば良い。

• 英語のみ：$30$
• 中国語のみ：$10$
• ドイツ語のみ：$5$
• 中国語とドイツ語を両方登録しているが、英語は登録していない：$10$
• 全部登録している人：$5$

問3

(a) $B_4$

(b)図のようになる。

• $B_1$：$8$
• $B_2$：$12$
• $B_3$：$12$
• $B_4$：$18$

(c) $B_6$

(d) 区切られたグリットを挟んだところに最も近い基地局があると、この探索方法だとその基地局が選ばれないことがある。

平成26年度

プログラミング

問1

選択ソートのプログラムの穴埋め

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void selectSort(void){
    int i,j,min;
    for(i=0;i<N-1;i++){
        min=i;
        for(j=i+1;j<N;j++){
            if( data[min] > data[j] ){
                min=j;
            }
        }
        swap(i,min);
    }
}

void swap(int x,int y){
    int tmp;
    tmp=data[x];
    data[x]=data[y];
    data[y]=tmp;
}

(b)計算量を求めなさい。

$O(N^2)$

(c) N=8,data[N]={5,8,7,3,6,1,4,2}であった場合を考える。プログラムの実行時、変数iの値がインクリメントされ、i=2となった直後のdataの値を求めなさい。

• i=0のとき：{1,8,7,3,6,5,4,2}
• i=1のとき：{1,2,7,3,6,5,4,8}
• i=2のとき：{1,2,3,7,6,5,4,8}

問2

異なる$n$個の候補から$r$個を選択する組み合わせの総数を求める、次の条件を満たす関数を作成しなさい。

• $n,r$を引数とする。
• 再帰呼び出しを用いる。
• $n,r$の大小関係に関するエラー処理はしなくてよい。

また、次の性質を利用して良い

• $_n\mathrm{C}_0 = _n\mathrm{C}_n = 1$
• $_n\mathrm{C}_r = _{n-1}\mathrm{C}_{r-1} + _{n-1}\mathrm{C}_r$

1
2
3
4
5
6
7

int combination(int n,int r){
    if(r==0 || r==n){
        return 1;
    }else{
        return combination(n-1,r-1)+combination(n-1,r);
    }
}

問3

関数の引数における値渡しと参照渡しの違いを説明しなさい。

値渡しは、関数に渡す引数の値をコピーして渡す方法である。関数内で引数の値を変更しても、呼び出し元の変数の値は変わらない。参照渡しは、関数内で引数の値を変更すると、呼び出し元の変数の値も変わる。参照渡しは、値渡しに対して、メモリの使用量が少ない。

問4

情報数学

問1

（a) $aRb$ならば、$Ca=Cb$であることを示しなさい。

$aRb$より、$Ca={a,b,x_1,x_2,\cdots,x_n}$と表すことができる。対称律の定義より、$Cb={b,a,x_1,x_2,\cdots,x_n}$である。よって、$Ca=Cb$である。

(b) $aRb$でなければ、$Ca \cap Cb = \emptyset$であることを示しなさい。

背理法で示す。$Ca$と$Cb$に共通の要素$x$があったとする。$aRx$と$bRx$の関係が成り立つので、推移律より$aRb$が成り立つ。これは$aRb$でないことに矛盾する。よって、$aRb$ではないとき、$Ca \cap Cb = \emptyset$である。

(c) $2$つの整数$a,b$に対して、$a-b$が$3$の倍数であるとき、$a=_3b$とする。このとき、関係$=_3$は同値関係であることを示しなさい。

• 反射律：$a-a=0$は$3$の倍数であるので、$a=_3a$である。
• 対称律：$a-b=3k$ならば、$b-a=-3k$である。$-3k$は$3$の倍数なので、$b=_3a$である。
• 推移律：$a-b=3k$かつ$b-c=3l$ならば、$a-c=a-b+b-c=3k+3l=3(k+l)$である。$k+l$は整数なので、$a-c$は$3$の倍数である。よって、$a=_3c$である。
• 以上より、$=_3$は同値関係である。

問2

二分木の木の高さは以下のように定義できる。

• 空の二分木の高さは$0$である。
• ノードが1つ以上ある二分木には根ノードがあり、その高さは以下で定義する。$\max(根ノードの左につながる部分木の高さ, 根ノードの右につながる部分木の高さ)+1$
  さらに、全てのノードをみて、左右のノードにつながる部分木の高さの差が$1$以下である二分木を「近似的平衡二分木」と定義する。

(a) 高さが3の近似的平衡二分木に含まれるノード数の最小値を答えなさい。さらに、高さが4の場合についても同様に答えなさい。

高さが3の場合、ノード数の最小値は$4$である。

1
2
3
4
5

    o
   / \
  o   o
 / 
o 

高さが4の場合、ノード数の最小値は$7$である。

1
2
3
4
5
6
7

    o
   / \
  o   o
 / \   \
o   o   o
 \
  o

(b)高さ$h$の木について、ノード数の最小値を$a_n$とする。漸化式で$a_n$を示しなさい。ただし、$a_0=0,a_1=1$とする。

$n\geq 2$のとき、$a_n=a_{n-1}+n-1$

$18$個ののーどが含まれる近似平衡二分木の高さの最大値を答え、その理由を説明しなさい。

$a_n \leq 18$を満たす最大の$n$を求める。$a$を列挙すると、$a_1=1,a_2=2,a_3=4,a_4=7,a_5=11,a_6=16,a_7=22$であるので、高さは$6$である。

問3

(a)

故障率を$p$と置く。

$$ p^4 + 4\cdot p^3(1-p) + 2\cdot p^2(1-p)^2 = p^2(-p^2+2) = 0.00019999 = 2 \times 10^{-4} $$

(b)

$$ 1 - ((1-p)^4 + 4\cdot p(1-p)^3 + 2\cdot p^2(1-p)^2) = p^2(p-2)^2 = 0.00039601 = 4 \times 10^{-4} $$