講義・演習‎ > ‎春・夏学期‎ > ‎

GSE62100 情報フルエンシー(Pythonによるアルゴリズムと問題解決の技法)

  • 2018年度 春学期 月曜3時限(13:30〜15:00)
  • コンピュータールームB
  • Teaching Assistant: 渡邉 一生,星野 佑
日付 内容  備考 
4月16日  ガイダンスとりあえずPython interactive shellを使ってみる第1回の宿題 着席表(4月15日版),
Pythonチュートリアル
Google code jam
4月23日  ソースコードの利用Store creditに挑戦(問題編)Reverse wordsに挑戦(問題編)第2回の宿題 今回は「とりあえずPython interactive shellを使ってみる」の「関数の定義と利用」から説明します.
5月07日  ファイル入出力Reverse wordsに挑戦(解答編)
Minimum scalar product(問題編)
第3回の宿題,第3回の課題はMoodleのコースに掲載

5月14日 プログラミングコンテストの簡単な問題に挑戦
Store creditに挑戦(解答編)Speaking in tonguesに挑戦(問題編)
第4回の宿題
第4回の課題はMoodleのコースに掲載
着席表(5月8日版),
今回はReverse wordsに挑戦(解答編)の「リストの操作を簡潔に」から説明します.
5月21日  プログラミングコンテストの簡単な問題に挑戦の続き
Speaking in tongueに挑戦(解答編)Minimum scalar productに挑戦(解答編)
Bullseye(問題編)Crop triangles(問題編)
第5回の宿題,次回は小テストの練習をします.
第5回の課題はMoodleのコースに掲載
ACM-ICPCへの誘い(2016年度版)
ここまでの知識で
ACM-ICPC Japan domesticのA問題は解けると思います.
実際に解いて試したいならばAOJに登録して試してみると良いかも.
5月28日  小テストの練習(出題はACM-ICPC Japan domestic 2017のA問題),
2分探索の利用,計算時間の見積り,
Bullseye(解答編)Crop triangles(解答編)
第6回の宿題は特になし(次回の小テストに備えてください),
今回は課題なしです.
2分探索による平方根の見積り
2分探索で解けそうな問題: Jane's flower shop解答編),など
6月04日  小テスト(出題はACM-ICPC Japan domestic A問題の2007年から2016年のどれか一つ),
AOJやGCJ2018以降の参加のデモ,
Crop triangles(解答編の続き),
第7回は宿題なし,
第7回は課題もなし
今回はCrop triangles(解答編)の「計算時間の計測」から説明します.
ACM-ICPC 2018
申込開始: 2018年6月上旬
申込締切: 2018年6月21日(木)
国内オンライン予選: 2018年7月6日(金)夕方
アジア地区横浜大会: 2018年12月8日から10日
6月11日 小テスト(出題はACM-ICPC Japan domestic A問題の2007年から2016年のどれか一つ),
グラフ探索の利用,
Watersheds(問題編)
グラフ理論とグラフ探索の基本関連する講義資料),グラフ探索のコード例
第8回の宿題は「Watershedsの解答を自分なりに作ること」とします.グラフ探索のコード例を利用すること推奨です.
第8回の課題はなしです.
挑戦したい問題: All your base,Country leader
6月18日  小テスト(出題はACM-ICPC Japan domestic A問題の2007年から2016年のどれか一つ),
Watershedsに挑戦(解答編)
グラフ探索と列挙
第9回の課題: Watershedsの解答にわかりやすいコメントを入れたものをMoodleで提出する.dynamic gridの解答例を作り,わかりやすいコメントを入れてMoodleで提出する.
第9回の宿題: Ample syrupSpace cubesの問題を読む
グラフ探索を使えば解けそうな問題
dynamic grid池のある庭園迷宮を一周(ちょっとむずかしい),文字解読(ちょっとむずかしい),橋の撤去
6月25日 minimum scalar product small datasetの列挙による解答編
Ample syrupに挑戦(問題編),Space cubesに挑戦(問題編)
第10回の課題: アルゴリズムを利用してample syrupのsmall datasetを部分集合列挙で解く解答コードを作る,またspace cubesのsmall datasetを部分集合列挙で解く解答コードを作る.
第10回の宿題: gCampusの問題を読む.
部分集合を列挙できれば解けそうな問題
Ample syrupのsmall dataset,Space cubesのsmall dataset,
7月02日 小テスト(dynamic gridから出します.ただし,全体は長いコードになるので,部分的に抜き出して出題します.)
動的計画法単始点最短路問題とダイクストラ法
中くらいの難しさの問題への挑戦,
全点間最短路問題とFloyd-Warshall法gCampusに挑戦(問題編)
第11回は課題なし.
第11回の宿題: technobabbleの問題を読む.
ダイクストラ法を元にすると解きやすそうな問題: gCampuscrossing the roadpony express
7月09日 最大流の利用
technobabble(問題編)
ネットワークフロー(スライド)最大流問題とその解法グラフ上の最短路問題Edmonds-Karpアルゴリズムの実装
第12回の課題: gCampusを解く解答コードを作り,わかりやすいコメントを入れてMoodleの「第12回課題」に提出する.
第12回の宿題: technobabbleの解き方を考えてくる.(難しいようならばsmall datasetに対する部分集合列挙アプローチだけでも作ってみる.)

7月16日  小テスト(gCampusから出します.ただし,全体は長いコードになるので,部分的に抜き出して出題します.)
難しい問題に挑戦
technobabble(解答編)
第13回の課題: Technobabbleを解くコードを作り,わかりやすいコメントを入れてMoodleの第13回課題に提出する.Small datasetのみに対応できるコードでもよい.

7月23日 数理最適化の利用線形最適化の説明整数最適化の説明),
機械学習の利用
TensorFlowMNIST for ML beginners

  授業時間外の学修課題(詳細はMoodleに,提出締切は7月31日)