コンピュータ数学基礎２及び演習 A組

Mathematical Basics of ComputerScience 2 A組

9914G31

14ISCIP202

須田　智晴、関川　浩

Hiroshi Sekigawa

2024年度後期

2024 Second Semester

月曜4限、木曜1限

Monday 4th Period and Thursday 1st Period

理学部第一部　応用数学科

Department of Applied Mathematics, Faculty of Science Division Ⅰ

3.0単位

講義/演習

Lecture/Seminar

-

① [対面]対面授業/ [On-site] On-site class

効率のよいプログラムを書くための基礎となる，基本的なデータ構造とアルゴリズムについて説明する．また，アルゴリズムの計算量についても説明する．実際にコンピュータを用いた演習も行う．本授業の内容は効率的なプログラミングの理論的な基礎となるものであり，担当教員が企業の研究員のときに，実際にどのように利用したかについても言及する予定である．

本科目は本学科のカリキュラム・ポリシーに定める「応用数学に特化した内容の基礎部分」を扱う科目の一つであり，ディプロマ・ポリシーに定める「数学を中心とする基礎知識を習得し、数学の応用領域を体系的かつ統合的に理解できる能力」の一部を身につけること，具体的には，アルゴリズムとデータ構造について基本的な概念を理解し，活用できることが目的である．

(1) 配列，リスト，スタック，木などの基本的なデータ構造を利用することができること．
(2) 各種ソートアルゴリズム，グラフに関する基本的なアルゴリズムについて説明できること．
(3) 計算量の概念について説明できること．

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

とくになし．

ディベート・ディスカッション　Debate/Discussion／プレゼンテーション　Presentation

-

次回の授業で何を扱うかについて，講義資料を参考に1時間程度予習しておくこと．
授業中に扱ったアルゴリズムや例などは2時間程度復習し，説明，活用できるレベルまで理解しておくこと．

なお，自習用として，会津大学のサイト Aizu Online Judge (AOJ)の学習コース
https://onlinejudge.u-aizu.ac.jp/courses/list

を利用することも薦める．

講義70%，演習の成績30%の割合で評価する．

• 講義70%の内訳は，到達度試験40%，授業レポート20%，授業中の演習10%．
• 演習30%の内訳は，小課題10回計20%，レポート10%．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

【参考書】

• 平田富夫，アルゴリズムとデータ構造（第3版），森北出版，2016.
• A.V. エイホ，J.E. ホップクロフト，J.D. ウルマン，アルゴリズムの設計と解析I，サイエンス社，1977.

【その他資料】

• 講義資料を毎回LETUSに掲載する．

第1回：アルゴリズムと計算量
アルゴリズムとは何か，アルゴリズムの計算量とは何かを理解する．

第2回：基本的なデータ構造(1)
基本的なデータ構造のうち，配列，リスト，スタック，待ち行列について理解する．

第3回：基本的なデータ構造(2)
木について理解する．

第4回：集合の表現法(1)
集合を計算機で表現する方法のうち，半順序の付いた2分木，2分探索木について理解する．

第5回：集合の表現法(2)
集合を計算機で表現する方法のうち，平衡木，ハッシュについて理解する．

第6回：ソート(1)
バブルソート，クイックソート，マージソートについて理解する．

第7回：ソート(2)
ヒープソート，バケットソート，基数ソートについて理解する．

第8回：グラフのアルゴリズム(1)
有向グラフに対する最短経路問題を解くダイクストラのアルゴリズム，フロイドのアルゴリズムについて理解する．

第9回：グラフのアルゴリズム(2)
有向グラフの探索アルゴリズム，強連結成分を求めるアルゴリズムについて理解する．

第10回：グラフのアルゴリズム(3)
無向グラフに対して最小木を求めるアルゴリズム，関節点を求めるアルゴリズムについて理解する．

第11回：文字列の検索
文章の中から特定の文字列を効率よく検索するアルゴリズムについて理解する．

第12回：行列と多項式の計算(1)
行列の積を高速に計算するシュトラッセンの行列乗算アルゴリズムについて理解する．

第13回：行列と多項式の計算(2)
離散フーリエ変換，高速フーリエ変換と，それを用いた多項式乗算アルゴリズムについて理解する．

第14回：アルゴリズムの設計法
アルゴリズムの設計法である分割統治法，動的計画法，欲張り法について理解する．

第15回：到達度の確認と解説
本科目の授業内容に関する到達度の確認と解説を行う．

関川：情報通信関係企業での研究員（数学，情報系）としての勤務実績を活かし，データ構造とアルゴリズムに関する講義を行う．

Mathematica

Python

Y

N