授業科目一覧
基盤科目
コース科目
卒業研究(全科履修生のみ)
夏季集中科目
メニューここまで

アルゴリズムとプログラミング('16)

※印刷用にはシラバスPDF版新規ウィンドウ をご利用ください
主任講師
鈴木 一史 (放送大学准教授)
放送メディア
ラジオ
放送時間(平成29年度)
第1学期:(水曜)16時45分~17時30分

講義概要

計算機科学における基礎的なアルゴリズムやプログラミングについて学習する。データ型、変数、条件文、分岐、繰り返し、関数、配列、構造体、ファイル、メモリ等の基本的な知識について学ぶ。データの探索やソーティングなどを例として、アルゴリズムの効率や計算量について考える。また、リスト構造を用いたスタックやキューといったデータ構造の実装について学習する。なお、プログラミングの学習にはC言語の例を用いる。
※詳しくはシラバス

開設年度
平成28年度
科目区分
コース科目(情報コース(専門科目))
〔2009年度~2015年度〕専門科目(情報コース)
〔2008年度以前〕専門科目(情報コース)
科目コード
1570161
単位数
2単位
単位認定試験
試験日・時限
平成28年度 第2学期:平成29年1月24日(火曜)3時限(11時35分~12時25分)
平成29年度 第1学期:平成29年7月26日(水曜)7時限(16時45分~17時35分)
単位認定試験
平均点
(平成28年度 第1学期)84.1点
 
備考
 
このページのトップへ本文ここまで

授業の目標

初歩的なプログラミング技術について学習する(C言語を利用)。
情報科学・計算機科学におけるソフトウェア作成の手続きを学習する。
基本的なアルゴリズム、データ構造、計算量などについて学習する。

履修上の留意点

※オペレーティングシステムやコンパイラのインストールができるコンピュータ知識や初歩的なC言語のプログラミング経験があることが望ましい。印刷教材の一部の応用的な演習課題解答例(C言語のコード等)は、Web補助教材に掲載するのでWebを閲覧できる環境があることが望ましい。
※「情報」に関連した基盤科目や導入科目、プログラミングを扱った面接授業等を先に受講することを勧める。
※関連科目としては、「データ構造とプログラミング('13)」(専門科目)等がある。

シラバス

テーマ 内容 執筆担当講師名
(所属・職名)
放送担当講師名
(所属・職名)
1 プログラミング アルゴリズムやプログラミングについて学習する。コンパイラによるソースコードから実行可能なターゲットプログラムへの変換の大まかな流れについて学習する。C言語を例として、簡単なデータの入力、データの出力、変数、式、コメント記述等の基礎的なプログラミングについて学ぶ。

【キーワード】
アルゴリズム、プログラミング言語、コンパイラ、インタプリタ、入力、出力、変数、式、コメント記述
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
2 条件分岐 条件分岐について学習する。条件分岐文では、設定した条件にしたがって実行するコードを変更することができる。C言語によるif文、if-else文、条件分岐に使われる比較演算子、switch文、条件演算子、goto文について学習する。

【キーワード】
条件分岐、if文、if-else文、比較演算子、switch文、条件演算子、goto文
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
3 ループの仕組み コンピュータは大量の繰り返しの計算を高速かつ正確にこなすことができる。プログラミングにおいて、何らかの命令を繰り返し実行する処理は非常に重要である。ループ(loop)はこのような計算を実行するために使われる。ループとは、ある条件が満たされるまで、繰り返し実行される一連の命令のことである。

【キーワード】
繰り返し、ループ、入れ子型ループ、無限ループ、for文、while文、do-while文、for文とwhile文の変換
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
4 ループの応用 ループを応用したプログラムの例として、モンテカルロ法による円周率πの計算シミュレーションについて学習する。また、アルゴリズムの動作に必要な資源の量を評価する計算量について考える。アルゴリズムの速度を比較するための方法として、ビッグ・オー記法について学習する。

【キーワード】
モンテカルロ法、円周率、計算量、時間計算量、空間計算量、ビッグ・オー記法、関数の増加率
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
5 関数 頻繁に使うコードは関数として1つのコードにまとめると繰り返し利用することが可能になり便利である。関数の“引数”と“戻り値”について学習し、“値渡し”と“参照渡し”の違いについて考える。さらに、関数などが自分自身を呼び出し実行する“再帰呼び出し”の概念について学ぶ。

【キーワード】
関数、スコープ、引数、戻り値、値渡し、参照渡し、再帰、終了条件
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
6 配列の仕組み 配列の仕組みについて学習する。配列の宣言、初期化、配列要素の読み出しや書き込みについて学ぶ。また、多次元配列の仕組みや多次元配列の応用的な使い方について学ぶ。さらにC言語における配列を利用した文字列の表現や文字列に関連する関数等の使い方を学習する。

【キーワード】
配列、添字、多次元配列、文字列、ヌル文字、構造体の配列、構造体のポインタ配列
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
7 配列の操作 配列に対する操作として、挿入、削除、探索などの基本的な操作を学習する。線形探索と順序配列を利用した二分探索の仕組みを学習し、それぞれ探索の特徴について学ぶ。また、C言語による線形探索と二分探索のプログラム実装について考える。

【キーワード】
配列、挿入、削除、探索、配列と関数、線形探索、順序配列、二分探索、計算量
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
8 配列の応用 配列を使った応用的なコード例を学習する。スタックとキューという基本的なデータ構造と操作について学習する。そして、C言語による配列を利用したスタックとキューの実装例について学ぶ。配列と関数を利用したコードの応用例として、コンウェイのライフゲームについて考える。

【キーワード】
配列、スタック、プッシュ、ポップ、キュー、エンキュー、デキュー、ライフゲーム
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
9 ファイル ファイルの読み込みや書き込みに関するコードについて学習する。ファイル内のデータ値を読み込んで計算を行うコードについて考える。簡単な画像データのファイル形式や仕組みについて学習する。画像ファイルのデータをメモリへ読み込んで、メモリ上でデータの処理を行った後に、処理したデータを画像ファイルへ書き出すコードについて学ぶ。

【キーワード】
ファイル、画像ファイル、画像フィルタリング、輪郭抽出、ラプラシアンフィルタ、ソーベルフィルタ
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
10 ソーティング バブルソート、選択ソート、挿入ソートなどの基本的なソーティングのアルゴリズムについて学び、これらのアルゴリズムのC言語によるコード例について学習する。また、これらのソーティングアルゴリズムの計算量や特徴について考える。

【キーワード】
整列、昇順、降順、バブルソート、選択ソート、挿入ソート、qsort関数、計算量
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
11 高速なソーティング 値の大小比較による高速なソーティング例として、クイックソートについて学習する。クイックソートは分割統治アルゴリズムであり、再帰プログラムで実現することができる。本章では、C言語によるクイックソートの実装について学ぶ。また、値の大小の比較によらないソーティングの例として、基数ソートについて学習する。

【キーワード】
クイックソート、分割統治、再帰、スタック、ビンソート、基数ソート
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
12 メモリ メモリはコンピュータプログラムにとって主要な資源の一つである。プログラムを作成するにあたって、メモリがプログラムでどのように利用できるか知っておくことは重要である。本章では、一般的なコンピュータにおけるプログラムのメモリレイアウトについて学習する。また、C言語における要素数の大きな配列の利用方法などについて考える。

【キーワード】
メモリ、プログラム内蔵式計算機、メモリレイアウト、セグメント、ガベージコレクション、スタックメモリ領域、ヒープメモリ領域
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
13 連結リスト 連結リストは基本的なデータ構造の一つである。本章では、連結リストのデータの挿入と削除といった主要な操作について学ぶ。また、データの探索、表示等の操作についても学習し、C言語による連結リストの実装について考える。そして、連結リストと配列を比較してその利点や問題点について考える。また、連結リストの操作に関する計算量について学習する。

【キーワード】
リスト、連結リスト、ノード、挿入、削除、探索、表示、計算量
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
14 連結リストの応用 連結リストを用いたスタックとキューのデータ構造の実装例について学習する。また、連結リスト(片方向連結リスト)の構造を拡張した、双方向連結リスト、環状連結リスト、環状双方向連結リスト等について学ぶ。そして、これらのリスト構造における利点や欠点、連結リストへのデータの挿入や削除の計算量について考える。

【キーワード】
連結リスト、スタックの実装、キューの実装、双方向連結リスト、環状連結リスト、双方向環状連結リスト、番兵、優先度付きキュー
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
15 アルゴリズム「ハフマン符号化法」 ソーティング等のアルゴリズムや基本的なデータ構造は、より複雑なアルゴリズムの中で利用されることがある。本章では、ハフマン符号化法の事例について学習する。ハフマン符号の実装には、ソーティングアルゴリズムや優先度付きキューなどのデータ構造が使われることが多い。本章では、ハフマン符号化のアルゴリズムを学習するとともに、接頭符号、ハフマンツリー、カノニカル・ハフマン符号の例についても学ぶ。

【キーワード】
符号化、ハフマン符号化法、カノニカル・ハフマン符号、接頭符号、ハフマンツリー
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
このページのトップへ本文ここまで
授業科目案内 教養学部 放送大学