Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

平成27年度秋季基本情報午後問9

情報処理技術者試験 C

平成27年度秋季 基本情報技術者試験(FE)の午後問題9は、

に関する問題でした。

f:id:rahaema:20190223222929p:plain

プログラム例(h27a_fe_pm9.c)

Access.Log

S0012015101809000011IASys Op Lib
S0012015101809100421IASys Op Lib
S0012015101809200831IASys Op Lib
S0012015101809301231OASys Op Lib
S0012015101809401621OASys Op Lib
S0012015101809502011OASys Op Lib
V0012015101811004812IAVisitor 01
V0012015101811105222IRVisitor 01
V0012015101811205612OAVisitor 01

実行結果

設問1の実行結果が以下です。設問2については上記のプログラムを利用して取り組んでみてはいかがでしょうか。

$ gcc h27a_fe_pm9.c && ./a.out

S001  Sys Op Lib  10-18 09:00 11 IN
                                      10-18 09:10 21 IN
                                                          10-18 09:20 31 IN
                                                          10-18 09:30 31 OUT
                                      10-18 09:40 21 OUT
                  10-18 09:50 11 OUT

V001  Visitor 01  10-18 11:00 12 IN
                                      10-18 11:10 22 (R)IN
                  10-18 11:20 12 OUT

平成27年度秋季基本情報午後問8

情報処理技術者試験 C

平成27年度秋季 基本情報技術者試験(FE)の午後問題8は、

  • Boyer-Moore-Horspool法(BM法)を用いて、文字列検索を行うプログラム

に関する問題でした。

f:id:rahaema:20190221190035p:plain

プログラム例(h27a_fe_pm8.c)

実行結果

本問で紹介されているボイヤー-ムーア文字列検索アルゴリズム(bmmatch関数)がどれ位高速に動作するのか、効率の悪い方法(naivematch関数)と比較してみました。

検索文字列の長さを8000000文字とし、その末尾に検索文字列("THISISAPEN")を連結して、検索文字列の最後でマッチするようにし、実行した結果が以下です。上段がBM法、下段が効率の悪いアルゴリズムの結果です。

今回の実験では、BM法が約3倍高速に動作していることが分かりました。検索文字列を長くするなど、条件を変えるともっと性能差が現れるような気がします。

$ gcc h27a_fe_pm8.c && ./a.out
7999989 0.010095[s]
7999989 0.028534[s]
$ ./a.out
7999989 0.010078[s]
7999989 0.028884[s]
$ ./a.out
7999989 0.010046[s]
7999989 0.028848[s]

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

情報処理技術者試験 C

平成27年度春季 基本情報技術者試験(FE)の午後問題8は、

に関する問題でした。

f:id:rahaema:20190216193126p:plain

プログラム例(h27h_fe_pm8.c)

実行結果

本問で紹介されているクイックソートを応用したアルゴリズム(select関数)がどれ位高速に動作するのか、効率の悪い方法(select_slow関数)と比較してみました。

配列の大きさを100000、3番目に小さい値を検索した結果が以下です。3回実行してみました。上段がクイックソートを応用したアルゴリズム、下段が効率の悪いアルゴリズムによる実行結果です。

$ gcc h27h_fe_pm8.c && ./a.out
34094   0.001247[s]
34094   21.022426[s]
$ ./a.out
83186   0.001020[s]
83186   22.713672[s]
$ ./a.out
77109   0.001389[s]
77109   23.093841[s]

クイックソートはO(n\log n)で動作するので効率が良いというのは、よく知られた事実ですが、O(n^{2})のアルゴリズムと比較してみると、その性能差をまざまざと実感することができますね。

平成26年度秋季基本情報午後問9

情報処理技術者試験 C

平成26年度秋季 基本情報技術者試験(FE)の午後問題9は、

  • C言語によるセキュリティ管理

に関する問題でした。

f:id:rahaema:20190214220241p:plain

プログラム例(h26a_fe_pm9.c)

実行結果

$ gcc h26a_fe_pm9.c && ./a.out

AE002    UserE2       特権S 付加   特権O 解除
AE003    UserE3       特権O 解除
AP004    UserP4       利用者ID 削除  特権O 解除
AP006    UserP6       利用者ID 追加  特権O 付加

使用したファイル

NewFile

AE001 UserE1 41 20140419
AE002 UserE2 48 20141014
AE003 UserE3 48 20140716
AP005 UserP5 46 20141015
AP006 UserP6 44 00000000

OldFile

AE001 UserE1 40 20140419
AE002 UserE2 44 20140712
AE003 UserE3 4C 20140716
AP004 UserP4 45 20140715
AP005 UserP5 44 20140713

情報処理技術者試験の過去問を実際に動かしてみよう!

情報処理技術者試験

最近、情報処理技術者試験(応用情報・基本情報)の午後問題で出題されるアルゴリズムやプログラミングに関する問題を実際に動かしてみるという試みを続けているのですが、はてなブログに書くだけでは、今までにどんな分野が出題されてきたのかなど、全体を俯瞰しにくいという問題があるように思います。

そこで、今まで解いてみた問題を各回ごとに整理し、どんな内容だったのかをリストアップしたページを作成してみました。合格を目指して、勉強されている方の参考に少しでもなればいいなと思います。

f:id:rahaema:20190212215041p:plain

平成26年度秋季基本情報午後問8

情報処理技術者試験 C

平成26年度秋季 基本情報技術者試験(FE)の午後問題8は、

  • 2つの文字列間の編集距離(レーベンシュタイン距離)

に関する問題でした。

f:id:rahaema:20190209220923p:plain

プログラム例(h26a_fe_pm8.c)

実行結果

$ gcc h26a_fe_pm8.c && ./a.out
abcabba
cbabac
5
$ ./a.out
kitten
sitting
5
$ ./a.out
peace
people
5

関連

こちらでは、文字列kittenとsittingの編集距離の値が3となっていますが、置換を許しているためです。

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

情報処理技術者試験 C

平成26年度春季 基本情報技術者試験(FE)の午後問題9は、

  • 印字したときに単語が行末で切れないようにテキストを編集してファイルに出力するプログラムに関する

問題でした。

f:id:rahaema:20190203164100p:plain

プログラム例(h26h_fe_pm9.c)

設問1のプログラムを以下に示します。

実行結果

in.txt

The    Infomation   Technology   Engineers
   Examination   was  first  administered  in 1969. In 1970,
 it became a national examination.
       Since its commencement, the examination has played
    an important role   in the development of IT    engineers.

実行

$ gcc h26h_fe_pm9.c && ./a.out in.txt out.txt
$ cat out.txt
The    Infomation   Technology   Engineers
   Examination   was  first  administered  in
1969. In 1970,
 it became a national examination.
       Since its commencement, the examination has
 played
    an important role   in the development of IT
  engineers.