[Python] 重み無し単一始点最短経路問題
Python で重み無しの有向グラフの単一始点最短経路問題を解きます。 以下の続きです。 最短経路問題 グラフ理論における最短経路問題（さいたんけいろもんだい、英:shortest path problem）とは、重み付きグラフの与えられた2つの...
[Python] トポロジカルソート
トポロジカルソートを Python で書きます。 以下の続きです。 トポロジカルソート トポロジカルソート（英:topological sort）とは、グラフ理論において、有向非巡回グラフ（英:directed acyclic graph, DA...
[Python] BFSによるグラフの探索
無向グラフをBFSで探索するアルゴリズムを Python で記述します。 以下の続きです。 幅優先探索 幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(...
[Python] DFSによるグラフの探索
無向グラフをDFSで探索するアルゴリズムを Python で記述します。 グラフは隣接リストを用いて表現します。 深さ優先探索 深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）...
GNUライセンス
問題 電機メーカのA社は，GPLが適用されたオープンソースソフトウェアの一部を改変した二次的著作物を搭載してテレビの新製品を開発した。この製品を販売するに当たり， A社が求められるGPLのルールに則した適切な対応はどれか。 請求があればA社が修正した部分を含む全ての...
CGに関する用語の説明 (2)
問題 コンピュータグラフィックスに関する記述のうち，適切なものはどれか。 テクスチャマッピングは，すべてのピクセルについて，視線とすべての物体との交点を計算し，その中から視点に近い交点を選択することによって，陰面消去を行う。メタボールは，反射・通過方向への視線追...
CGに関する用語の説明 (1)
問題 CGにおける基本的な用語の説明として，適切なものはどれか。 アンチエイリアシングとは，画像のサンプリングが不十分であることが原因で生じる現象のことである。レイトレーシングとは，曲面を陰影によって表現することである。レンダリングとは，ウィンドウの外部の図形を...
バッカス・ナウア記法
問題 あるプログラム言語において，識別子(identifier)は，先頭が英字で始まり，それ以降に任意個の英数字が続く文字列である。これをBNFで定義したとき，a に入るものはどれか。 <digit>::＝0｜1｜2｜3｜4｜5｜6｜7｜8｜9 <...
[Python] 隣接リストを用いてグラフを表現
下記の記事の続きです。 Python で隣接リストを用いてグラフを表現します。 隣接リスト 隣接リスト（英: adjacency list）は、グラフ理論でのグラフにある頂点または辺を全てリスト（一覧）で表現したものである。 出典: フリー百...
[Python] 隣接行列を用いてグラフを表現
Python で隣接行列を用いてグラフを表現します。 グラフ理論については、下記を読んでいる途中です。 グラフ理論講義ノート 隣接行列 グラフ理論および計算機科学において、隣接行列（りんせつぎょうれつ、英:adjacency matrix）は、...