| 科目名 |
アルゴリズムとデータ構造 |
| クラス |
－ |
| 授業の概要 |
数学の問題には、その問題の解き方はわかったとしても、現実的な時間の範囲内で解けるとは限らない問題が多く存在する。例えば、巨大な合成数の素因数分解も、2 から順に割って行けば、原理的には可能ではあるが、とてつもなく時間がかかることがある。このように、問題の解き方と、その計算時間との関係は、数学の問題だけではなく、プログラムを書く上でも重要であり、本授業では、各種アルゴリズムを提示し、その計算量についての講義と、そのアルゴリズムを用いたプログラム作成の演習を行う。 |
| 授業の到達目標 |
本授業では、情報免許科目『コンピュータと情報処理II』で使用したテキストと同じテキストを用いる。『コンピュータと情報処理II』では、テキストの 1 ～ 9 章に関して取り扱ったが、Ｃ言語によるプログラミングにおいて重要なポインタの扱い方やデータ構造の構築に関する講義や演習ができなかった。そこで、最初の５コマで、このような内容に関する講義・演習をした上で、ソート，サーチ，数値計算で用いられる、アルゴリズムとデータ構造について、その方法と計算量の講義・演習を行う。この授業は、各種アルゴリズムとデータ構造を理解し、あるアルゴリズムが与えられれば、そのアルゴリズムの時間的・空間的複雑さを正確に評価できることを、最低ラインの目標とする。 |
| 授業計画 |
以下の内容の講義と演習を行う。
| 回 |
内容 |
| 1 | 授業全体のオリエンテーション
Ｃ言語の応用 (1) ポインタ |
| 2 | Ｃ言語の応用 (2) ポインタ |
| 3 | Ｃ言語の応用 (3) ポインタ |
| 4 | Ｃ言語の応用 (4) 構造体 |
| 5 | Ｃ言語の応用 (5) データ構造の構築 |
| 6 | アルゴリズムとデータ構造とは
ソート・アルゴリズムと、その計算量 (1) |
| 7 | ソート・アルゴリズムと、その計算量 (2) |
| 8 | ソート・アルゴリズムと、その計算量 (3) |
| 9 | ソート・アルゴリズムと、その計算量 (4) |
| 10 | サーチ・アルゴリズムと、その計算量 (1) |
| 11 | サーチ・アルゴリズムと、その計算量 (2) |
| 12 | 数値計算と、その計算量 (1) |
| 13 | 数値計算と、その計算量 (2) |
| 14 | 各種データ構造 (1) |
| 15 | 各種データ構造 (2) |
|
| テキスト・参考書 |
テキスト： 新版 明解Ｃ言語 入門編，柴田望洋著，ソフトバンクパブリッシング
このテキストは、情報免許科目『コンピュータと情報処理Ⅱ』で使用したテキストと同じテキストである。 |
| 自学自習についての情報 |
授業で学習した、アルゴリズムやデータ構造を定着させるには、授業で課す小レポートや最終課題のレポートに真剣に取り組むことが不可欠である。自宅にあるパソコンで利用できる、フリーのＣ言語のコンパイラに関する情報は、授業中に提供するので、プログラミングの練習に活用して欲しい。 |
| 授業の形式 |
授業はすべて情報処理センターで行い、ある程度講義が進むたびに、演習を行う。 |
| 評価の方法（評価の配点比率と評価の要点） |
(1) 小レポート (40%)
(2) 最終課題のレポート (60%)
１． (1) 小レポートとは、3 コマに 1 回のペースで、プログラムとその実行結果を提出するものである。
２．人のプログラムをコピーして提出したことが明らかになった場合は、レポート点は 0 点とする。
３．プログラミング技術は、一つずつ積み上げるようにして習得すべきものであるので、すべての授業に出席することが望ましい。やむを得ない事情で欠席した場合は、その欠席した授業で行われたことを自習しておくこと。 |
| その他 |
本授業を履修する前に、情報免許科目『コンピュータと情報処理II』を履修しておくことが望ましい。履修していない受講生は、指定したテキストの 1 ～ 9 章を事前に読んでおくこと。 |