総合分析情報学コースを徹底分析! 歴代出題テーマとキーワード

2020年3月8日

東京大学大学院 学際情報学府 学際情報学専攻 総合分析情報学コースの出題テーマ・キーワードをまとめました。どの年度もコンピューターサイエンスの幅広い知識が求められていることがわかります。

2018年度以降は6問構成で、第1問・第2問が必答問題となり、出題範囲も増えています。特にネットワークやアーキテクチャの分野では、情報や処理の一連の流れを詳細に述べることが求められています。

  第1問 第2問 第3問 第4問 第5問 第6問 第7問 第8問
07夏 微分方程式、ポアソン過程 グラフ、横型探索、縦型探索 再帰アルゴリズム、末尾再帰 分散並列処理、プロセス間通信(遠隔手続き呼び出し、分散共有記憶)、クラスタリング、グリッド・コンピューティング スレッド、アトミックオペレーション、同期・排他制御、セマフォ TCP、フロー制御、輻輳制御、輻輳ウィンドウ、パケットロス デコーダー、ALU  
07冬 確率、コイン投げ A*アルゴリズム、ダイクストラ法 命令レベル並列化、共有メモリ型・分散メモリ型・対象型・非対称型マルチプロセッサ producer-consumer問題、ビジーウェイティング、セマフォ 抽象データ型、オブジェクト指向型言語、多重継承、単一継承 プロトコルのレイヤー構造、砂時計モデル、パケットスイッチング、サーキットスイッチング、パケットロス、パケット遅延 全加算器、キャリー先読み回路  
08夏 ラプラス変換、微分方程式 ゲームのアルゴリズムの構想 レジスタ修飾、インデックス付きアドレッシング、ベースアドレッシング、PC相対アドレッシング、アドレッシング方式のトレードオフ スレッドの同期、デッドロック、ミューテックス、優先度上限プロトコル、リソース順序付け 正規表現、BNF、正規文法、文脈自由文法、文脈依存文法、生成規則 TCP/IP, BGP, ICMP, SMTP, HTTP, CIDR, サブネット・スーパーネット, AS, DNS, インターネットの過程を詳細に述べる フリップフロップ、DRAM,SRAM 空間的自己相関、バッファリングによる空間分析、空間データにおける属性データ、点データ、線データ、面データ、ラスターデータ、ベクターデータ、トポロジー、空間的スケール・解像度
08冬 連立微分方程式 全域木、最小全域木、最小全域木を求めるアルゴリズム 仮想記憶、アドレス変換、TLB、内部・外部フラグメンテーション 分散並列処理、プロセス間通信、排他制御、(タプルスペース) マクロ、マクロによる高速化 輻輳制御、スロースタート、AIMD、TCP 7セグメント回路のデコーダー 空間スケール・時間スケール、オーバーレイ、空間データの種類と特徴、空間情報の例とその向上
09夏 極限、積分、最小値 フィボナッチ数とそのアルゴリズム 記憶階層、キャッシュヒット率、平均アクセス時間、キャッシュのアドレスマッチングと書き込み方式 末尾再帰とその解決 多重プロセス、デッドロック、哲学者の食事問題 TCP、UDP、TCPの特徴を近似する方程式、物理層・リンク層の伝送技術・伝送速度、高帯域通信 マグニチュード・コンパレータ(絶対値比較器) 位置データと属性データ、位置を特定・記述する方法とその特徴、属性データの尺度基準とその特徴、地図の歪み、スケール、使いやすい空間情報の提示方法
09冬 固有値と固有ベクトル、対角化、行列のn乗 クイックソート、B木 パイプライン、データハザード、制御ハザード、構造ハザード、スーパーパイプライン、スーパースカラ、VLIW コンパイラ、インタプリタ、仮想機械 ページング方式、セグメント方式、ファーストフィット、ベストフィット、ワーストフィット、SSD トンネリング、オーバーレイネットワーク、セグメントサイズ 素数識別論理回路、クワインマクラスキー法、ムーアの法則、MOS回路のスケーリング則 空間参照系、ユビキタスコンピューティング、状況認識(コンテクスト・アウェアネス)、現実世界と仮想世界の融合
10夏 微分方程式 数列、行列を用いた数列の高速化とその計算量 浮動小数点数、RAID、DMA ページ置き換えアルゴリズム、FIFO、LRU、ページフォールト ソート、リンクトリスト IP、IPヘッダ、Time to Live、Header Checksum、NAT 組み合わせ回路の解析(加算器)、順序回路の解析(JKフリップフロップ)、AD変換回路 ラスターデータ、属性データ、混合画素(混合ピクセル)、空間データ、誤差、不確実性、GPS、緯度・経度、世界測地系、距離抵抗、重力モデル、物理的距離と認知距離
10冬 極限、極座標で表された部分の面積、確率、確率分布、一様分布、期待値、指数分布 文字列検索アルゴリズム、Quick Search法 MIPS、CPI、リング保護、アクセス制御リスト、ケイパビリティ プロセスの情報、I/O bound、CPU-bound、並行プロセスの同時実行制御機構、スケジュラー、O(1)スケジュラー、CFS アッカーマン関数、動的計画法 TCP、TCPヘッダ、ポート、フロー制御、エンドツーエンド原理 BCD adder、line decoder、フリップフロップ、クロック周波数の高速化を阻む技術的要因 地図、投影法、縮尺、空間参照系(座標系)、位置(場所)特定、実空間、仮想空間、空間情報の整備・利用におけるユビキタスコンピューティングの応用
11夏 ベクトル積、スカラー3重積、行列式、逆行列、定積分 ハノイの塔 オブジェクト指向言語、多重継承、抽象クラス、純粋仮想関数、仮想関数テーブル、ダックタイピング、メモリレイアウト、ポインタ、メソッド呼び出し 割り込み処理、サブルーチン、パイプラインハザード、機械語への翻訳 スケジューリング、到着順、処理時間順、プリエンプション、平均応答時間 経路制御、ルーティング、フォワーディング、最短経路、距離ベクトル、階層構造 ブール式の簡約化、組み合わせ回路、パリティチェック回路、2乗回路 空間分布、密度、分析単位、測量、基準点、電子化、ナビゲーション、屋外、屋内、位置情報、誤差、精度、不確実性、人間の空間の認識や伝達
11冬 極値、微分方程式、連立微分方程式、重積分、円柱の共通部分の体積 PageRank 文字列検索アルゴリズム、ずらし表、BM法、KMP法 直接アドレス、間接アドレス、総体アドレス、インデックス修飾アドレス、乗算命令、加算命令、ビットシフト命令、連想記憶、キャッシュメモリの制御 ページ置換アルゴリズム、LRU、キャッシュ・コヒーレンシー機構、ライトスルー、ライトバック AS、AS内経路制御、メッセージの複雑性、収束性、エラーに対する堅牢性、AS間経路制御、prefix hijacking、Hot Potato Routing 比較器、7セグメントデジタル表示器、積和標準形、ドントケア、真理値表、カルノーマップ ベクターデータ、トポロジー、地理情報システム、レイヤ、オーバーレイ解析、視覚化、主題図、資格変数、空間事象、位置情報の整備や応用
12夏 極限、微分方程式、タンクの水 数列の漸化式、数列を求めるアルゴリズム、計算量 正規表現、文字列照合プログラム、再帰呼び出し 仮想記憶、ヒット率、平均アクセス時間、マルチコア デッドロック、割り込み、クリティカルセクション、システムコール、FIFO、LRU、ページフォールト TCP、UDP、ACK、シーケンス番号、ウィンドウ、輻輳制御 補関数、シフトレジスタ、フリップフロップ 空間情報を利用したシステム・サービス
12冬 極限、微分方程式、陰関数の面積 AND/OR木、ゲーム木、ミニマックス法、アルファベータ枝刈り 再帰呼び出しを含まないプログラム、BNF文法、解析技、曖昧性除去 segmantation fault、スタック、スタックポインタ、割り込み、割り込み処理ルーチン、割り込みベクタ リング型バッファ、生産者-消費者問題、セマフォ、P命令、V命令、相互排除 OSI参照モデル、イーサネット、IP、TCP、HTTP、フロー制御、輻輳制御、複数ウィンドウ 全加算器、キャリルックアヘッド、簡約化 空間的近接性指標、直線距離
13夏 連立一次方程式、テイラー展開、収束半径、定積分 編集距離、動的計画法 マージソート キャッシュメモリ、スラッシング、キャッシュミス、メモリ階層 ファイルシステムの設計、領域割当、制御情報管理、入出力法、リスト管理、ビットマップ管理、アクセス制御リスト方式、ケーパビリティ方式 MACアドレス、IPアドレス、ホスト名、NAT、イーサネットプロトコル、VLAN、ハブ、スイッチ、ルータ、CSMA/CD、CSMA/CA、ARQ、ARP Query、ARP Reply、Ethernet、
MAC、IP、UDP、TCP、 Slow-Start、Congestion-Avoidance、Flow-Control、
DNS、OSPF、HTTP、Congestion Control、IEEE 802.11、802.1X、WPA2、パケット遅延、パケットロス
ブール関数、乗法標準形、論理回路、乗算回路 ベクタ型データ、ラスタ型データ
13冬 微分方程式、固有値、対角化、勾配 ダイクストラのアルゴリズム 勾配降下法 デッドロック、DAC、MAC、同期型・非同期型メッセージパッシング 浮動小数点数、Little Endian、Big Endian、ダイレクトマップ方式、フルアソシアティブ方式、セットアソシアティブ方式 チェックサム、TCP、UDP、ACK、NACK、CRC、パリティチェック、エラー訂正 全加算器、全減算器、マルチプレクサ、ALU ボロノイ分割、バッファリング、集計データ、可変単位地区問題、グルーバル解析、ローカル解析
14夏 極限、微分方程式、対角化 過半数要素の判定アルゴリズム 最大公約数を求めるプログラム 3階層の既得システム、分岐命令、アクセス時間、プロセッサデザイン、命令セットとキャッシュメモリのトレードオフ セマフォ、メッセージパッシング、P命令、V命令 TCP、輻輳制御、AIMD、接続確立と終了、公平性 ミーリー型順序機械、ムーア型順序機械、自動販売機の制御、フリップフロップ 位置情報、データ共有、プライバシー、ナビゲーションシステム、方向感覚、位置誤差、少子高齢化、都市の縮小、用途混合、情報管理、情報伝達、情報利用
14冬 微分方程式、円柱と放物面の体積、重積分、行列の10乗 バイナリデータの圧縮アルゴリズム 末尾再帰、文脈自由文法 キャッシュメモリ、ライトスルー、ライトバック、TLB、パイプライン、条件分岐 ページング、局所ページ置き換え、帯域ページ置き換え、LRU、FIFO、共有メモリ型マルチプロセッサ 5層スタック、カプセル化、BGP、DHCP、ARP、OSPF、RIP、DNS、IPアドレス、MACアドレス、RTT、TCP ブール式の簡約化、全加算器、デコーダ、マルチプレクサ、ALU 位置情報、座標参照系、位置特定、空間相互作用、重力モデル、ネットワーク距離、持続可能性、スマートシティ、情報技術、主題図
15夏 微分方程式、テイラー展開による近似 ゲーム木、アルファベータ法 再帰呼び出し FIFOアルゴリズム、キャッシュヒット率、キャッシュブロックサイズ、キャッシュメモリ容量、LRU、GPGPU、MMU、SIMD スケジューリング、優先度、クォンタム、ラウンドロビン、待ち行列 TCP、ARP、フロー制御、輻輳制御、パケットの送受信 扇風機の操作、PLD、HDL 地図情報、スケール、解像度、ビッグデータ、オープンデータ、秘匿化、電子地図、実空間、参照(基準)点、状況認識、行動支援システムの開発・利用
15冬 ベクトル解析、rot、div、テイラー級数展開 グラフ、ダイクストラのアルゴリズム フィボナッチ数 マルチコアアーキテクチャ、キャッシュメモリ、平均アクセス時間 ビットマップテーブル、連結リスト方式、ビットマップ方式、連続割当方式、索引割当方式 ping、traceroute、ARP、DHCP、DNS、OSPF、BGP 順序回路、フリップフロップ、ブール関数 位置情報サービス、位置特定、状況認識、ラスターデータ、ベクターデータ、解像度、地図投影法、空間参照系、歪み、地理的減少、空間減少、空間相互作用、距離抵抗、重力モデル、空間行動
16夏 極限、連立微分方程式 部分集合選択ゲーム 階乗 メモリ管理アーキテクチャ、ベストフィット、ファーストフィット、マイクロプログラム、バス、メモリマップドI/O デマンドページング、プリページング、ページテーブル、ページフォールト、TLB 輻輳制御、Cumulative ACK、Duplicate ACK、シーケンス番号、パケットロス、遅延、TCP、信頼性、EWMA、Deviation、Premature Timeout、Round Trip Time、Fast Retransmit、Fast Recovery、NAT、アドレス変換、TCP帯域の近似 順序回路、簡約化、ブール代数式 位置情報、空間参照系、空間言語、空間分布、空間的自己相関、距離、都市の縮小、コンパクトシティー、空閑地、オーバーレイ、バッファリング、カーネル密度推定、環境、心理、情報技術の応用
16冬                
17夏 行列式、微分方程式 ハフマン符号 JITコンパイレーション、正規表現 パイプライン処理、MIPS、フォワーディング、アウトオブオーダー実行 排他制御、機械語、同期命令 マンチェスター符号化方式、CSMA/CD、リアルタイム性、TCP/IP、経路制御表、スライディングウィンドウ方式、フロー制御 下方標準形、クワイン法、第一次圧縮、ムーアの法則、リテラル 空間データ、データモデル、属性情報、地図、大縮尺、小縮尺、詳細さ、ナビゲーション、ランドマーク、空間参照、GIS
17冬 極限、同時分布、周辺分布 逆ポーランド記法、スタック、キュー、連結リスト 辞書式比較、再帰呼び出し、文脈自由文法 シングルサイクルプロセッサ、マルチサイクルプロセッサ、可変長クロック、CPI、プログラムカウンタ、命令レジスタ、データレジスタ、レジスタファイル、ALU、メモリ、ロード命令、ストア命令、レジスタ命令、ブランチ命令、ジャンプ命令、命令フェッチ、デコード、メモリアドレス計算、レジスタ計算、メモリアクセス、ライトバック、ブランチ、ジャンプ、コンパイル、プロセッサの効率向上 プリエンプティブCPUスケジューリング、デッドロックの防止、プリページング、ディスクスケジューリング、マイクロカーネルアプローチ アドレス変換、MACアドレス、ARP、TCP、経路制御、IoT、CDMA、6LoWPAN、CoAP、REST 正規表現、順序回路、真理値表、状態遷移図、ミーリーマシン、Carry Look Ahead Adder、PLD、HDL 空間参照、空間参照システム、社会基盤、オープンデータ、空間行動、GISデータのモデル、ラスターデータ、属性値の基準
18夏 テイラー展開、固有値、固有ベクトル、微分方程式 逆ポーランド記法、例外処理 確率変数、ベイズの定理、期待値、分散、決定木、ランダムフォレスト、特徴ベクトル、訓練例、テスト例、過学習、交差検定、正則化、バックプロパゲーション、損失関数 IoT、Restful API、LPWA、KVS、無線通信装置を用いた測位システム マルチタスク処理、ポリング、割り込み、ネットワークデバイスの入出力、CPUバウンド、I/Oバウンド、クラウド、データキャッシュ、PMD、MEC、SDN、ブロックチェーン、DDos攻撃 FPGA、ASIC、論理ゲート、論理ブロック、I/Oパッド、配線チャネル、ルックアップテーブル、全加算器    
18冬 2変数関数の最大最小、立体の面積、鉛直投げ上げ(力学) 二分探索木、再帰呼び出し、ハッシュ表 確率密度関数、分布関数、期待値、従属変数、回帰分析、線形回帰、非線形回帰 RFID、GPS、携帯端末の認証、センサー情報の応用 OSの仮想化技術、ネットワークの仮想化技術、データセンターのネットワーク、VPN、VLAN、SRIOV、NFV、ネットワークスライシング マンチェスターコーディング、エンディアン、セットアソシアティブキャッシュ、クロック周波数、CPI、組み合わせ回路、真理値表、ブール式、ゲート図    
19夏 漸化式、メタン分子の構造、3重積分、極座標への変換 双方向連結リスト、二分ヒープ ベン図、ベイズの定理、ニューラルネットワーク、入力層、中間層、出力層、教師あり学習、教師なし学習 GPS、環境発電、利用者の持つ情報、時計の同期 CPUのスケジューリング、ページフォールト、ページテーブルの階層化、ページ置き換えアルゴリズム、デッドロック、アトミック命令、相互排除 マルチプレクサ、RSフリップフロップ、スーパーパイプライン、VLIW、スーパースカラ、アウトオブオーダー実行、投機的実行、LAN、イーサネット、マンチェスターエンコーディング、CSMA/CD、CRC、誤り検出、リピーター、ブリッジ、ルーター    
19冬 固有値、固有ベクトル、微分方程式、極値、積分 動的計画法、末尾再帰 期待値、分散、ベルヌーイ試行、尤度、ベータ分布、事前分布、事後分布、教師あり学習、教師なし学習、強化学習、訓練例、テスト例、方策、価値関数、ニューラルネットワーク、k-means、分類、回帰、クラスタリング、マルコフ決定過程、Q学習 RFID、パッシブ型RFID、衝突回避、transponder、二分木、地理情報システム、最近傍探索 プロトコル、インターネットの5層プロトコル、輻輳制御、フロー制御、TDMA、FDMA、CDMA、CSMA、トークンリング、CDN、OTT、ネットワークスライシング、5G、ネットワーク・ソフトウェア化 ISA、FLOPS、RISC/CISC、Pipeline Hazard、ALU、TLB、Register File、SIMD/MIMD、MADD(積和演算)、ASIC、コンピューターの基本的なアーキテクチャ、命令の実行ステップ、CPUとGPUの相違点、GPUのアーキテクチャ