情報処理IV

[ 上智大学の学部シラバス内の本授業のページ]

お知らせ

本授業は教室(コンピュータルームC)を仕切って前半分で行なう予定ですので、予め前半分に着席していて下さい。

第7回(11/18)までは角皆が、第8回(11/25)からは澁谷が主担当です。但し、担当者出張の為、第10回(12/9)は角皆が担当で1回読切の話をします。

レポート提出に際しての注意

メディアセンターの各自のアカウントから所定のメイルアドレスにメイルで送る。
Subject: に出題日を明記する。 (提出日ではない。提出されたレポートを整理する際に間違えられて未提出と思われても知りませんぞ。)
プログラムの先頭にコメントとして、学生番号・氏名・アカウント名を明記する。

履修予定者への注意

初回の授業には必ず出席すること。
初回の授業の時に総合メディアセンターのコンピュータルームのコンピュータが利用できる状態にあること。夏休み中に大幅な設定変更が行なわれたので、総合メディアセンター発行の「センターニュース」やメディアセンターのウェブサイトなどを参照して、変更点・利用上の注意事項を確認すること。
自分の password を忘れて利用できない者は、事前に総合メディアセンター事務室(2号館3階)にパスワード変更申請の手続きを行なって、授業の時には使える状態にしておくこと。

講義概要

計算機室での実習により、情報処理I～IIIで学んだ基礎事項を基に、様々なデータ構造やその実装を扱い、情報検索や計算など各処理に適した情報システムの設計を学ぶ。又、make によるプロジェクト管理やプログラムの共用・再活用など効率的なシステム開発手法に触れる。 C 言語で実際にプログラムを作るので、情報処理III程度のプログラミングの理解・習熟を要す。

講義計画

大体この順に進める予定。

C言語プログラミングの復習および基礎の確認
変数領域の動的確保(C 言語の文法事項の補足)
データ構造とは
種々のデータ構造(リスト・スタック・キュー・木など)
再帰呼出と帰納法
計算量について
種々のアルゴリズム(符号とその実装)
総合演習
分割コンパイル・make によるプロジェクト管理(補足)

主な参考書

「プログラミング言語C(第2版)」 B.W.Kernighan・D.M.Ritchie 著・石田晴久訳 (共立出版)
「アルゴリズムC(新版)」R.Sedgewick 著・野下浩平・佐藤創・星守・田口東訳(近代科学社)
「プログラミングに活かすデータ構造とアルゴリズムの基礎知識」今泉貴史(アスキー)
その他適宜。online manualを大いに活用されたい。文法書や例題の豊富な参考書も役立つであろう。

講義内容

10/7

配ったプリント [アンケート(pdf,16KB) |page 0～5(pdf,41KB) ] ・プロジェクタ資料 [10/7授業時(pdf,29KB) ]

前期の「情報処理III」では、C言語の文法の基礎を学び、「何をどう計算すれば良いか」が判ったらプログラムが書けるようになった、という前提で、この授業では、取組む問題に対して「何をどう計算すれば良いか」が判るようになることを目標とする。

C言語プログラミングの復習および基礎の確認。

データ構造とアルゴリズム(前振り)。メモリの動的確保。malloc。

課題: ベクトルの成分の個数を入力してから、その分だけのメモリ領域を確保することにより、無駄なくメモリを利用するようにした、ベクトル計算のプログラム (提出期限: 10/13)

10/14

配ったプリント [page 6～11(pdf,43KB) ] ・プロジェクタ資料 [10/14授業時(pdf,32KB) ]

前回の課題の解説と補足。データ構造とは。リスト構造について。リストの実装(1):リスト要素の型定義・新規作成・走査

課題: 実習3.1のプログラムで、リストの走査(表示)の部分を関数 print_list() として関数化したプログラム (提出期限: 10/20)

10/21

配ったプリント [page 12～17(pdf,47KB) ](誤記訂正済) ・プロジェクタ資料 [10/21授業時(pdf,83KB) ]

前回の課題の解説と補足。リストの実装(2):リスト要素の削除・挿入。 free()による領域解放。

課題: 入力した整数を値とする新節点を、リストの適切な場所に挿入して、作成したリストの各節点の値が大きさの順になるようなリストを作成することにより、次々と入力した整数値を大きさの順に並べ替えて表示するプログラム (提出期限: 11/3)

10/28

配ったプリント [page 18～23(pdf,44KB) ] ・プロジェクタ資料 [10/28授業時(pdf,108KB) ]

前回の課題の補足(ヒント)。リスト構造の補足(プッシュダウンスタック・FIFOキュー)。リストと配列との比較。木(tree)構造、特に二分木。二分木の実装。再帰呼出。

課題: 入力した整数を値とする新節点を適切な末端に追加して木を作成し、その木を走査することにより、次々と入力した整数値を大きさの順に並べ替えて表示するプログラム(二分探索木) (提出期限: 11/10)

11/4

配ったプリント [page 24～27(pdf,47KB) ] ・プロジェクタ資料 [11/4授業時(pdf,81KB) ]

前々回の課題の解説と補足。計算量について。木(tree)構造、特に二分木(続き)。例: 演算木(式木)。 Mathematicaを例に数式処理ソフトでの式の構造を見る。式の記法(前置・中置・後置)について。今回は新たな課題無し。

11/11

配ったプリント [page 28～29(pdf,22KB) ] ・プロジェクタ資料 [11/11授業時(pdf,104KB) ](誤記訂正済)

提出状況を鑑み、前々回(10/28)の課題の解説は延期。

演算木・式記法の補足。応用: 多項式の実装。多項式電卓を作ろう。

11/18

配ったプリント [page 30～35(pdf,45KB) ] ・プロジェクタ資料 [11/18授業時(pdf,29KB) ]

前々々回（10/28）の課題の解説と補足。応用: 多項式の実装。多項式電卓を作ろう。双方向リスト。

11/25

今回からアルゴリズムについて(担当: 澁谷)。情報源符号化の基礎とハフマン符号(1)。

12/2(予定)

情報源符号化の基礎とハフマン符号(2)。

12/9(予定)

分割コンパイル。ヘッダファイル。make によるプロジェクト管理。

12/16(予定)

逐次的な符号化とエライアス符号(1)。

1/6(予定)

逐次的な符号化とエライアス符号(2)。

1/13(予定)

算術符号(1)、または簡単なユニバーサル符号(1)。

1/20(予定)

算術符号(2)、または簡単なユニバーサル符号(2)。