アルゴリズム -プログラミングの前に「アルゴリズム＋データ構造」-
| 単位数 | ナンバリングコード |
|---|---|
| 2 | DIF306 |
|
|
|
| 教員名 | 穴田 有一 |
|---|---|
| 専門 | ソフトマター物理学（高分子固体物理学） |
| 出身校等 | 北海道大学工学部応用物理学科卒業，北海道大学大学院工学研究科応用物理学専攻修士課程修了，北海道大学大学院工学研究科応用物理学専攻博士後期課程単位取得退学，工学博士 |
| 現職 | 北海道情報大学教授 |
| 授業形態 |
|---|
| 前期印刷授業・後期印刷授業・前期面接授業・夏期面接授業 |
| 授業範囲 |
|---|
| 教科書の第1章から第4章まで |
| 試験範囲 |
|---|
| 上の「授業の範囲」に記載した範囲から出題します。
ただし、教科書の〔参考〕は除きます。「学習用プリント集」は必要に応じて参照してください。 （持ち込み許可物）インターネット試験は一切自由。面接授業は自筆ノート（印刷物の貼付不可） （試験に関する注意事項）印刷授業の科目試験は、インターネット試験で実施します。 |
| 科目の概要 |
|---|
| 問題を解く手順を記述したものをアルゴリズムといいます。そして、アルゴリズムをプログラミング言語で表現したものをプログラムといいます。しかし、アルゴリズムだけでプログラムをつくることはできません。扱うデータの表現を変えると、アルゴリズムも変えざるを得ません。データの表現はデータ構造と呼ばれますが、データ構造はアルゴリズムと同様にプログラムの性能を決定する重要な要素です。すなわち、Wirthの名言にあるように、『アルゴリズム＋データ構造＝プログラム』なのです。どのようなデータ構造を採用しどんなアルゴリズムを選ぶかで計算の速さが変わります。 |
| 授業における学修の到達目標 |
|---|
| これまでに多くのデータ構造とアルゴリズムが開発されています。この科目では、これらを学ぶことによって、問題に適したアルゴリズムとデータ構造を選択する能力を身に付けることを目標とします。 |
| 講義の方針・計画 |
|---|
| 「授業範囲」に列挙したアルゴリズムとデータ構造について学習してください。これまでに開発されている主要なアルゴリズムとデータ構造をよく理解するためには、これらをプログラムで表現することも必要です。この科目では、アルゴリズムの具体的な表現法として、現在広く普及しているC言語を用います。また、アルゴリズムの性能は計算量で評価します。テキストでは計算量についても詳しく解説されています。個々のアルゴリズムの計算量についても学習してください。テキストには問題が掲載されていませんが、「学習用プリント集」に問題を掲載しましたので、学習の参考にしてください。なお、試験には自筆のノートだけ持ち込みを認めます。普段からノートを作って学習してください。
第1回：（教科書第1章）アルゴリズムとデータ構造の基本 第2回：（教科書第2章）データ構造―配列 第3回：（教科書第2章）データ構造―連結リストの作り方 第4回：（教科書第2章）データ構造―連結リストを使った基本操作 第5回：（教科書第2章）データ構造―スタックとキュー 第6回：（教科書第2章）データ構造―木構造（木の基本） 第7回：（教科書第2章）データ構造―木構造（木の走査） 第8回：（教科書第3章）探索―2分探索木 第9回：（教科書第3章）探索―2分探索法 第10回：（教科書第3章）探索―ハッシュ法 第11回：（教科書第4章）整列―単純な整列アルゴリズム 第12回：（教科書第4章）整列―シェルソート 第13回：（教科書第4章）整列―ヒープソート 第14回：（教科書第4章）整列―クイックソート 第15回：（教科書第4章）整列―マージソート |
| 準備学習 |
|---|
| 印刷授業は、教科書や学習用プリントなどを基に自学自習で学習を進めますが、授業範囲の内容の他に、教科書の内容全体を2単位で90時間かけて学習することを目安としています。
わからない用語や内容は、参考文献等で検索することが準備学習として必要になります。 面接授業において、以下の準備学習を行う。 （予習）聴講前に、教科書の該当箇所に目を通してください。 （復習）聴講後に、教科書の該当箇所を読んで、確認してください。 |
| 課題(試験やレポート等)に対するフィードバック方法 |
|---|
| 印刷授業は、提出されたレポートについて講評を付与して返却する。
|
| 成績評価の方法およびその基準 |
|---|
| 試験：100％
ただし、対面のスクーリングでは、授業中の演習問題などを平常点として加味して評価します。 |
| 教科書 |
|---|
| 書 名：基礎から学ぶデータ構造とアルゴリズム（初版）
著者名：穴田有一・林 雄二 発行所：共立出版 ISBN：9784320122437 |
| 参考書 |
|---|
| 参考書籍を一つだけ挙げておきます。各自の判断で、必要ならば参考にしてください。なお、他にも多くの書籍が市販されているので、適当なものを参考にしてもよいでしょう。
書 名：アルゴリズムC第1巻―基礎・整列（初版） アルゴリズムC第2巻―探索・文字列・計算幾何（初版） 著者名：R.セジウィック（野下浩平他訳） 発行所：近代科学社 |
| その他 |
|---|
| 計画的にノートを作りながら学習してください。一夜漬けで試験に臨んでも、合格は難しいと思います。 |
| 試験期間 |
|---|
| シラバス検索画面トップページ（https://syllabus-tsushin.do-johodai.ac.jp/）下部の「2022科目試験時間割」を参照 |
| 学習プリント |
|---|
| あり |
| 教職科目 |
|---|
| 情報５の１（選択） |
| 関連受講科目 |
|---|
| なし |
| 担当教員の実務経験 |
|---|
| 1981年から1982年にかけて、石油化学企業に勤務し、4ヶ月間の工場実習を経て研究所に配属され、プロジェクトチームのメンバーとして合成樹脂材料の研究開発に従事しました。2つの開発テーマを与えられましたが、その内の一つ、自動車部品メーカーに販売することを目的としたゴム状の合成樹脂材料の開発では、ガラス面での低摩擦力を実現するために、物理学研究の基本的方法論にもとづく独自の分析方法を考案し、様々な摩擦係数をもつ材料を容易に成形するための材料組成をつきとめました。この研究については、プロジェクトリーダーの主任研究員および部門主管からも高評価を得て、プロジェクトの進行に寄与しました。
この実務経験から学んだことは、学問の基礎を修得することが実務上でも有益であること、そして、研究開発を進めるためには、プロジェクトチームの一員として協調しながらも、独自の考えを持つことが重要であり、口先だけで無く、その考えに基づく実績を作ることで、チームと協調しながらプロジェクトの前進に寄与することができるということです。 本学の担当科目では、この経験に基づいて、基礎知識と学問の方法論を学習することの重要性を伝えるとともに、その基礎に裏付けられた自分の考えもち、他者とコミュニケーションを十分にとりながら協調することの重要性を伝えています。 |