情報科学科 ネットワークシステムコース 西関研究室.

Presentation on theme: "情報科学科 ネットワークシステムコース 西関研究室."— Presentation transcript:

1 情報科学科 ネットワークシステムコース 西関研究室

2 西関研ではアルゴリズムの研究をしています．
ミールカードを例にとって紹介してみましょう． 年会費払うだけで １日800円までは無料 お得 300円余り ぴったり 500円 800円

3 献立の選び方 メニューは40種類 学食 メニューを取るかどうか 240通りの献立 約 通り!!

4 ＝アルゴリズム 計算の仕方 ？ 40種類のメニュー 800円の献立 カタカタカタ 計算の仕方を パソコンは言われた パソコンを 1兆通りから
教えなければ ならないね． パソコンを 　　　使えば・・・ パソコンは言われた ことしかやってくれないよ． 1兆通りから どうやって選ぼう・・・

5 入力 出力 40種類のメニュー 800円の献立 １秒 3日 良いアルゴリズム 悪いアルゴリズム ・計算時間が速い ・計算時間が遅い 良いアルゴリズムを考えることは大切！！

6 西関研ではアルゴリズムの研究をしています．
具体的な研究例 　　・ 停電復旧法 　　・ 板金加工手順 　　・ スケジューリング 　　・ チップの配置法 など

7 チップの配置法 7個のチップを1枚の基盤に埋め込みたい！

8 チップの配置法 1 2 3 4 5 6 7 2 1 4 3 6 7 5 1番のチップは3番，4番，5番，7番のチップと繋いで 2番のチップは4番，5番，6番のチップと繋いで 3番と6番、4番と7番のチップを繋ぐ。

9 チップの配置法 2 1 4 3 6 7 5 しかし、このように何も考えずに配置してしまうと、 回路がショート（交差）してしまう。

10 チップの配置法 1 3 5 6 2 7 4 このようなチップの配置の仕方ならショートしない チップを うまく 配置する方法を求めたい

11 入力 出力 実際には 数十個 「うまく」が困難になってくる アルゴリズムを作って自動で配置しよう！ グラフ描画

12 具体的な研究例 ・ 停電復旧法 ・ 板金加工手順 ・ スケジューリング ・ ＶＬＳＩの配線法 など
西関研ではアルゴリズムの研究をしています． 具体的な研究例 　　・ 停電復旧法 　　・ 板金加工手順 　　・ スケジューリング 　　・ ＶＬＳＩの配線法 など

13 応用例（電力網） 変電所 工場 電線 住宅

14 応用例（電力網） 故障で停電が発生したとき・・・ 実際に電力を 送っている区域

15 応用例（電力網） 多くの停電区間を復旧できる送り方をより早く求めたい 従来 現在 経験則 アルゴリズム 停電区間

16 ＶＬＳＩの配線法 素子の数が増えると．．． 200個 (推定) 「うまく」が困難になってくる アルゴリズムを使って自動で配置しよう！

17 まとめ 西関研究室ではアルゴリズム、特に グラフアルゴリズムの研究を行っています。 アルゴリズムとは計算の仕方のことです。
アルゴリズムにはいいアルゴリズムと 悪いアルゴリズムがあります。 良いアルゴリズム 悪いアルゴリズム ・計算時間が速い ・計算時間が遅い 例

18 離散アルゴリズムの設計・解析 グラフとネットワークの理論
　　効率のよい離散アルゴリズムの統一的設計法、アルゴリズムの新しい解析法などの研究を行います。 　　また、グラフ理論、ネットワーク理論、計算幾何学などの離散数学、大規模システムの設計や可視化のためのグラフ描画、秘密共有法などの情報セキュリティも扱います。

19 西関研のイベント ４月 花見 ７月 暑気払い １０月 芋煮会 １１月 駅伝大会＆おでん １２月 忘年会 ３月 送別会

20

21 ここまでののまとめ 西関研究室では アルゴリズムの研究を行っています。 40種類のメニュー 800円の献立 アルゴリズム＝ 計算の仕方

22 まとめ 西関研究室ではアルゴリズム、特に グラフアルゴリズムの研究を行っています。 アルゴリズムとは計算の仕方のことです。
アルゴリズムにはいいアルゴリズムと 悪いアルゴリズムがあります。 西関研究室では既存のアルゴリズムを良い アルゴリズムに改良したり、新しいアルゴリズム を作ったりしています。

23 今日のまとめ アルゴリズムとは 40種類のメニュー 800円の献立 アルゴリズム＝ 計算の仕方 グラフ化とは 1 2 6 7 5 3 4

24 ＶＬＳＩの配線法 アルゴリズム 入力：点と辺の関係 (点1は点3，4，5，7と接続，点2は・・・．) 出力：交差がないグラフの描画

25 ＶＬＳＩの配線法 アルゴリズム グラフを 様々な条件 の下で描くことが研究の目的 交差，大きさ etc．

26 ＶＬＳＩの配線法 2 1 4 3 6 7 5 1番のVLSIは3番，4番，5番，7番のVLSIと繋いで 2番のVLSIは4番，5番，6番のVLSIと繋いで 3番と6番、4番と7番のVLSIを繋ぐ。

27 ＶＬＳＩの配線法 アルゴリズム アルゴリズムを使って 自動で配置しなおすことができる

28 ＶＬＳＩの配線法 2 1 4 3 6 7 5 1番のVLSIは3番，4番，5番，7番のVLSIと繋いで でも、このVLSIの配置では配線がショート（交差）してしまう。 2番のVLSIは4番，5番，6番のVLSIと繋いで 3番と6番、4番と7番のVLSIを繋ぐ。