3、4、8章だけ載せています。
4章 ネットワークとインターネット
1. プロトコルとは何か。この章で紹介した3つのプロトコルとそれぞれの目的を述べよ。
ネットワークが十分に機能するために、動作を決定する規則。
プロトコルその1:CSMA/CD(Carrier Sense, Multiple Access with Collision Detection)
目的:イーサネット標準に基づいたバス型ネットワークにて送信されるメッセージを制御すること。
プロトコルその2:CSMA/CA(Carrier Sense, Multiple Access with Collision Avoid)
目的:(スター型)無線ネットワークにて送信されるメッセージを制御すること。
プロトコルその3:TCP(Transmission Control Protocol)
目的:高い信頼性でインターネットのトランスポート層を実装すること。
2. クライアントサーバモデルを説明せよ。
プロセス間通信で使われている方式の1つであり、プロセスが実行する基本的な役割を、他のプロセスに要求を出すクライアントと、クライアントからの要求に応えるサーバとして定義する。1つのサーバが多くのクライアントにサービスを提供するので、サーバは常に稼働していなければならない。ネットワークアプリケーションで広く利用されている。
3. P2Pモデルを説明せよ。
お互いにサービスを提供・享受する一群のプロセスから構成される。通常は、一時的に実行されるプロセスから構成される。インターネットを通じてメッセージをやりとりするインターネットメッセンジャーなどが例。
4. 3種類の分散コンピューティングシステムを説明せよ。
クラスタコンピューティング
多くの独立したコンピュータが密接に結合して作業することで、大型コンピュータ並みの計算能力やサービスを提供する分散システム。小さい1台のコンピュータが故障しても全体は動き続くので、システムに高い可用性(継続稼働できる。壊れにくい、復旧が早いなど耐障害性に強い)が必要な時に用いる。また、作業量が集中したコンピュータから空いているコンピュータに作業を自動的に移せるので、負荷分散システムでもある。
グリッドコンピューティング
クラスタほど密接に結合せずに緩く結びついたマシンが大規模な作業を行う。グリッドに参加するマシンはデータとアルゴリズムを分散させるのを簡単にするソフトウェアを含むことがある。例えば家庭にあるPCでも、使わない時間だけでもグリッドに参加できる。極めて複雑な数学の問題を解くことも可能になってきている。
クラウドコンピューティング
ネットワーク上で共有される膨大な数のコンピュータをユーザの要望に応じて割り当てる分散システム。ここでいう「クラウド」とは、ネットワーク上で利用可能な莫大な計算資源のこと。
5. 開放型ネットワークと閉鎖型ネットワークの違いは何か。
開放型はプロトコルが完全に公開されており、無料で使用できるが、閉鎖型は例えば企業が開発したらその企業が知的財産権が発生し、企業はその閉鎖型ネットワークを貸すことで利益を得る。
6. なぜCSMA/CDプロトコルは、無線ネットワークに適用できないのか。
マシンが自分の送信と他のマシンの送信が衝突しても検知でないから。例えば、他のマシンの信号を受信したくても、自分自身の信号の送信がそれを打ち消してしまう場合もある。
また、他の理由として、マシンはセントラルAPと通信できるが、マシンからマシンへの信号は障害物などが原因で妨害されることがあるから。
7. CSMA/CDプロトコルを用いてネットワークにメッセージを送信しようとするマシンが行うことを、ステップに分けて説明せよ。
・バスが静かになるのを待つ
・バスを監視しながら、メッセージがバスにないところを見計らって送信を開始する
・他のマシンが同時に開始してしまったら、どちらのマシンも衝突を検知してそれぞれランダムな時間休止して再度送信を試みる
8. 隠れ端末問題とは何か。それを解決するための技法を述べよ。
無線通信する際に、建物などによってマシン間の交信が妨害されること。
解決する技法として、マシン間の通信の衝突を検出するのではなく回避するようなプロトコルを使う。
9. ハブとリピータでは、何が違うのか。????
ハブはバス型ネットワークを連結する装置で、極めて短いバスであり、ネットワークはハブをセントラルとするスター型のように見えるが、実際はバスネットワークである。
リピータはネットワークを繋ぐ装置の中で最も単純な装置で、2つのバス間で相互の信号を渡す。バス型ネットワークを連結する場合、単にバスを連結するだけである。
10. ルータはリピータ、ブリッジ、スイッチと何が違うのか。
ルータは違う性質のネットワークも繋いでインターネットを構成する。
後者は同じ性質のネットワーク同士を繋いで大きなネットワークを構成する。
11. ネットワークとインターネットでは、何が異なるのか。
ネットワークはコンピュータを連結することによって構成されるシステム。
インターネットはネットワークを連結した集合。
12. メッセージをネットワークに送信する権利を制御する、2つのプロトコルを述べよ。
CSMA/CDプロトコルとCSMA/CAプロトコル。
13. 32ビットのインターネットアドレスの使用は、当初は十分な拡張余地があると考えられたが、その予想は正確ではなかった。IPv6は128ビットのアドレッシングを使用する。128ビットは適切だろうか。解答の根拠を示せ(例えば可能なアドレスの総数と世界の人口を比較せよ)。
2^32 = 約43億で、世界人口はそれの倍近い。先進国以外でも一人1個端末を持ち始めており、先進国では一人複数の端末を持つ人も珍しくない現状だ。
2^128 は約43億×約43億×約43億×約43億なので、世界人口が1億倍になって一人が1億個端末を所持してもまだ半分以上余りがあるので、おそらく大丈夫だろうと予想できる。
14. ドット数値記法によって表されるビットパターンを記せ。
a. 000001010001001000100011
00000101=5
00010010=18
00100011=35
なので
5.18.35
b. 1000000000100000
10000000=128
00100000=32
128.32
c. 0011000000011000
00110000=48
00011000=24
48.24
15. 次のドット数値記法によって表されるビットパターンを記せ。
a. 0.0
0000000000000000
b. 26.19.1
00011010 00010011 00000001
c. 8.12.20.13
00001000 00001100 00010100 00001101
16. インターネットのエンドシステムのアドレスが154.148.46.120とする。16進記法での32ビットアドレスは何か。
9A.94.2E.78
17. DNSルックアップとは何か。
DNSによってニーモニックアドレス(URL・ドメイン名)がIPアドレスに変換するプロセスのこと。
18. コンピュータのニーモニックインターネットアドレスが、batman.batcave.metropolis.govであるとすると、このマシンを含むドメインの構造はどのように推測できるか。
トップレベルドメインgov中のドメインmetropolis中のサブドメインbatcave中にコンピュータbatmanがあると推測できる。
19. 次の電子メールアドレスの構成要素を説明せよ。
文字列kermitで識別される個人を差出人または受取人として、ドメインanimals.com中のメールサーバに届けられる。
20. VoIPの文脈において、アナログ電話のアダプタと組み込み電話の違いは何か。
アナログ電話アダプタはアクセスISPが提供する電話サービスに接続できるようにする装置であるが、組み込み電話はそのような銅線によるアナログ回線をイーサネット上のVoIPに置き換えることによって費用を抑えようとするものだ。
21. メールサーバの役割は何か。
電子メールサービスを提供すること。具体的には、電子メールはまずユーザのメールサーバに送られ、メールは宛先のメールサーバに転送され、受取人がメールサーバにアクセスするまで蓄積しておくこと。
22. Nユニキャストとマルチキャストの違いは何か。
前者は配信側のサーバやその近くのコンピュータに重大な負荷がかかってしまうので、それを解決する案の1つが後者で、インターネットルータが配信の問題を担っており、クライアントが複数でもサーバは1つのメッセージを1つのアドレスで送信すればいい仕組みになっている。
(↓参考。違いを明示・ピックアップしているというより、それぞれの仕組みを書いているだけなので↑の回答の方が良さげ。
前者は単にサーバ側からリスナーにメッセージプログラムを遅ればいいが、
後者は1つのメッセージを複数のクライアントに向かって1つのアドレスで送信され、ルータがそのアドレスを見て、メッセージのコピーをリスナーに転送する。
そして、リスナーのその局の放送を聞きたい要求は近くのルータに送られ、ルータがその要求をサーバに送る)
23. 次の用語を定義せよ。
a. ネームサーバ
ニーモニックアドレスをIPアドレスに変換する時に参照するデータベース。
b. アクセスISP
ティア1とティア2にアクセスするための独立したネットワーク。イントラネットとも呼ばれる。
c. ゲートウェイ
あるネットワークがインターネットに連結される地点のこと。単にルータのことを指す場合もある。家庭用WiFiに関してゲートウェイといえばネットワークのAPとそのAPに接続されたルータの両方を合わせてゲートウェイと呼ぶ。
d. エンドシステム
個々のユーザがアクセスISPに接続するための装置。ホストとも呼ばれる。
24. 次の用語を定義せよ。
a. ハイパーテキスト
文章や画像などを含むだけでなく、複数の文章をハイパーリンクによって結合することもできる、テキストを超えた文章。インターネットアプリケーションはこの字ハイパーテキストの概念に基づいている。
b. HTML
ハイパーテキストドキュメントに含まれるタグという特殊記号は、ドキュメントをディスプレイスクリーン上にどのように表示し、画像などのマルチメディア資源がどのように加えられているかなどを記述する。そのタグの体系がHTMLである。
c. ブラウザ
ユーザがインターネット上のハイパーテキストにアクセスできるようにするソフトウェアパッケージはクライアント側とサーバ側で2つある。ブラウザはクライアントパッケージの方であり、ユーザのコンピュータ上にあり、ユーザがウェブを探索するためのUIを提供する。
25. 多くの一般インターネットユーザは、インターネットとwwwを混同している。それぞれの用語を正しく説明せよ。
インターネット:様々なネットワークを連結してできる、いわばネットワークのネットワーク。
www:インターネット上のハイパーテキストによるドキュメントには他のドキュメントに遷移するハイパーリンクがあり、関連する情報が組み合わさり網のようになったものをウェブと呼び、全世界を網羅するウェブをwwwと呼ぶ。
26. 単純なウェブドキュメントのソースバージョンを表示し、ドキュメントの基本構造を特定せよ。とりわけドキュメントのヘッダと本体部を特定し、それぞれで見つけた文を列挙せよ。
ソースバージョン
<!DOCTYPE html>
<html>
<head>
<meta charset=”utf-8″>
<title>**について</title>
</head>
<body>
<h1>題名です</h1>
<p>本文です</p>
</body>
</html>
<head>
<meta charset=”utf-8″>
<title>**について</title>
</head>
がヘッダである。
<body>
<h1>題名です</h1>
<p>本文です</p>
</body>
の部分が本体部。
表示される文章は以下の3文。
**について
題名です
本文です
27. HTMLタグを5個列挙せよ。それぞれの意味を説明せよ。
<html>:htmlのコードを書いていることを示している。
<h1>:大きな文字でタイトルを表記する。
<p>:passageの略で文章をこのタグ内に書くのに使う。
<a>:タグ内に遷移先のURLと紹介文を書いて、URL先に遷移するリンクとなる。
<body>:本文や画像などのメインのコンテンツはこのタグ内に収める。
28. “Rover”という単語が****というURLのドキュメントに連結されるように、次のHTMLドキュメントを変更せよ。
<html>
<head>
<title>example</title>
</head>
<body>
<h1>犬</h1>
<p>My dog’s name is Rover</p>
</body>
</html>
↓変更
<html>
<head>
<title>example</title>
</head>
<body>
<h1>犬</h1>
<p>My dog’s name is <a href=”****”>Rover</a>. </p>
</body>
</html>
29. 問題文略します。
タブの部分に”Example”と出て、
大きい文字で”My Pet Dog”と出て、
Rover.jpgの画像が表示される
30~33. 省略
34. 次のURLの構成要素を特定せよ。
http:プロトコルはhttpを使用
lifeforms.com:ドキュメントを保持するニーモニックアドレス。TLDがcomなので商用。
animals/moviestars:ホストのファイルシステムの中でドキュメントの場所を示すディレクトリパス
kermit.html:ドキュメント名
35. 略
36. 略(httpsはSSL暗号化して盗み聞きしても暗号化された状態で漏れるように通信する)
37. ウェブのクライアントサイドアクティビティとサーバサイドアクティビティの例を、それぞれ2つ挙げよ。
飛行機の予約ページを例に見ると
・フライトの日にちを入力(クライアントサイド)
・その情報がサーバに転送されて、その日のフライトが表示される(サーバサイド)
検索エンジンなら
・検索したいトピックを入力(クライアントサイド)
・その情報がサーチエンジンに転送され、関連していそうなドキュメントを特定したドキュメントを表示(サーバサイド)
38. OSI参照モデルとは何か。
(普及してないインターネットの構築モデルのやつ)
開放型システム間相互接続参照モデルの略。開放的なネットワークを構築するために、各製造会社が他社の装置やソフトウェアと互換性を保って動作するように、ISO(国際標準化機構)が規定した。7レベルの階層に基づいているが、4層の手法が先に普及したのでこちらは4層の手法に比べて普及していない。
39. パストポロジーに基づくネットワークでは、バスはマシンがメッセージを送るための競合する共有不能資源である。デットロックは、どのように制御されているか。
デッドロックが発生したらそれを検出して、強制的にメッセージの送信をやめさせる。
40. インターネットソフトウェア階層構造の4つの層を列挙せよ。各層によって実行される動作を述べよ。
・アプリケーション層
メッセージを準備して宛先アドレスを指定する
メッセージを受け取る
・トランスポート層
メッセージをパケットに分割する
パケットを集めてメッセージを再構成する
・ネットワーク層
各パケットに中継アドレスを割り当てる
パケットが最終目的地に到着したことを検知する
・リンク層
パケットを送信する
パケットを受け取る
41. なぜトランスポート層は、大きなメッセージをパケットに分割するのか
長いメッセージは、多くのメッセージが交差するインターネットルータにおいて、他のメッセージの流れを阻害するから。
42. アプリケーションがトランスポート層に、TCPを使用してメッセージ送信を依頼するとき、アプリケーション層の要求を実現するためにトランスポート層は、どのような追加メッセージを送るか。
メッセージを送信する前に、受信側のトランスポート層に、これからメッセージを送る旨のトランスポート層独自のメッセージを送信する。
43. トランスポート層を実装するため、TCPはUDPよりどのようにすぐれたプロトコルだと考えられるか。また、UDPはTCPよりどのようにすぐれているか。
・TCPの方が良い点
メッセージを送る前に受信側に送る旨を伝え、接続を確立してからメッセージを確実に送るので、信頼性が高い。
・UDPの方が良い点
メッセージを直接送るので効率が良い。
44. UDPがコネクションレスプロトコルであるとは、どういう意味か。
メッセージを送信する前に接続を確立することなく、与えたれたアドレスに単に送信するだけという意味。
??45. 次のそれぞれを用いて流入するトラフィックをフィルタリングする。TCP/IPプロトコルのどの階層にファイヤウォールを置くのが適当か。
a. メッセージ内容
b. 発信者アドレス
ネットワーク層
ゲートウェイ
c. アプリケーションの型
??46. 特定の用語や句を含むメールメッセージをフィルタリングするためにファイヤウォールを設置したい。このファイヤウォールは、ドメインのゲートウェイに設置するべきか、あるいはドメインのメールサーバに設置するべきか。
メールサーバ。
47. プロキシサーバとは何か。その利点は何か。
インターネットへの接続を監視する予防的なツールの1つであり、サーバの有害な行為からクライアントを守ること目的として、クライアントとサーバの間で仲介として機能するソフトウェアユニットである。
利点
サーバとクライアントを仲介することによって、実際のサーバは真のクライアントかどうかを見抜けなくなるので、サーバがクライアントから情報を盗めなくなる点。
他にも、サーバからクライアントに送られる全てのメッセージをプロキシサーバは検査できるので、既知のウイルスなら検知でき、感染を阻止できる。
48. 公開鍵暗号の原理を要約せよ。
・メッセージを公開鍵で暗号化する
・暗号化されたメッセージは公開鍵では解読できない
・メッセージを受け取った者は暗号鍵で暗号を解読できる
認証局が公開鍵と公開鍵の所有者の正確なリストを保持している。
49. 保護されていない遊休PCは、インターネットにとってどのように危険なのか
例えば、DoS攻撃の計算能力のソースとして悪用される場合がある。
50. インターネットのグローバルな性質がインターネット上の問題を法的に解決する時の制約になるとは、どのような意味か。
同じ行為でも国によって合法か違法かが異なる場合があるので、世界中で同様に利用できるインターネットの違法性を解決しにくくなる場合があるという意味。
3章アルゴリズム
手書きだったので、オープンソースのクラウドストレージとして使っているインスタにアップしました。
自作回答8章データ構造
1.
行優先ABCDEFGHIJKL
列AEIBFJCGKDHL
2.
39
3.
20
4. 伝統的な1次元配列で動的リスト実装したい。どう複雑?
セルの位置がずれる
データ構造が成長する際に必要なメモリ空間が必要になる。また、設計を誤ると、1つの項目の追加をするだけで、大規模な構造の再編成が起きたり、データ構造が成長しすぎてデータ構造全体を他のメモリ領域に移さなければならなくなったり。
5. 3次元配列の格納方法は?i番目の平面j行k列の要素を示すアドレス多項式
一番上の平面は2次元配列のように格納して、2番目の平面も続けて格納していけばいい。
x + (i-1)ab + (j-1)a +k-1
行、列の長さ(要素数)をそれぞれa,bとした
6.
Gを1つ右に移動、Fも、Eも
CとEの間にできた1マスにDを格納
7.
C
15
G
E
21
B
11
U
NULL
F
13
8.
J
38
B
36
X
46
G
30
K
40
P
34
9.
JANE
変更後
N
NULL
I
NULL
J
46
E
50
M
NULL
A
40
(nullにしなくても、jeanの邪魔にならなければ適当に繋げてもいい)
10. 連結リスト中のPreviousEntryの直後にちゃんと挿入できるのは
ルーチン1。
ルーチン2だと、NewEntryのポインタはNewEntryのアドレスを指すので、リストの後ろの方と繋がっていない。
11.
リストAの後ろにリストBを繋ぐとする。
Aの最後の要素のポインタフィールドの値をBの最初の要素のアドレスに変更
すれば良い
12.
連続リストA,Bとする。i,j=0
①A[i],B[j]の大小比較をして、小さい方を空リストCに入れる。ただし、A[i-1]がそのリストの最後の要素ならば(つまり、Aにはもう比較する要素がない場合)、B[j]を大きいと判断する。(A,Bが逆でも同様)
②A[?] = B[?] となるまで(同じ数字が出るまで)①を繰り返す
③同じ大きさの要素が出たら、Cにその数を二個追加して、i,jをどちらも1つ増やす。
A,Bの要素がなくなるまで①〜③を繰り返す。
連結リストでも同様にできる。
13.
先頭のポインタフィールドの値をnullにする。
先頭+(i+1)のセルのポインタフィールドの値を先頭+iのセルのアドレスに変更。
i=0,1,2,,,,n-2
14.
a.
先頭のセルのアドレスを示すポインタの値、先頭セルのポインタフィールドの値、先頭+1、、、、先頭+n-1(最後尾)
の順にスタックに保存していく。
つまり、取り出す際には、最後尾から先頭へのアドレスが出てくる。
スタックから1つpopし、そのアドレス(最後尾)のセルのポインタを、今さらにスタックをpopして出てくるアドレス(最後尾-1のアドレス)に向ける。(最後部のセルのポインタフィールドの値を、最後から2番目のセルのアドレスに変更する)
新しくpopで取り出した方のアドレスは保持し、そのアドレス(最後尾-1)のセルのポインタを、今さらにスタックをpopして出てくるアドレス(最後尾-2のアドレス)に向ける。
これを繰り返す
popしてスタックが空になった場合、その最後のアドレス(昔は先頭だったアドレス)のポインタフィールドの値をnullにする。
b.
少なくともこのやり方なら、スタックはアドレスを保持する形で関わっている。
i=スタックpop
Reverse{
j=スタックpop
アドレスiのポインタをアドレスjに向ける
i ← j
if スタックが空 then アドレスiのポインタをnullにして終了
else Reverse
}
**********再起を使わないなら***************
スタックにアドレス保存:
for 1~n
A[i]のアドレスをスタックへ
逆順に変更:
for(スタックが空でない)
{
変数dがemptyならスタックpopし、変数dに入れる(not emptyなら何もしない)
また新しくスタックpopし、変数cに入れる
アドレスdのセルのポインタを、アドレスcに向ける
d ← c
}
アドレスdのセルのポインタをnullにする
プログラム終了
15.
略
16.
A
- 文字Dをプッシュ
10 f
11 c
12 a
13 d
スタックが空になるまでpopし、最後にpopしたものを消す。
そして、残りをpushしていけば良い。
補助ストレージはスタックがいい。
(popせずにポインタずらすのは無理なん?)
配列A,Bにそれぞれスタックの要素をpopして入れる?
2つのスタックなら、別のスタックに逆順にして移動できる
3つのスタックなら、逆順でもそのままでも移動できる
(abcdefg->abcedfg ってこと?)
a~dまでをスタック2に移動
eをスタック3に移動
d,e,c,b,aの順にスタック1に移動
スタックに入っている名前を変更したり誤字を修正するには、修正したい要素に行くまでの操作が多いので計算量が増えてしまうが、名前へのポインタをスタックに格納するなら、スタックで格納する要素が減り、その問題が緩和されるから。
後ろに- 待ち行列にプレミアムパス実装
方法1
全部popして、優先したい要素をpushしてpopしたやつを戻す
方法2
別のキューを用意して、そのキューに要素があればその要素を優先してpopする。新しいキューが空なら元のキューの要素をpopできる
14~18
a.
guf–p(head)d(tail)r
b.
pを挿入したいセルにaが入っているので、(aが消えてpになる?)- ?
略、結構計算量多いよね?
略(どれレスの通りに木を書けばいい
略(アドレス繋げるだけ
ルートポインタが含むアドレスは42- 図8-21の再帰じゃない版
- 葉がアルファベット順に並ぶようにすればいい
- ztwp–r——hj
- 略(高さ3の完全二分木になる。
リストだけど木として実装:全社員の名簿
木だけどリストとして実装:パチンコ玉がどの穴に入るか
セルにポインタフィールドの値を3つ格納できるようにするといい。(例えば、1つ目が親、2つ目が左の子、3つ目が右の子、とすればよい)
兄弟間の移動をしたい時は、親に移動してから、違う方の子に移動すればいい。- チェス盤を表すデータ構造
黒、白、置かれてない、の3パターンを表現する。例えば、0,1,2。
それを2次元の配列に入れる。
(多分、for文とかで0が1に囲まれてるかを見ればいいかも)
左
スタックに要素をpushしていき、1つずつpopしてリストに格納すればいい。
2分木にはならないはず。(無理矢理できるかも)
左の親子関係は全て配偶者関係にする。4回結婚したら人の左の子には4個ノードがある。
右は文字通り親子関係にする。
図8-21 の
TargetValue = 根節点の値 の時、
その節点を削除し、
その節点の左に付いている部分木のノード数と右のそれを比較して少なくない方を選んで、
左だったなら、その左の子に移動し、そこから右の子があればずっと右に移動する。行き着いたノードを削除して開いたところに入れる。この作業で木が分離されたらその空いた箇所に対してこの操作をもう一度行う。
図8-20なら
Dを削除→左が多い→Bに移動→Cに移動→CをDがあった位置に挿入
特別なポインタフィールドを1つ用意する。
そのポインタは子も親も指しておらず、そのノードAの複製のようなものを指すことができる。
このポインタに刺されたノードBは実際の木の構造には変化を与えず、ノードBのポインタはノードAのポインタと見做される。
略(int ageみたいに書き並べたらいい
define type 名前 to be
{char names[100];
int namepointer = 0;
手続き1 名前変更{
}
手続き2 名前追加{
}
……- キューを表す抽象データ型
define type queue to be{
list = []
headpointer
tailpointer
}
インスタンス生成
queue q1,q2 ;
挿入の疑似こーど
tailpointer が指す位置に要素をpush
削除の疑似こーど
headpointer が指す位置の要素をpop
a. ユーザ定義のデータ型には演算が定義されておらず、プログラミング言語にデフォルトで用意されているものでなくユーザが定義したデータ型。一方、基本データはデフォルトで用意されており、演算も定義されている。
b. どちらもユーザによって定義されたものであるが、抽象データ型は演算まで定義されている。
データ構造:住民のマイナンバーと住所を含む構造体のリスト
手続き:構造体追加・削除、住所変更・削除・追加
データ構造:HP、攻撃力、残機、レベルなど
手続き:HP減らす()、攻撃力up、レベルup、残機1つ減らす- スタックをキューに
push
QueueEntries[tailP] = New;
pop
QueueE[–headP]
にすればいい?
継承をすることができたり手続きだけでも定義できる点において、より一般的といえる。
コメント