Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

数学ガール/ポアンカレ予想

本書を読み終えた今、「ポアンカレ予想」が理解できたか?と問われたら、間違いなくNoだと思います。 p225やp340に、

* ポアンカレ予想
Mを3次元の閉多様体とする。
Mの基本群が単位群に同型ならば、Mは3次元球面に同相である。

とありますが、この予想すら理解するのは、正直なところ難しいです。

こんな難しいことを扱っている本書ですが、楽しめたか?と問われたら、自信を持ってYesと答えたいと思います。

ポアンカレ予想を理解するという大きな流れには乗れなかったのかもしれませんが、本書を通して、その支流にある今まで高校や大学などで学んだ微分方程式三角関数テイラー展開フーリエ展開などについての理解を、楽しみながら深めることができたのは有意義な経験でした。

特に印象に残ったのは第9章で、「テトラが言葉を失って椅子から立ち上がるような事実」への導きがとても良かったですね。自分でもノートに数式を書いていくというのも楽しみの一つでした。p326を読みながら新たに問題を設定して解いてみたのですが、実際に手を動かしてみると理解が深まるような気がします。

f:id:rahaema:20180520153751p:plain

また、シリーズ6巻目と言うことで、とうとう主人公のが受験を目前に控えた受験生に成長しています(我が子もそうですが、子供の成長は早い!)。特に受験を控えている高校3年生の受験生の方々にとっては物語を追うことで、と一緒に受験勉強に取り組み、そして乗り越えていくような体験をすることができるのでないでしょうか。サザエさんちびまる子ちゃんのように登場人物が歳をとらない物語とは違った良さがありますね。

平成30年度春季応用情報午後問3

平成30年度春季 応用情報技術者試験(AP)の午後問題3は、再帰による深さ優先探索を用いたナイトの巡回問題でした。

IPA 独立行政法人 情報処理推進機構:問題冊子・配点割合・解答例・採点講評(2018、平成30年)」のページでまだ解答が示されていませんので、自分なりの解答を載せておきます。

設問1
ア:2 イ:-2
設問2
ウ:iがM・N エ:i+1 オ:v+d[j] カ:h+dh[j] キ:board[v][h] ← 0
設問3

(1)

20行目:vを3からm+2まで1ずつ増やす
21行目:hを3からn+2まで1ずつ増やす

(2)

32行目:search(1, 3, 3)

(3)

2,3,16,17行目

設問1,2(h30h_ap_pm3_1.c)

設問1,2の実行結果

$ gcc h30h_ap_pm3_1.c && ./a.out
  1  8  3
  4 11  6
  7  2  9
 10  5 12

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

設問3(h30h_ap_pm3_2.c)

平成30年度春季基本情報午後問12

平成30年度春季 基本情報技術者試験(FE)の午後問題12(アセンブラ言語CASL)は、

  • 数字 → 数値変換(プログラム1)
  • 文字列から数字を探索し管理テーブルに格納する(プログラム2)
  • 2つの整数の積を求める(プログラム3)

についての問題でした。

基本情報技術者試験の午後問題では、C, COBOL, Java, CASL, 表計算の問題の中から1問選択して解答することになりますが、CASLを選択するという戦略は結構いいのではと思います。今回もあまり難しくない問題だったのではないでしょうか。

いつもは紙上で解いて終わりだったのですが、以下のシミュレータで実行してみました。CASLは不慣れですので、書き方などアドバイスをいただければ助かります。

プログラム1(h30h_fe_pm12_1.casl)

設問1の実行結果

問題文中の図1の例で試してみましたが、GR0に567が格納されています。

f:id:rahaema:20180503152352p:plain

プログラム2(h30h_fe_pm12_2.casl)

設問2の実行結果

問題文中の図2の例で試してみましたが、図3のように管理デーブル(0x001C番地)に数値を切り出すことができました。

f:id:rahaema:20180503152555p:plain

プログラム3(h30h_fe_pm12_3.casl)

設問3の実行結果

24行目で以下のようにデータを設定して試してみました。

DATA    DC      '25 10.' 

実行結果を見ると、GR0に250が格納されています。

f:id:rahaema:20180503153127p:plain

平成30年度春季基本情報午後問9

平成30年度春季 基本情報技術者試験(FE)の午後問題9(C言語)は簡易集計プログラムに関する問題でした。ファイルを扱うときは、Rubyなどのスクリプト言語を用いてきたのですが、久しぶりにC言語でファイル処理を行ってみました。

プログラム1(h30h_fe_pm9_1.c)

設問1の実行結果

$ gcc h30h_fe_pm9_1.c -o prog1 -DQ1
$ ./prog1 fig1.psv fig2.tsv && cat fig2.tsv
    FE-111         2       200
    FE-222         1       400
    FE-333         3       900
    FE-444         2      1200

プログラム2(h30h_fe_pm9_2.c)

設問2の実行結果

