HOME»応用情報技術者試験掲示板»H.30秋  問3プログラミングについて
投稿する

H.30秋  問3プログラミングについて [5458]

 ええいああさん(No.1) 
設問4「コ」にはいる空欄をN(log2(σ)+1)だと思って解答したら、答えがNlog2(σ)でした。
納得いかなく、答えが間違っていて、N(log2(σ)+1)が本当の正解ではないかと思っています。

誰か教えてください。
2024.10.09 17:14
jjon-comさん(No.2) 
AP プラチナマイスター
応用情報 平成30年 秋期 午後 問3
https://www.ap-siken.com/kakomon/30_aki/pm03.html

いいえ,N×log2(σ)が正しいです。

次のスレッドの plさんの発言 No.6 を参照。
https://www.ap-siken.com/bbs/1621.html

> オーダ(なんとオーダーOrderのこと)では、1回も100回も同じことです。
> 1万回でも1億回でも、それが整数値で無限でなければ
> コンピュータにとって些細な事だからです。

> n回比較する作業を、何回すれば良いでしょうか。
> n-1回なので、それはn回に等しいです。
> n回の比較をn回繰り返すから、n^2。これがオーダになります。

> ちなみにn^2+nの場合、n^2以外の項は無視されます。
> これはn^2にとってnが些細過ぎる数だからです。
2024.10.09 18:08
こはさん(No.3) 
この投稿は投稿者により削除されました。(2024.10.09 18:36)
2024.10.09 18:36
こはさん(No.4) 
聞かれているのがウェーブレット木だからです。

問題文の図1左側のビット数の総和を求める必要があります。

つまり、σ=4だと深さが1で終わります。

だから、σ=4、N=10だと図1の左の通りになりビットの総和は20。

これを一般化すると解答の通りとなります。
2024.10.09 18:35
こはさん(No.5) 
私の勝手な推測ですが、ええいああさんは求めるべきビット数は、「1・0を全て振り分け切った」つまり「図1のウェーブレット木の更に1つ深いところまでの総和を求める必要がある」と思い、解答の式にしたのかなと思います。

私も引っかかりました。難しいですね。
2024.10.09 18:52
 ええいああさん(No.6) 
こはさん、おっしゃる通りです。
ビットを全て振り分け切ったもので解答してしまいました(図1の右のように)。

そこで、気になってしまったのですが、ウェーブレット木とは、図1を例にすると図1左の形が完成形ということでしょうか。

問題文を見てみるとウェーブレット木の構築(3)では、文字列が1種類になるまで分解しているのですが、これはあくまで文字列に対する操作であってウェーブレット木での操作ではないという理解で合ってますか。

ご返信お待ちしております。
2024.10.09 21:11
こはさん(No.7) 
> そこで、気になってしまったのですが、ウェーブレット木とは、図1を例にすると図1左の形が完成形ということでしょうか。

そうなんだと思います。

根拠としては、ウェーブレット木構築手順の(3)にある記述です。
------------------------------------------------------------------------
  ビットの値が0の場合に取り出した文字列内の文字が2種類以上の場合は,その文字列に対応する新たなノードを生成して,左の子ノードとする。取り出した文字列内の文字が1種類の場合は,新たなノードは生成しない。
  ビットの値が1の場合に取り出した文字列内の文字が2種類以上の場合は,その文字列に対応する新たなノードを生成して,右の子ノードとする。取り出した文字列内の文字が1種類の場合は,新たなノードは生成しない。
------------------------------------------------------------------------

文字列"CTCGAGAGTA"を考えると、図1のウェーブレット木の深さ1の左のノードの場合、「11000」の1番目の「1」と2番目の「1」はともに「C」になります。
先程の文章を読む限り、「取り出した文字列内の文字が1種類の場合は,新たなノードは生成しない。」ということですので、深さ1から更に深いノードは生成されないということになります。

ですので、完成形という認識で問題ないのかと思います。

うまく説明できてるかわかりませんが、気になる点がありましたらご指摘ください。
2024.10.09 21:54
こはさん(No.8) 
> 問題文を見てみるとウェーブレット木の構築(3)では、文字列が1種類になるまで分解しているのですが、これはあくまで文字列に対する操作であってウェーブレット木での操作ではないという理解で合ってますか。

図1の文字列の振り分けでは、最終的には「各文字列が1種類ずつ」になるように振り分けられています。
この図1の直前の記述
「また,図1の文字列の振り分けは,ウェーブレット木によって文字列Pが振り分けられる様子を示している。」

上記の内容から、図1にある文字列の振り分けは「あくまで文字列に対する操作であってウェーブレット木での操作ではない」という理解で良いと私も思います。

気になる点があればご指摘いただけると幸いです。
2024.10.09 22:17
jjon-comさん(No.9) 
AP プラチナマイスター
No.4~No.8 の論点がズレているので再度発言します。

問題文を見なくても,アルゴリズムが何だろうと,
N×(log2(σ)+1)
の +1 を書いている時点で,計算量(オーダ)の解答として不正解です。理由はNo.2で述べました。

計算量(オーダ)という概念を知らないのなら,ネット検索すれば解説がいくつもみつかるでしょう。
2024.10.09 22:42
こはさん(No.10) 
空欄「コ」で聞かれていることは「キー値のビット列の長さの総和」ですので、論点はずれていないかと思います。

計算量を求める問題(今回の問題だと空欄「ケ」、「コ」)であれば、オーダー記法に則り、端数は除いた表記にはなります。

いかがでしょうか。
2024.10.09 22:53
jjon-comさん(No.11) 
AP プラチナマイスター
ごめんなさい,オーダに関する問いは ケとク で終わっており,コ は違うのですね。
No.2とNo.9は読み捨ててください,たいへん失礼いたしました。
2024.10.09 23:02
 ええいああさん(No.12) 
jjon-comさんの、計算量に関するお話も、再確認する良いきっかけになりました。No.2の時スルーしてしまいごめんなさい。

こはさん、理解できたと思います。本当にありがとうございました。おそらく今回の試験にウェーブレット木はでることはないと思うのですが、問3は本番でも解こうと思っているので、自分が思い込んだ解き方でなく、問題文をしっかり読んで解こうと思います。

お二方、大変ありがとうございました。
夜分に失礼しました。

日曜日頑張ってきます!
2024.10.09 23:33
返信投稿用フォーム
お名前
顔アイコン

本文(コミュニティガイドライン⇱を順守して適切な投稿を心がけましょう)
🔐投稿削除用のパスワード
投稿プレビュー
※SQL文は全角文字で記載してください。
※宣伝や迷惑行為を防止するため、当サイト、姉妹サイト、IPAサイト以外のURLを含む文章の投稿はできません。
投稿記事削除用フォーム
投稿No. パスワード 
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop