過去問について.
集合と位相:入手済(すぐにupします)
アルゴリズムとデータ構造:ttp://www-ui.is.s.u-tokyo.ac.jp/~takeo/course/
2004/algorithm/index.html
ハードウェア構成法:いらない?
形式言語理論:配布済
というわけで,他の科目の過去問を手に入れた方は是非教えてください.渡して
もらえればupします.
松本, Fri Jan 14 22:15:56 2005情報数学の過去問がJPEGだったので、テキストで打ち直してみました。
添付ファイル後藤, Mon Jan 17 15:49:49 2005GJ
名無しさん, Tue Jan 18 20:25:57 2005太田くんによる情報数学の解答です.感謝.
添付ファイル松本, Tue Jan 18 23:15:46 2005アルゴリズムとデータ構造2003年度期末試験の解答案を作りました。
なかなか範囲が広くて他の年度のも気合を入れてやっておかないと結構やばそう
な感じがしました。というわけで押えておくべきキーワードを挙げておきます(
教官のページにあるやつですが)
プログラムの実行時間
リスト・スタック・待ち行列
ハフマンコード
ハッシュ(オープンとクローズド)
ハッシュの解析
優先度つき待ち行列(ヒープ)
2分探索木
2分探索木の解析
2-3木(挿入と削除)
MF-SET
最長共通部分問題(LCS)
ダイクストラのアルゴリズム
フロイドのアルゴリズム
DAG
有向グラフの強成分の求め方
プリムのアルゴリズム
クラスカルのアルゴリズム
無向グラフの関節点の探し方
最大マッチングの求め方
バブルソート、内挿ソート、選択ソート
クイックソート
クイックソートの時間解析
マージソート
ヒープソート
ビンソート, 基数ソート
再帰方程式の解法(同次解と特解)
3角形分割問題
α―β枝刈り
分岐制約探索法(?)
2最適化によるTSPの最適化
大変だァ
添付ファイル高山, Thu Jan 20 03:17:30 2005さっそくミスを発見。図8の右下がおかしくなっていました。一応修正したのを
アップします。間違いを見つけられた方はご指摘ください。
添付ファイル高山, Thu Jan 20 03:34:58 2005遅いですが情報数学の3Bの解答
2.
例えば
(1 1 1 0 1 0 0
1 1 0 1 0 1 0
1 0 1 1 0 0 1)
解答はいくつかあるはずです.右3列が単位行列になっていて,どの2列も0でな
い互いに異なるベクトルになっていればOK.
3.
y = w + e(wが符号語,eがエラー)
と分解して,y(転置H) = e(転置H)を計算計算すればわかる.
4.
2.の解答に依存.この場合は
(1 0 0 0 1 1 1
0 1 0 0 1 1 0
0 0 1 0 1 0 1
0 0 0 1 0 1 1)
左4列は単位行列で,右三列は2.の左4列を転置してくっつける.
間違いあったら教えてください
松本, Thu Jan 20 22:39:56 2005遅いと思うけど、情報数学の 1B の 2 は [a]R*[b] が成立するか否かが同値類
の代表元のとりかたに依存しないことを言えばいいと思いますよ。
M2, Mon Jan 24 03:20:40 2005お二方、補完ありがとうございます。>情報数学
おーた, Tue Jan 25 21:12:20 2005OS試験の用語集
デッドロックとは
プロセス1が資源Aをロックしている状態でさらに資源Bをロックしようとする
。
プロセス2が資源Bをロックしている状態でさらに資源Aをロックしようとする
。
これが同時に起きると、どちらのプロセスも資源を使えず、またロック解除も
行えない。
これをデッドロックという。
プロセスの飢餓(餓死:starvation)とは
スケジューリングには、以下のようなものがある。
・到着順(FIFO)方式
到着したものから順に最後まで終わらせていく方式。
・ラウンドロビンスケジューリング
一定時間(time quantum)ごとに順番にプロセスやスレッドを選んで実行する
。
・Shortest Job First CPUスケジューリング
一番早く終わるものから実行していく
・プライオリティスケジューリング(処理時間順方式)
優先度の高いものから順に実行していく。
・フィードバック待ち行列方式
優先度の高いものから実行するが、ただし一定時間で終わらなければ優先度
を下げる。
・処理時間順方式
処理時間が短いものから実行していく。
ただし、通常は処理時間などわからないので、フィードバック待ち行列方式
で実装する。
プライオリティスケジューリングでは、I/O処理の完了待ちなどの理由で
優先度が低くても実行されることがあるが、
そういったI/O処理などがないプログラムの優先度が高いと、
優先度が低いものはまったく実行されないままである。これをプロセスの飢餓
という。
スラッシングとは
物理メモリの容量は、(近年増加しているとはいえ)あまり多いものではない。
従って、ハードディスクによる仮想メモリなどを使用することが多い。
すると、ハードディスクから物理メモリに読み込んだり物理メモリからハード
ディスクに
書き込んだりするような処理を行う必要がある。
この処理は、アプリケーションが多くのメモリを要求すればするほど発生する
が、
そうするとハードディスクやメモリへの読み込み・書き込み処理が
処理の中で大部分を占めるようになり、外部からの入出力を受け付けられなく
なったり
などのようなCPU利用効率が低下した状態に陥る。
この状態をスラッシングという。
CPU使用率とは
各プロセスやカーネルCPU処理がCPUを占有する時間と
Idle時間を含めた全時間の比である。
スループットとは
単位時間当たりの処理能力のこと
ターンアラウンドタイムとは
指示を出してから、全てが完了するまでの時間
応答時間(レスポンスタイム)とは
ターンアラウンドタイムと似ているが、入力完了から最初の応答が得られるま
での時間
入力完了と、指示を出すタイミングは異なり、また最初の応答と全てが完了の
タイミングも異なる。
従って、ターンアラウンドタイムよりは必ず短い。
待ち時間とは
待っている時間。すなわち、自分の番になるまでの時間である。
計算方法は、ターンアラウンドタイムから実実行時間を引いたもの。
VFSとは
様々なファイルシステムに対して、抽象的にアクセスできる仕組みのこと
そのために、ファイルオープンやファイルリード等のようなシステムコール群
の
インターフェース(API)を提供する。
そして、そのインターフェースに合致するような関数を各ファイルシステム用
に作る。
ユーザーはそのAPIに合致するように関数を呼び出せば、どのようなファイル
システムに
対しても、同じようにアクセスできる。
プロテクションとは
各ファイルにおいて、どのユーザーがどのような権限を持っているかを制御す
る機構のこと
アクセスコントロール方式では各ファイルに、どのユーザーがどのような権限
を持っているか
という情報を持たせる。
それに対して、Capability List方式では、各ユーザーに、どのファイルにど
のような
権限を持っているかを記述する。
例えば、アクセスコントロール方式
file hoge:
sawa: write read, kojima: execute, nakajima: read
file foo:
sawa: execute, kojima: read
というようなデータを記述する。
Capability List方式
domain sawa:
hoge: write read, foo: execute
domain kojima:
hoge: execute, foo: read
domain nakajima:
hoge: read
というデータを持たせる。
二相ロックとは
使う資源を一度に全て確保してしまい、また一度に全て開放する手法。
これにより、まず時間差で資源を確保することが無くなるのでデッドロックが
少なくなる。
そしてまた、トランザクションがひとつずつ実行されているのと同様の状態(
直列化)を保持できる。
Y.Sawa, Thu Jul 14 17:08:58 2005バージョンアップしました。今後はHikiにアップします。
http://is.zng.info/hiki/hiki.cgi?OS%A5%C6%A5%B9%A5%C8%A4%CE%A5%B7%A5%B1%
A5%D7%A5%EA
間違いなどあれば、修正してください。
Y.Sawa, Thu Jul 14 19:37:43 2005連投鬱
ひらの, Thu Jul 14 20:09:28 2005過去衛門
添付ファイル ry, Sat Aug 20 17:39:17 2005離散数学、最小費用流問題
授業の板書に曖昧でよくわからない部分があるので、以下のページを見たほうが
いいかも
プライマル・デュアルのアルゴリズム
http://www.aomori-u.ac.jp/intro/engineer/infosys/Labo/abstract-1999/IS82
5.html
ymatsu, Tue Sep 6 18:19:13 2005離散過去問解答例
ただし問題Vは未答
添付ファイル ymatsu, Thu Sep 8 02:03:21 2005U\∂Mというのが、Uから∂Mを除いた集合を意味するということを
やっと分かった今日この頃
ひらの, Thu Sep 8 22:59:42 2005なんか、演習問題の5(フローとか)は↓が参考になるような、ならないような。
http://coolee.at.infoseek.co.jp/graphtheory2.html
tokuda, Sun Sep 11 02:42:45 2005なんか、演習問題の5(フローとか)は↓が参考になるような、ならないような。
http://coolee.at.infoseek.co.jp/graphtheory2.html
tokuda, Sun Sep 11 02:43:04 2005二重投稿すみません。
tokuda, Sun Sep 11 02:43:54 2005知っている人も多いかと思いますが、細谷教官のウェブサイトに去年の過去問が
アップされています。
http://arbre.is.s.u-tokyo.ac.jp/~hahosoya/teach.html
で、それが過去衛門氏がうpしてくださった追試験と(たぶん)おんなじです。
ということは、今年も…?
というか誰か解答例をプリーズ。
letter, Sun Sep 11 18:20:28 2005コンパイラの追試問題を解いてみました。品質は無保証です。っていうか手で書
いたら3倍は早く終わったと思う。ぎゃー。
添付ファイル kosak, Sun Sep 11 20:25:05 2005問題2の (2) を豪快に無視してました...。たとえば Ocaml でいう let f x =
let g y = x + y in g は、f を抜けた後も f のローカル変数 x が生存してい
るため、スタックでは実現不能です。
kosak, Sun Sep 11 20:54:43 2005離散問題IIIの解答に一部おかしいところがありました.
線形計画問題の整数性を示すためには,係数行列がユニモジュラであることを示
す必要があります.
この場合は無向二部グラフの接続行列がユニモジュラであることを示す必要があ
ります.
ymatsu, Mon Sep 12 17:47:01 2005問題IIIについて訂正.
まず,無向二部グラフ(U,V,E)の各辺に対し,UからVへ向かうような向き付けを
与えることで,有向二部グラフ(U,V,A)に変換します.この接続行列をDとすると
,演習第1回の問題4の結果よりDは完全ユニモジュラなので,ユニモジュラであ
ることは容易に示せます.こうして,
maximize x_1+...+x_m
subject to
D x <= a
x_i >= 0
の形に書き直します.
ただし,aの第i要素は,iがUの頂点に対応するなら1,Vの頂点に対応するなら-1
とします.
Dがユニモジュラ,aが整数ベクトルより線形計画問題の整数性がいえます.
ymatsu, Mon Sep 12 22:51:08 2005パスは二郎くんの苗字(3文字)
添付ファイル 30日の試験の昔の過去問, Tue Sep 27 22:26:09 2005計算機構成法の去年の本試験(たぶん)(thanx tkd)
をテキストにした奴。
パスは二郎くんのHN(3文字)
添付ファイル letter, Wed Sep 28 16:52:21 2005パスは二郎くんの苗字
添付ファイル 古い過去問の解答, Thu Sep 29 23:44:35 2005言語モデル,計算量,ネットワーク,知能システムの過去問.
連続系は持ち込み可時代の超難問しか無かったので敢えてアップせず.
最近の連続系の過去問お持ちの方は是非アップしてください.
添付ファイル 名無しさん, Sun Jan 29 03:11:48 2006ヒント: アルバム
ry, Fri Aug 4 21:45:35 2006修正
2005専門I(2)(c) :
×I'
○J'
まぁ、分かりづらいのでちゃんと書き換えたほうがいいと思いますが、
とりあえずこれでよいと思われます。(thx to ymatsu)
こじま, Mon Aug 7 21:13:57 2006あとで気が付いたんだけれども,J'ではfの解釈が定義されているので,
I'をJ'に変えるだけだとまずい気がする.
やはり,
[[P]]J = (b_0, b_1, ..., b_{n-1}, b_n) =
(b_1, b_2, ..., b_n, b_n)
とでもするしかないんじゃなかろうか.
ymatsu, Tue Aug 8 10:15:53 2006X 「J'ではfの解釈が定義されているので,」
O 「J'ではfの解釈が定義されていないので,」
ymatsu, Tue Aug 8 10:16:43 2006データを追加しました。
ry, Sat Aug 19 21:55:16 2006