%=====================================================================
% 秋田高専 2E 情報工学概論
% 
% last updated 2005.11.27
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float,misc}
\usepackage{html, listings, jlisting}
\oddsidemargin 0mm  %左の余白 25.4mm-0mm　奇数ページ
\evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ
\textwidth 160mm
%
\newcommand{\command}[1]{「\texttt{#1}」}
\newcommand{\tw}[1]{\texttt{#1}}
\renewcommand{\lstlistingname}{リスト}
\lstset{language=C,%
        basicstyle=\footnotesize,%
        commentstyle=\textit,%
        classoffset=1,%
        keywordstyle=\bfseries,%
	frame=tRBl,framesep=5pt,%
	showstringspaces=false,%
        numbers=left,stepnumber=1,numberstyle=\footnotesize%
	}%
%
\begin{htmlonly}
\usepackage{verbatimfiles}
 \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}}
\end{htmlonly}
%
\begin{document}
\title{これまでの復習(後期中間試験に向けて)}
\date{2005年11月28日}
\author{山本昌志\thanks{国立秋田工業高等専門学校　電気情報工学科}}
\maketitle
%
これまでの，学習をまとめる。後期中間試験には，このプリントに書いてある内容を理解
して臨むこと。授業内容の分かっていない者は，少なくとも10時間は集中して勉強するこ
と．どうしても理解できない場合は，成績の良い者に聞くなり，オフィスアワーを利用し
て，私に質問すること．
%=====================================================================
\section{アルゴリズムとデータ構造}
%=====================================================================
%---------------------------------------------------------------------
\subsection{アルゴリズム}
%---------------------------------------------------------------------
アルゴリズムは，問題を解くための手順を定めたものである．情報科学の分野では，コン
ピューターを使って問題を解く場合の手順のことをいう．プログラムは，その手順を表現
したものである．そのため，アルゴリズムでは曖昧なことは許されず，厳格に手順を決め
なくてはならない．そうしないと，プログラムは書けない．

問題を解く場合，いろいろなアルゴリズムが考えられるが，以下のようなものが良いアル
ゴリズムである．
\begin{itemize}
 \item 計算の早い方が良いアルゴリズムである．
 \item 使用するメモリーがすくない方が良いアルゴリズムである．
\end{itemize}
%---------------------------------------------------------------------
\subsection{データ構造}
%---------------------------------------------------------------------
データ構造(data structure)とは，データのメモリー上の表現方法のことを言う．諸君は，
これまでにいろいろなデータ構造を学習した．まずは，C言語で用意されている次のよう
なものである．
\begin{itemize}
 \item 単純型変数
 \item 配列
 \item 構造体
\end{itemize}

後期の授業では構造体を使ったリストと言われるデータ構造を学習した．これは重要であ
る．
%
%=====================================================================
\section{ソートのアルゴリズム}
%=====================================================================
ソートとは，データをある規則にしたがい順番に並び替えることである．ここでは，ラン
ダムに並んだ整数(数列)を昇順に並び替えることを学習した．
%
%---------------------------------------------------------------------
\subsection{バブルソート}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
数列の隣どうしの要素の大小を比較してそれらを交換しながらソートする方法である．交
換が1回も生じなかったら，ソートが完了である．これは，小さい値のデータが泡(バブル；
bubble)のように浮かんで行くように見える\footnote{昇順にソートする場合．}ことから
この名前がつけられた．

リスト\ref{prog:buble_sort}が配列\tw{sort}に格納された整数を昇順に並び替えるプロ
グラムである．このプログラムの動作を考えるために，データ数を\tw{N}として，
\tw{sort[0]}を左端，\tw{sort[N]}を右端とする．すると，以下のことが分かる．
\begin{itemize}
 \item もっとも値の大きいデータは，外側の1回のループ(5行目の\tw{do})で右端に移動する．
 \item 左に移動すべき小さいデータは，このループで一つずつしか移動できない．この一つず
       つしか移動できないので，整列に多くの計算回数が必要となる．
\end{itemize}

このプログラムでは，\tw{do}ループ中の11行目の
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	if(sort[i]>sort[i+1])
 \end{verbatim}
\end{quote}\vspace{-5mm}
%
がもっとも多く実行される文である．この文の最小実行回数は，最初から整列できている
場合である．このときの，実行回数は，$N-1$回であるのは明らかである．最悪の場合は，
最小の値が右端にある場合である．この場合の実行回数は，$(N-1)^2$となる．なぜなら
ば，
\begin{itemize}
 \item この最小の値は，1回外側のループ(\tw{do}文のところ)を実行する毎に，一つ左に移動する．
 \item 所定の位置に移動するために，$N-1$回，外側のループを実行する必要がある．
 \item 外側のループを1回実行する毎に，内側のループは$N-1$回，実行される．
\end{itemize}
となるからである．

最初のデータの並び方により，$N-1$回から$(N-1)^2$まで開きがある．初期位置と整列終
了位置との差の最大の期待値を計算することになるが，それは$(N-2)/2$程度であ
ることは分かるだろう．最小値の初期位置と整列終了位置との差の期待値である．この
程度とすると，先の比較の実行回数は，
\begin{align}
 \frac{(N-1)(N-2)}{2}=\frac{N^2}{2}-\frac{3}{2}N+1
\end{align}
となる．データ数$N$が大きい場合，$N^2$に比例して計算量が増加する．

この$N^2$に比例して計算量が必要な場合，$O(N^2)$と書く．この表記法を
\textbf{$O$記法}($O$-notation)といい，計算オーダーを示す．数学で使うランダウの記
号に似ている．バブルソートの計算のオーダーは，$O(N^2)$である．
%------------------------
\subsubsection{プログラム}
%------------------------
教科書のList 1-1(p.3-4)のバブルソートの関数は，リスト\ref{prog:buble_sort}の通り
である．これを\tw{main}関数から呼び出すことにより，配列\tw{sort}に格納された整数
が昇順に並び替えられる．
\begin{itemize}
 \item 配列\tw{sort}はグローバル変数\footnote{関数の外で宣言されたので，どの関数
       からでもアクセスできる．}なので，関数の引数として渡していない．
 \item 数列の個数\tw{N}は，\tw{\#define}で与えられる．
 \item 入れ替えが生じると，\tw{flag}の値が1になる．入れ替えが起きないときは，
       \tw{flag}の値は0である．これはフラグ(flag:旗)と呼ばれるもので，計算の状態
       を表す．
\end{itemize}
%
\lstinputlisting[caption=バブルソートの関数,label=prog:buble_sort]
{program/buble_sort.c}
%
%---------------------------------------------------------------------
\subsection{クイックソート}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
ある一つの要素を基準とし基準値より大きいグループと小さいグループに分ける．分けら
れたグループも同様の方法で分ける．全てのグループの要素が1つになるまでこの作業を
繰りかえし，このときソートが完了する．いろいろなソートの中で，平均的には最速であ
るから，この名前がついている．
%
%------------------------
\subsubsection{プログラム}
%------------------------
教科書のList 1-3(p.8-9)のクイックソートの関数は，リスト\ref{prog:quick_sort}の通り
である．これを\tw{main}関数から呼び出すことにより，配列\tw{data}に格納された整数
が昇順に並び替えられる．
\begin{itemize}
 \item 関数の引数は，ソートする配列の両端(\tw bottom, top)と配列を表すポインター
       (\tw{*data})である．
 \item 配列のポインター(\tw{*data})は，配列名として使える．
\end{itemize}
%
\lstinputlisting[caption=クイックソートの関数,label=prog:quick_sort]
{program/quick_sort.c}
%---------------------------------------------------------------------
\subsection{マージソート}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
最初に少ない個数の数列を並べ替えたグループを作る．次に，2つのグループを併合(マー
ジ)して，より大きな並び替えられたグループを作る．これを繰り返すことにより，大き
なグループができ，最終的には一つのグループになり並び替えが終了する．
%------------------------
\subsubsection{プログラム}
%------------------------
%
\lstinputlisting[caption=マージソートの関数,label=prog:merge_sort]
{program/merge_sort.c}
%---------------------------------------------------------------------
\subsection{コームソート}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
バブルソートは隣との比較のため，小さい値は一つずつしか移動できない(昇順)．比較す
る間隔を広くして，一気に移動させる方法がコームソートである．このソートでは，適当
な間隔でバブルソートを行い徐々にその間隔を狭める方法がとられる．実験から，間隔は
$1/1.3$ずつ小さくしていくのが良いと言われている．最終的には隣との比較(間隔が1)を
行い，交換が起こらなければソートの完了である．
%------------------------
\subsubsection{プログラム}
%------------------------
%
\lstinputlisting[caption=マージソートの関数,label=prog:comb_sort]
{program/comb_sort.c}
%
%---------------------------------------------------------------------
\subsection{単純挿入ソート}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
まず，最初の数列の2つを比較して，小さいほうを左に，大きいほうを右にする．次に数
列の3番目を，その左にある2つの数列と小さいほうから順に比較し，収まる位置を探索し
て，挿入する．これを，4番目,5番目，$\cdots$と順次，数列の最後まで繰り返す．最後
の数列が挿入されたらソートが完了である．
%------------------------
\subsubsection{プログラム}
%------------------------
%
\lstinputlisting[caption=単純挿入ソートの関数,label=prog:simple_sort]
{program/merge_sort.c}
%
%---------------------------------------------------------------------
\subsection{2分挿入ソート}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
単純挿入ソートでは，数列のある値を挿入する適当な位置は端から順に探している(リニ
アーサーチ)，位置を探す数列は並べ替えられているので，真中の値から比較するバイナ
リーサーチが可能で，それを適用して速度の向上を図った方法が，2分挿入ソートである．
%------------------------
\subsubsection{プログラム}
%------------------------
%
\lstinputlisting[caption=2分挿入ソートの関数,label=prog:binary_sort]
{program/binary_sort.c}
%
%---------------------------------------------------------------------
\subsection{ソートのアルゴリズムの比較}
%---------------------------------------------------------------------
ソートのアルゴリズムの評価に計算量の他に，安定性というものが使われる．
\begin{itemize}
 \item 安定なソートとは，同じ要素があったとき，それらを入れ替えない．
 \item 不安定なソートとは，同じ要素があったとき．それらを入れ替える可能性がある．
\end{itemize}

これら学習したソートの計算量と安定性については，表
\ref{table:sort_characteristic}(教科書の Table 1-2)のとおりである．

\begin{table}[H]
  \caption{ソートのアルゴリズムの特徴}
  \label{table:sort_characteristic}
  \begin{center}
    \begin{tabular}{lll}
      \hline
      \multicolumn{1}{c}{アルゴリズム} &
      \multicolumn{1}{c}{計算量オーダー} &
      \multicolumn{1}{c}{安定性} \\
      \hline \hline
      バブルソート & $O(N^2)$ & 安定 \\
      クイックソート &$O(N\log N)$ 〜$O(N^2)$ & 不安定 \\
      マージソート & $O(N\log N)$ & 安定 \\
      コームソート & $O(N\log N)$ & 不安定 \\
      単純挿入ソート & $O(N^2)$ & 安定 \\
      2分挿入ソート & $O(N^2)$ & 安定 \\
      \hline
    \end{tabular}
  \end{center}
\end{table}
%
%=====================================================================
\section{サーチのアルゴリズム}
%=====================================================================
サーチとは，
\begin{quote}
 文字どおりたくさんのデータの中から目的のデータ(キー)がどこにあるか(もしくは，あるかな
 いか)を調べる作業
\end{quote}
である．整数のデータが配列に格納されている場合について，目的のデータを探す方法を
学習した．
%
%---------------------------------------------------------------------
\subsection{リニアサーチ}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
目的のデータを端から順に探索する方法である．データがランダムに並んでいる場合，こ
の方法しかない．

このアルゴリズムの計算のオーダーは，$O(N)$である．なぜならば，端から探索していく
ため，データが一致するためには平均$N/2$回の比較が必要であるからである\footnote
{目的のデータが探索すべき列の中にある場合}．
%------------------------
\subsubsection{プログラム}
%------------------------
教科書のList 2-1(p.37-38)のリニアサーチの関数は，リスト
\ref{prog:linear_search}の通りである．これを\tw{main}関数から呼び出すことにより，
整数\tw{x}と一致する配列\tw{a}の添え字の番号が求められる．
\begin{itemize}
 \item \tw{x}が探索するデータである．
 \item 配列はポインターとして渡されている．\tw{main}関数の実引数の配列名は，ポイ
       ンターである．この関数では，\tw{main}関数の呼び出し側の配列は，\tw{a[]}
       という配列になる．
 \item \tw{num}がデータ数を表す．
 \item 目的のデータと一致するものが無かった場合，\tw{NOT\_DOUND}を返す．この値は，
       \tw{\#define}で置換されれる．
\end{itemize}
%
\lstinputlisting[caption=リニアサーチの関数,label=prog:linear_search]
{program/linear_search.c}
%
%---------------------------------------------------------------------
\subsection{番兵をつかったリニアサーチ}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
リスト\ref{prog:linear_search}の計算速度を上げるために，通常のリニアサーチでは番兵を
つかう．リスト\ref{prog:linear_search}では，1回のループで，
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	n<num&&a[n]!=x
 \end{verbatim}
\end{quote}\vspace{-5mm}
のように2回の比較(\tw{n<num}と\tw{a[n]!=x})を行っている．目的のデータ(キー)を配
列の最後に入れる(番兵)ことにより，\tw{n<num}の比較の計算を行わないで済むようにで
きる．こうすると配列の最後では，\tw{a[n]!=x]}が成立しなくなるので，ループから抜
けることになる．ループから抜けた後，キーと元々あった配列の最後の値と比較すればよ
いのである．

このようにすると，比較の数が半分になる．しかし，計算量のオーダーは$O(N)$と変わら
ないことに注意しよう．
%------------------------
\subsubsection{プログラム}
%------------------------
教科書のList 2-2(p.38-39)の番兵を用いたリニアサーチの関数は，リスト
\ref{prog:linear_sentinel_search}の通りである．引数は，先ほどの番兵を用いないリ
ニアサーチと同じ．
%
\lstinputlisting[caption=番兵をつかったリニアサーチの関数,label=prog:linear_sentinel_search]
{program/linear_sentinel_search.c}
%
%---------------------------------------------------------------------
\subsection{バイナリーサーチ}
%---------------------------------------------------------------------
%--------------------
\subsubsection{原理}
%--------------------
データの並びに規則性が無い場合，リニアサーチのように端から順に捜すしかない．しか
し，データの並びに規則性がある場合，その性質を利用できる．

たとえば，データが昇順に並んでいた場合，端から比較するのではなく，最初に真ん中に位置す
るデータと比較する．すると，サーチすべきデータの個数が1回の比較でに半分になる．同じこ
とを繰り返すと，比較すべき対象が$1/2$ずつ減少する．データの個数が多い場合，この
方法は劇的にサーチが早くなる．この方法をバイナリーサーチと言う．

リニアサーチだと，1回の比較で1個しかデータの候補が減らないのに，バイナリーサーチ
だと半分に減少させることができるのである．ただし，バイナリーサーチを使うために
は，データを予めソートしておく必要がある．サーチの回数が1回であれば，ソートの手
間を考えるとリニアサーチの方が良い．サーチの回数が増加すると，バイナリーサーチの
方が有利になる．

1回の計算，リスト\ref{prog:binary_search}の5〜15行のループで，検索する範囲は$1/2$にな
る．したがって，$\alpha$回のループでその範囲が1になれば計算が終了する．データの
個数を$N$として，式で表すと，
\begin{align}
 N\left(\frac{1}{2}\right)^{\alpha}=1
\end{align}
となる．これから，計算回数$\alpha$は，
\begin{align}
 \alpha=\log_2 N
\end{align}
と導き出せる\footnote{ここの計算は，
$\left(\frac{1}{2}\right)^{\alpha}=\frac{1}{N}\quad\Rightarrow\quad 2^{\alpha}=N
\quad\Rightarrow\quad \log_2 2^{\alpha}=\log_2 N \quad\Rightarrow\quad
\alpha\log_2 2=\log_2 N \quad\Rightarrow\quad \alpha=\log_2 N$}．バイナリーサーチの場合の計算量のオーダーは，$O(\log_2 N)$である．
%------------------------
\subsubsection{プログラム}
%------------------------
教科書のList 2-3(p.41-42)のバイナリーサーチの関数は，リスト
\ref{prog:binary_search}の通りである．これを\tw{main}関数から呼び出すことにより，
整数\tw{x}と一致する配列\tw{a}の添え字の番号が求められる．
\begin{itemize}
 \item 配列はポインターとして渡されている．\tw{main}関数の実引数の配列名は，ポイ
       ンターである．
 \item \tw{left}がデータが存在する左端で，\tw{right}が右端を表す．
 \item 目的のデータと一致するものが無かった場合，\tw{NOT\_DOUND}を返す．この値は，
       \tw{\#define}で置換されれる．
\end{itemize}
%
\lstinputlisting[caption=バイナリーサーチの関数,label=prog:binary_search]
{program/binary_search.c}
%
%=====================================================================
\section{リスト}
%=====================================================================
%---------------------------------------------------------------------
\subsection{原理}
%---------------------------------------------------------------------
リストは前後のデータのある位置をメモリーに入れることにより，データの列(ここでは
数列)を構成する．最初のデータの位置を元に，それから順にたどりすべてのデータをつ
なぎデータ列(数列)を構成する．この様子を図\ref{fig:list}に示す．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/list.eps}
  \caption{リスト}
  \label{fig:list}
 \end{center}
\end{figure}
%

このようにすると，ここのデータは順にアクセス(シーケンシャルアクセス)することにな
り，その速度は一般に遅い．一方，データの削除と挿入は，データの位置を記憶するポイ
ンターを変更するだけなので，高速になる．
%--------------------------------------------------------------------
\subsection{プログラム}
%--------------------------------------------------------------------
教科書のList 3-3(p.75-77)では，リスト\ref{prog:list}に示す構造体を用いてリストを
作っている．
\begin{itemize}
 \item \tw{*prev}が前のノードを示すポインターである．
 \item \tw{*next}が次のノードを示すポインターである．
 \item \tw{*data}がこのノードのデータである．
\end{itemize}
%
\lstinputlisting[caption=リストを表す構造体,label=prog:list]
{program/list.c}
%
%---------------------------------------------------------------------
\subsection{リストと配列の違い}
%---------------------------------------------------------------------
配列もリストも，複数のデータの値と順序を記憶するデータ構造である．しかし，その使
い方はかなり異なり，その性質をよく理解しなくてはならない．

配列は目的のデータにランダムアクセスが可能で，目的のデータの値を得たり，データの
値の変更が高速にできる．添え字を指定するだけで，それらが可能である．しかし，デー
タの削除と挿入には計算回数が多くなる．たとえば，10番目のデータを削除するとなると，
11番目を10番目に移動，12番目を11番目に移動，13番目を12番目に移動$\cdots$とデータ
を順次移動させる必要がある．

一方，リストは目的のデータにアクセスするためには，シーケンシャルアクセス
\footnote{データを先頭から順番に読み込み、あるいは書き込みを行なう方法。}を行う．
そのため，データへのアクセス回数が多くなり配列より低速になる．しかし，データの削
除と挿入は簡単で，その前後へのノードのポインターの値を変更するだけである．したがっ
て，挿入と削除は高速になる．

\begin{table}[H]
 \caption{配列とリストとの違い}
 \label{table:diff_list_array}
 \begin{center}
  \begin{tabular}{lll}
   \hline
   & 配列 & リスト \\
   \hline \hline
   データへのアクセス & 添え字によるランダムアクセス可能 & リストを順にたどる \\
   アクセスのための計算量 & $O(1)$ & $O(N)$ \\
   データの挿入/削除 & 計算コスト大 $O(N)$ & 計算コスト小 $O(1)$\\
   メモリーのコスト & 小 & 配列より大 \\
   \hline
  \end{tabular}
 \end{center}
\end{table}
%
%=====================================================================
\section{C言語プログラムテクニック}
%=====================================================================
教科書のList 3-2(p.72)では，C言語のプログラムでよく使われるメモリーの確保と配列
に関するテクニックが書かれている．また，List 3-4(p.75-77)では型定義という方法が
使われている．これらは重要なので，よく理解すること．
\begin{itemize}
 \item \tw{array=(int *)malloc(sizeof(int)*count);}\vspace{-3mm}
 \begin{quote}
  少々複雑に見えるが，処理される順に見ていけば簡単である．
  \begin{enumerate}
   \item 最初に\tw{sizeof(int)}が評価される．関数\tw{sizeof()}は，型のバイト数を
	 返す．ここでは，整数型\tw{int}のバイト数である4が返される．
   \item 次に，この4とデータ数である\tw{count}の乗算が行われる．この結果は，デー
	 タを格納するために必要なバイト数の計算になっている．
   \item \tw{malloc()}関数は，\textit{Memory ALLOCate}(記憶割付)の略で，引数で渡
	 されたバイト数のメモリーを確保して，その先頭のポインター(アドレス)を返す．
   \item \tw{(int *)}はキャストと呼ばれる強制型変換である．\tw{malloc}で返される
	 ポインターは強制的に整数型としている．従って，ポインターを+1加算すると，
	 アドレスは4つ進むことになる．
   \item 整数型のポインター(アドレス)を整数型のポインター\tw{array}に代入してい
	 る．
  \end{enumerate}
 \end{quote}
%
 \item \tw{free(array);}\vspace{-3mm}
       \begin{quote}
	関数\tw{free()}は，そのプログラムで使用しているメモリー領域を開放するた
	めにある．ここでは，\tw{malloc}で確保された領域を開放している．
       \end{quote}
%
  \item \tw{int *array}と\tw{array[n]}\vspace{-3mm}
       \begin{quote}
	ポインターで宣言しているものを配列として使っている．これは，配列がどのように処
	理されているか，考えればよく分かる．配列\tw{array[n]}は，\tw{*(array+n)}と評価
	される．すなわち，配列\tw{array[n]}は，ポインター\tw{array}に\tw{n}加算したポ
	インター(アドレス)が示す値と言うことである．このようなことから，配列で宣言して
	いなくても，配列のように使うことができるのである．
       \end{quote}
%
 \item \tw{typedef struct tagListNode\{} \\
       \hspace{3em}\tw{struct tagListNode *prev;}\\
       \hspace{3em}\tw{struct tagListNode *next;}\\
       \hspace{3em}\tw{int data;}\\
       \tw{\} ListNode;}\vspace{-3mm}
       \begin{quote}
	これは，\textit{TYPE DEFine}(型定義)と呼ばれるもので，型に別名をつける役割があ
	る．ここでは，\tw{struct tagListNode}と言う型を，\tw{ListNode}という別名
	で使える．このことにより，宣言が簡単になる．
       \end{quote}
%
 \item \tw{lastnode=NULL}\vspace{-3mm}
       \begin{quote}
	これは，ヌルポインター，あるいは空ポインターと呼ばれるものである．これは，
	\tw{lastnode}が何も指し示していないことを保証するために，使っている．
       \end{quote}
%
 \item \tw{newnode->data=buf;}\vspace{-3mm}
       \begin{quote}
	\tw{newnode}はポインターである．ポインターが指し示す構造体のメンバーにアクセス
	する場合，アロー演算子(\tw{->})を使う．ここでは，ポインター\tw{newnode}が示す
	構造体のメンバー\tw{data}に\tw{buf}の値を代入している．ポインターではなく，普
	通の変数となっている構造体の場合，そのメンバーにアクセスするにはドット演算子
	(\tw{.})を使う．
       \end{quote}
\end{itemize}
%=====================================================================
\section{合格点を取るためには}
%=====================================================================
\begin{itemize}
 \item ここで学習したアルゴリズムを用いて，10個程度の整数がソートできること．
 \item 少なくても，バブルソートとクイックソートのプログラムを理解すること．
 \item 計算量を示す\textbf{$O$記表}を理解すること．バブルソートとバイナリーサー
       チの計算量のオーダーについて，説明できること．
 \item リニアサーチとバイナリーサーチのプログラムが理解できること．
 \item リニアサーチにおける番兵の役割とそれを実現するプログラムを理解すること．
 \item リストを作成するための構造体がか書けること．
 \item リストと配列の違いが理解できること．
 \item ここで学習したC言語のプログラムテクニックが理解できること．
\end{itemize}
%=====================================================================
\end{document}