理工学部Faculty of Science and Engineering
COT200XG（計算基盤 / Computing technologies 200）創生科学基礎演習IIIExercises of Fundamental Informatics III
金沢 誠Makoto KANAZAWA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2023 |
| 授業コードClass code | H9050 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 木1/Thu.1 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 小西館‐W204 |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | ○ |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
創生科学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
(Course outline)
The course introduces the students to functional programming as well as to various fundamental notions in programming and software development in general.
(Learning objectives)
The goal is to be able to do the following:
- to write programs in Haskell to solve various combinatorial problems
- to test your program automatically using QuickCheck
- to compare efficiencies of different programs for solving the same task
- to write programs following the principle of modular design
(Learning activities outside of classroom)
Students are expected to read the relevant part of the textbook prior to each class meeting, and to work on the assigned homework.
(Grading Criteria)
The grade will be based on the submitted homework assignments (100%).
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
プログラミング言語Haskellを通して，関数プログラミングの考え方と，プログラミング全般に関する次のような基礎的事項を学ぶ。
・再帰的な関数の定義
・帰納的なデータ型の定義
・モジュール化
・抽象的データ型
・アルゴリズムの効率
到達目標Goal
・Haskellを使っていろいろな問題を解くプログラムを書くことができる。
・QuickCheckを用いてプログラムの自動テストを行うことができる。
・プログラムの効率の良さを比較することができる。
・モジュール化されたプログラムを書くことができる。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
講義と演習を組み合わせて行う。演習では，学生に対して個別に指導する。課題の提出・フィードバックは「学習支援システム」を通じて行う。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：集合，型，簡単な計算
集合に関するおさらい，Haskellにおける型，数式，関数の定義
2[対面/face to face]：ヴェン図と論理結合子，リストと内包表記
論理結合子，真理表の計算，リスト，リストに対する関数，文字列，タプル，リスト内表表記，列挙式
3[対面/face to face]：素性と述語，プログラムのテスト
対象領域の表現，複雑な性質の表現，テストによるバグの検出，性質に基づくテスト，QuickCheckを用いた自動テスト
4[対面/face to face]：リストと再帰
再帰的な関数の定義，リストの整列，再帰とリスト内表表記の対比
5[対面/face to face]：さらに再帰について
再帰的定義の停止性，無限リストと遅延評価，いろいろな再帰関数，再帰と帰納法
6[対面/face to face]：高階関数
再帰的定義に共通なパターン，map, filter, foldr/foldl, カリー化と部分適用
7[対面/face to face]：さらに高階関数について
ラムダ式，関数合成，カリー化とアンカリー化
8[対面/face to face]：代数的データ型
列挙型，タプル，リスト，Maybe型，Either型
9[対面/face to face]：式木
木，数式，数式の評価，命題論理式，命題論理式の評価，命題論理式の充足可能性，構造的帰納法，相互再帰
10[対面/face to face]：関係と量化子
量化子の表現，二項関係
11[対面/face to face]：データの表現
big-O記法，集合の4つの表現（リスト，重複のない整列されたリスト，順序木，AVL木）
12[対面/face to face]：データ抽象化
モジュール，集合の4つの表現のモジュール化，抽象的データ型
13[対面/face to face]：組み合わせアルゴリズム
重複の除去，部分リスト，デカルト積，リストの置換，k個の要素の選び方，数の分割，エイト・クイーン，
14[対面/face to face]：組み合わせアルゴリズム（続き）
組み合わせアルゴリズムに関する応用問題
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】
テキストの該当箇所をあらかじめ読んでおく。
授業内で示された課題を完成させる。
テキスト（教科書）Textbooks
Donald Sannella, Michael Fourman, Haoran Peng, and Philip Wadler. 2022. Introduction to Computation: Haskell, Logic and Automata. Springer.
https://doi.org/10.1007/978-3-030-76908-6 （法政大学のネットワークからダウンロード可能）
https://www.intro-to-computation.com （著者によるこの本のサイト）
テキストは英文だが，日本語による講義資料を用意する。
参考書References
Graham Hutton 著，山本和彦 訳．2019. プログラミングHaskell 第2版．ラムダノート．
https://www.lambdanote.com/products/haskell
成績評価の方法と基準Grading criteria
毎回の課題の評価による（100%）．毎回の出席が必須．
学生の意見等からの気づきChanges following student comments
本年度授業担当者変更によりフィードバックできません．
学生が準備すべき機器他Equipment student needs to prepare
ノートパソコン．
その他の重要事項Others
プログラミングの経験は必要としない。HaskellはJavaやPythonのような手続き型言語とは大きく異なるが，プログラミング初心者にも修得可能である。