$ gcc h30h_fe_pm9_1.c -o prog1 -DQ2
$ ./prog1 fig3.psv fig4.tsv && cat fig4.tsv
$ gcc h30h_fe_pm9_2.c -o prog2
$ ./prog2  fig4.tsv
        11         1       100 |**
        12         2       800 |******************
        13         2      1100 |*************************
        15         3       700 |***************

使用したデータファイル

fig1.psv

20180410|112610|FE-111|0001|000100
20180410|154358|FE-111|0001|000100
20180410|123820|FE-222|0002|000400
20180410|153249|FE-333|0001|000300
20180410|135044|FE-333|0001|000300
20180410|152859|FE-333|0001|000300
20180410|131923|FE-444|0002|000800
20180410|123907|FE-444|0001|000400

fig3.psv

20180410|11|2610|FE-111|0001|000100
20180410|12|3820|FE-222|0002|000400
20180410|12|3907|FE-444|0001|000400
20180410|13|1923|FE-444|0002|000800
20180410|13|5044|FE-333|0001|000300
20180410|15|2859|FE-333|0001|000300
20180410|15|3249|FE-333|0001|000300
20180410|15|4358|FE-111|0001|000100

平成30年度春季基本情報午後問8

平成30年度春季 基本情報技術者試験(FE)の午後問題8はヒープソートについての問題でした。まさに基本という名にふさわしい題材だと思います。

疑似言語で書かれた問題をC言語にして実行してみました。

h30h_fe_pm8.c

実行結果

$ gcc h30h_fe_pm8.c && ./a.out
Before:  15  5 30 60 45 20 10
After :   5 10 15 20 30 45 60

バブルソートとの速度比較

これだけで終わっては面白くないので、効率の悪いことで有名な O(n^2)アルゴリズムであるバブルソートと速度比較を行ってみました。

次のようにプログラムを変更。

#include <time.h>
#include <stdlib.h>

void bubbleSort(int data[], int num);

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

int main(void)
{
  int hnum = 100000;
  int data[hnum], heap[hnum];
  clock_t c1, c2;

  srand((unsigned)time(NULL));
  for (int i = 0; i < hnum; i++) {
    data[i] = rand();
  }

  c1 = clock();
  heapSort(data, heap, hnum);
  c2 = clock();
  printf("Heap Sort   = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);

  c1 = clock();
  bubbleSort(data, hnum);
  c2 = clock();
  printf("Bubble Sort = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);
  return 0;
}

実行結果

要素の数を100000個でやってみたのが以下です。

$ gcc h30h_fe_pm8.c && ./a.out
Heap Sort   = 0.044185[s]
Bubble Sort = 40.557902[s]

ヒープソートO(n \log n)アルゴリズムですが、O(n \log n)O(n^2)アルゴリズムではこんなにも性能が違ってくるんですね。アルゴリズムを学ぶことがいかに大切かということが実感できる結果となりました。

プロを目指す人のためのRuby入門

今までRubyのプログラムを書くといっても、仕事での事務作業の効率アップのために簡単なRubyスクリプトを書くということがメインで、自分でクラスやモジュールを定義して、大規模なプログラムを作る機会がなかったので、どうしてもクラスやモジュールについての理解が進まないのですが、本書の特に

  • 第7章 クラスの作成を理解する
  • 第8章 モジュールを理解する
  • 第10章 yieldとProcを理解する

はとても分かりやすく書かれているなと思いました。RubyRubyそのものが面白いので、ソフトウェア開発に携わることがなくても学び続けて行きたいですね。

以下は、読み返すとき用のメモです。

  • p125 4.8.2 with_indexメソッドを使った添え字付きの繰り返し処理
  • p167 5.6.8 ハッシュの初期値を理解する

今まで、ハッシュを初期化するために以下のようなコードを書いてきましたが、その意味を理解することができました。

h = Hash.new { |hash, key| hash[key] = 'hello' }
  • p173 Column 条件分岐で変数に代入 / &.演算子
a&.upcase
  • p175 Column !!を使った真偽値の全変換
!!find_user
  • p187 6.3.3 キャプチャの結果に名前をつける
  • p188 6.3.4 正規表現と組み合わせると便利なStringクラスのメソッド
  • p310 8.7.2 module_functionメソッド
  • p314 Column Singletonモジュールを使う
  • p319 8.9.3 prependでモジュールをミックスインする
  • p320 8.9.4 prependで既存メソッドを置き換える
  • p389 10.5.2 &とto_procメソッド
  • p422 12.7 Rake
  • p427 12.8.2 Bundlerでgemの依存関係を管理する

西郷どん!

郷土(といっても隣県)の偉人ですが、恥ずかしながら明治維新で活躍した人くらいの認識しかありませんでした。大河ドラマでも話題ですね。どう映像化されていくのか見る楽しみが倍増しそうです。

巻末に参考文献のリストがありますが、本書を執筆するにあたり膨大な資料に目を通されていることにびっくりしました。これだけの下準備をしないと作品は生まれてこないんですね。この姿勢をぜひ見習っていきたいと思います。