2007年12月5日水曜日

計算機言語II:第9回

  • 実施日:2007-12-05(水)2限
  • 講義内容:パッケージ、アクセス制御、情報隠蔽
  • 講義ノート(配布したものを、実際の講義内容を反映するように修正しています)
この講義では「情報を隠す」と題して、変数や関数、クラス、メンバ等を隠す機能について説明をしました。講義の最初に述べたように、情報を隠す機能自体はC言語にも備わっています。Java、あるいはオブジェクト指向言語で特に「情報隠蔽」が強調されることがありますが、それは、Cに比べて強力な機能が提供されているからだと言えます。

個々の機能(public, private, protected)については、必要になったときに調べていただく、ということで構いません。むしろ、講義の最後に示した例、つまり、メンバをpublicからprivateにすることで、プログラムコードがどう変化し、どのような利点をもたらすのか、その点を理解してほしいと思います。

計算機言語I:第8回

  • 実施日:2007-12-03(月)5限
  • 講義内容:局所変数
  • 講義ノート

情報システム論:第8回

  • 実施日:2007-12-03(月)2限
  • 講義内容:迷惑メールの対策、ウイルス
  • 講義ノート(前回のものと同じ)

計算機言語I:第7回

  • 実施日:2007-11-26(月)5限
  • 講義内容:パターン(照合の仕組など)
  • 講義ノート(前回と同じもの)

情報システム論:第7回

  • 実施日:2007-11-26(月)2限
  • 講義内容:迷惑メール
  • 講義ノート(前回のものと同じ)

計算機言語II:第8回

  • 実施日:2007-11-21(水)3限
  • 内容:インタフェース
  • 講義ノート(前回配布のものを使用)

2007年11月19日月曜日

情報システム論:第6回

  • 実施日:2007-11-19(月)2限
  • 内容:メール(1)
  • 講義ノート(途中まで)

計算機言語I:第6回

計算機言語II:第7回

情報システム論:第5回

  • 実施日:2007-11-12(月)2限
  • 内容:WWW(2)
  • 講義ノート(前回のものと同じ)

2007年11月7日水曜日

計算機言語II:第6回

2007年11月5日月曜日

計算機言語I:第5回

情報システム論:第4回

  • 実施日:2007-11-05(月)2限
  • 講義内容:WWW(歴史、仕組、サーバとクライアント)
  • 講義ノート(「WWWの仕組み」の途中まで)

2007年10月31日水曜日

計算機言語II:第5回

  • 実施日:2007-10-31(水)3限
  • 講義内容:クラスフィールド・クラスメソッド、配列
  • 配布資料(クラスフィールド・クラスメソッドは前回の資料を使用)
詳細は後で追記する予定

2007年10月29日月曜日

計算機言語I:第4回

(内容は後で追記します)

計算機言語II:第4回

  • 実施日:2007-10-24(水)3限
  • 講義内容:メモリ上でのオブジェクト、簡単なクラスの実装
  • 講義ノート1(前回公開済)、講義ノート2
(内容は後で追記します)

計算機言語I:第3回

(内容は後で追記します)

情報システム論:第3回

  • 実施日:2007-10-22(月)2限
  • 内容:インターネットの標準語・TCP/IP、IPアドレス
  • 講義ノート
(内容は後で追記します)

2007年10月17日水曜日

計算機言語II:第3回

  • 実施日:2007-10-17(水)3限
  • 講義内容:文字列(Stringクラス)
  • 講義ノート
この講義では、Javaにおけるクラスの典型例として、文字列を表すStringクラスを取り上げ、その使い方、内部の実装の一部について説明しました。これを通して、クラスというもののイメージをつかんでもらうのが目的です。

この講義でのポイントを整理しておきましょう。
  • クラスの記述(宣言)はフィールド(変数)とメソッド(関数)とから構成されている
  • クラスに属する値をオブジェクトと呼ぶ。オブジェクトは実行時にメモリ領域の割り付け+初期化を行うことで動的に生成される
  • オブジェクトの生成は、コンストラクタという特別なメソッドを呼び出すことで行われる。クラス宣言中では、コンストラクタはクラス名と同名で、返り値の宣言がないメソッドの形をしている
  • メソッド呼び出しは、構造体のメンバアクセスと同様、ドット演算子を用いて記述される
実行時のメモリ領域割り付けということから想像できる通り、オブジェクトとメモリアドレス参照(Cでのポインタ参照)とは大きな関わりがあります。来週は、今週の続きとして、この辺りから話をしていく予定です。

2007年10月15日月曜日

計算機言語I:第2回

  • 実施日:2007-10-15(月)5限
  • 講義内容:MLの式、型
  • 講義ノート
今回からMLの文法について説明を始めました。MLでプログラムを書き始めるのに必要な文法知識は、Cほど多くありません。今日の講義で説明した各種演算子に加え、次回以降で説明する組、リスト、関数の説明を行えば、一通りのプログラムは書けるようになります。

今回の講義では、MLとCとの文法の違いに重点を置いて説明しました。比較的簡単な内容の講義だったと思いますが、後の内容の基盤になりますので、整理のつもりで練習問題を解いてみて下さい。次回の講義の冒頭に解答例を示します。

情報システム論:第2回

  • 実施日:2007-10-15(月)2限
  • 講義内容:通信、ネットワーク、インターネット
  • 講義ノート
本講義の主題であるインターネットについて説明を始めました。今日はまず、この分野でよく使われる「通信」「ネットワーク」という用語の意味を整理し、それを基にインターネットとは何か、その歴史、インターネット接続の種類などについて説明しました。ポイントを簡単にまとめると、次のようになります。
  • 機器同士の「会話」が通信であり、「会話」のやり方をプロトコルという
  • ネットワークは、互いに通信できる機器が複数接続された「網」
  • LANとWANの違い、インターネット=inter(相互の)+net(ネットワーク)
講義中に少しだけ触れましたが、インターネットは単にパソコンなどの機器が接続されたネットワークではありません。繋がり方に制限があります。次回はその辺から話をしていく予定です。

計算機言語II:第2回

この講義では、Java言語の文法のうちメソッド内部に関する部分について説明を行いました。メソッドはC言語の関数に似ており、Javaでは文法もC言語に非常に似ています。そのため、上の講義ノートでは一通りまとめてありますが、講義ではC言語との違いについてのみ重点的に説明しました。主な違いは次のようになります。
  • 基本型(byte, booleanなどが新設。型の意味がアーキテクチャ非依存)
  • 条件式の型がboolean
  • for文におけるループ変数の宣言方法、その有効範囲
次週では、この講義で少しだけ登場した、文字列を表すクラスStringを題材にして、クラスとはどのようなものかについて話を始める予定です。

2007年10月5日金曜日

計算機言語II:第1回

今回は第1回目ということで、講義の概要を説明した後、この講義で取り上げるプログラミング言語Javaの特徴、動かし方などについてお話しました。Javaに代表されるオブジェクト指向プログラミング言語は、現代のプログラム開発において幅広く使われています。しかし、皆さんはこれまでCに代表される手続き型言語を学んでいますので、その点から言えば、発想の転換(手続き中心のプログラム開発からデータ中心のプログラム開発)が必要となり、馴染むまで少々苦労するように思われます。この講義では、Javaの全貌を紹介する(これは時間的に不可能です!)よりも、オブジェクト指向プログラミングとはどのようなものか、ご紹介することを中心にしたいと考えています。

上でも述べた通り、Javaの全貌を講義中にご紹介するのは時間的に不可能です。プリント等で可能な限り補足はしますが、それとは別に、各自で1冊、Javaの解説書を購入し、講義と並行して利用することを強くお進めします。Javaの解説書はたくさん出版されていますので、どれか自分に合いそうなものを選んでください。適切な本を選べるようになることも、社会に出る前の練習だと思ってください。

2007年10月1日月曜日

計算機言語I:第1回

  • 2007-10-01(月)5限
  • 講義内容:導入、プログラミング言語MLの概要、この講義の狙い
  • 講義ノート
第1回目の講義ということで、この講義の狙いを中心に、概要をお話しました。

この講義の中心は、Standard MLというプログラミング言語の紹介、そして、Standard ML を道具として再帰アルゴリズムを理解することです。Standard MLはCに比べて文法が習得しやすく、再帰やリスト、木、二分木などを理解するのに適しています。Cが苦手だと言う人も、リセットのつもりで取り組んでもらえればと思います。また、型推論、高階関数、多態など、プログラミング言語に関する研究の成果がいろいろ盛り込まれた言語であり、プログラミングが得意な人でも興味深い話がいろいろ出てくるのではないかと思います。

個人的な経験や認識から言えば、再帰は、プログラムが書けるようになるかどうかの大きな関門の一つです。アルゴリズムそのものも重要ですが、これを理解できると、プログラムを書く上でのある種のエッセンスが得られると思っています。この半期、実験IIとともに、皆さんとは、再帰を通して接する機会が増えます。是非、この半期で再帰を理解して頂ければと思います。

情報システム論:第1回

  • 2007-10-01(月)2限
  • 講義内容:導入、情報システムとは、情報システムとインターネットとの関わり
  • 講義ノート
第1回の講義ということで、この講義の概要をお話しました。講義中でお話しした通り、情報システム一般について論じても皆さんにとって面白いか疑問がありますので、現代の情報システムに欠かせない技術であるインターネットについてお話していこうと思っています。ただし、単なるインターネットの使い方ではなく、基盤技術にまで踏み込んで話をします。また、その基盤技術の話を基にして、セキュリティについてもお話していく予定です。

講義の最後でも述べましたが、インターネットの技術は進歩が早く、皆さんが社会に出るときには、この講義の話はもう古くなっているかもしれません。インターネットを使うには、そしてインターネットで身を守るには、ある程度技術を知っている必要があります。それと同時に、普段から、日々のニュースや記事などの中からインターネットに関するものに気を留めて注意しておく必要があります。その訓練という意味で、この半年間、インターネットに関するニュース、記事、本、出来事などに注意しておいて、自分が興味を持ったものを記録しておいて下さい。

それでは、半年の間ですが、よろしくお願いします。

2007年9月28日金曜日

開講通知:計算機言語II

  • 10/3(水)3限、8105教室
  • 講義内容:プログラミング言語Java、オブジェクト指向プログラミング
公開可能な資料はWWWで公開することを考えている。詳細は第1回目の講義の際、通知する。

開講通知:計算機言語I

  • 10/1(月)5限、8105教室
  • 講義内容:プログラミング言語ML、再帰プログラム
公開可能な資料はWWWで公開することを考えている。詳細は第1回目の講義の際、通知する。

開講通知:情報システム論(山陽学園大学)

  • 10/1(月)2限
  • 講義内容:インターネットの基盤技術と現状について
  • 講義WWWページ

2007年8月3日金曜日

岡山理科大学「データベース」定期試験結果

以下の方が合格です。

I05G012, I05G019, I05G042, I05G043, I05G046, I05G057, I05G066, I05G072, I05G076, I05G083

2007-08-04追記:試験問題の解答・解説を作成しました。参考にして下さい。

2007年7月20日金曜日

岡山理科大学「データベース」定期試験

  • 実施日: 2007-08-02(木) 7・8限時間枠
  • 試験範囲: 第1回〜第13回(表の設計)まで
  • ノート、配布資料持ち込み可。WWWで公開している資料のプリントアウトも可。参考書の持ち込みは認めないが、参考書を自分で要約してまとめた資料を持ち込むのは差し支えない。
  • 素点をベースに成績をつける。その際、出席点を加味する。

岡山理科大学「データベース」第14回

  • 実施日: 2007-07-19(木) 7・8限
  • 内容: トランザクション、インデックス
  • 講義ノート
今回は講義の最後ということで、残った話題の中から、データベースを使う上で比較的目にする機会の多い用語である「トランザクション」「インデックス」について説明しました。いずれも、データベースの特徴である「複数のユーザが同時に利用する」「大量のデータを扱う」ということから生まれてきた考え方です。

これまで扱ってきた「表」とは異なり、これらはいずれもデータベースシステム内部の仕組みに密接に関連しています。その意味で、この講義の主旨とはやや外れるテーマです。ですが、SQLを通してデータベースを使う、というだけであっても、トランザクションやインデックスを意識しなければならない場合もあります。そこで、この講義では、大体どのような概念なのか、なぜ必要なのか、を中心にお話を進めました。より詳細に知りたい方は、データベースに関する書籍などを参照して下さい。

これで今年度の「データベース」の講義は終わりです。皆さんが将来、データベースに関わる必要が出てきたときに、この講義の内容が役に立てば幸いです。

2007年7月19日木曜日

「コンパイラ」定期試験結果

以下は合格である。
  • 21170xxのうち、xxが以下の者:01, 03, 04, 05, 08, 11, 12, 13, 15, 17, 18, 19, 22, 23, 24, 25, 27, 28, 33, 34, 35, 38, 40, 41, 44, 46, 47, 49, 55, 57, 58, 59, 61, 62
  • 2115027, 2115045
  • 2116010, 2116020, 216022, 2116048, 2116058
以下は、追加判定により合格(C判定)となる可能性がある。追加判定を希望する場合は、課題を2610まで取りにくること。
  • 21170xxのうち、xxが以下の者:02, 14, 21, 29, 32, 39, 42, 43, 48, 50, 52
  • 2115001, 2115004
  • 2116046, 2116051

2007年7月13日金曜日

フレッシュマンセミナー

一応記録だけつけておこう。
  • 実施日: 2007-06-29(水) 2限
  • 内容: 高校数学から情報科学・情報数学への橋渡し
毎年あまり内容を変えてないので、手の内を明かさないということで、資料は置いていません。あしからず。

岡山県立大学「データベース」定期試験

  • 実施日: 2007-07-20(金) 2限
  • 場所: 8105
  • 試験範囲: 6/29講義分(第10回)の内容まで
  • ノート持ち込み可
  • 評価方法: 定期試験の素点で評価する。ただし、場合によっては、レポート課題等により追加判定を行うことがある。合格者、追加判定対象者は掲示するので、注意しておくこと。(ブログにも掲載する予定である)

岡山県立大学「データベース」第12回

  • 実施日: 2007-07-13(金) 2限
  • 内容: データベース技術の応用(情報システム、Web)
  • 講義ノート
今日の講義は最終回ということで、情報システムやWebとデータベース技術の関わりについてお話しました。

もともとデータベースは、情報システムの基盤技術として広く使われていました。情報システムで最も良く使われるシステムアーキテクチャはサーバ・クライアント型ですが、これがデータベース管理システムと合っているのが一つの理由だと思われます。この状況は今も変わっていません。

一方で、インターネット、とりわけWebの広がりにより、従来のデータベース技術ではカバーし切れないデータ管理手法が求められるようになりました。特にWeb検索では、Webページというスキーマのないデータを、大量かつ高速に処理しなければならないということで、クローリング(Webページ収集)、ランキング(ページの重要度を計算し、それにより検索結果の並べ替えを行う)など、新しいデータ管理手法がいろいろ提案され、現在も活発に研究が行われています。今回はその一端をご紹介するということで、PageRankというランキング手法を中心にお話しました。これはGoogleで実際に使われる(と言われている)手法で、グラフ理論を基に、ページ間のリンク構造だけで重要度を計算するものです。現在研究が盛んに行われている分野ということで、あまり体系だったお話ができないのですが、今の技術進歩の一端を感じ取ってもらえると幸いです。

2007年7月12日木曜日

岡山理科大学「データベース」第13回

  • 実施日: 2007-07-12(木) 7・8限
  • 内容: 表の設計(2) (第3正規形、実体・関連と正規形)
  • 講義ノート
今回の講義では、表の設計についてお話しました。前回の続きになります。

前回お話した第2正規形によって、更新時の不整合をかなり回避することができました。しかし、第2正規形でもまだ更新不整合を完全に取り除くことはできません。今回はまず、第2正規形で発生する更新不整合についていくつか例を出した後、これを回避する方法として、推移的関数従属性という考え方をお話しました。これを解消するように表を分割すると、第2正規形の更新不整合を回避することができます。このようにして得られた表を「第3正規形」と言います。この分割は、外部キー制約に着目したことになっています。

実のところ、第3正規形でもやはり更新不整合が発生することがあり、その回避のために、ボイス・コッド正規形、第4正規形、第5正規形など、さまざまな正規形が提案されています。ただ、実用上は第3正規形まで知っておけば充分だと思われますし、講義の後半で述べたように、実体・関連に着目した表の設計は、第3正規形までの手法と密接に関わりがあります。そのため、この講義では、第3正規形で話をとどめておくことにします。

次回は、この講義の最後として、インデックス(索引)、トランザクションという2つの用語について、簡単に説明を行います。

2007年7月11日水曜日

「コンパイラ」定期試験

  • 実施日: 2007-07-18(水)1限(8:40〜10:10)
  • 場所: 8105講義室
  • 配布資料、ノート持ち込み可。
  • 試験範囲:配布資料1章〜7章(実行時環境まで)
  • 成績評価:定期試験の素点により評価します。今のところ追加判定も考えています。
過去の問題は、配布資料9章に掲載した練習問題にほとんど含まれています。練習問題の解答は用意していません。

「コンパイラ」第12回

  • 実施日: 2007-07-11(水) 1限
  • 講義内容: 実行時環境、目的プログラム生成
  • 配布資料7章、8章
この講義の最後として、アセンブリ言語の生成手法、プログラムの実行時環境についてお話をしました。

プログラミング言語の構文には、アセンブリ言語との対応が比較的つきやすいものと、つきにくいものがあります。ここでは簡単な代入文、if文についてアセンブリ言語との対応を示した後、数式についてコード生成の手法を述べました。数式を題材にとったのは、解析木との関連が分かりやすいためです。講義でも述べた通り、簡単な形の数式(三番地コードといいます)の並びに直してみるとアセンブリ言語との対応が容易につきます。また、三番地コードの並びは解析木と深く関連しており、これまでお話した翻訳スキームによりコード生成を行うことができます。

後半の主題は、より複雑なプログラミング言語の動作を、ハードウェアに近いコンピュータの動作に対応づけることでした。特に注意すべき動作として、変数領域の割り付け方式(大域変数、局所変数、メモリの動的割り付け)とメモリ管理との関連、関数呼び出しの動作についてお話しました。時間がなくてざっとしかお話しできなかったのですが、ハードウェアとソフトウェアの橋渡しとなる部分ですので、おおまかな内容については理解しておいてほしいと思います。

これで今年度の「コンパイラ」の講義は終わりです。

2007年7月10日火曜日

「形式言語理論」第11回

  • 実施日:2007-07-10(火) 1限
  • 内容:PDAの2つの受理言語(最終状態受理、空スタック受理)の等価性、PDAとCFGの等価性
  • 教科書6.2.3項、6.2.4項、6.3.1項、6.3.2項
これにて今年度の「形式言語理論」の講義は終了です。レポート課題の提出を忘れないようにして下さい。

岡山県立大学「データベース」第11回

  • 実施日: 2007-07-06(金) 2限
  • 内容: トランザクション、インデックス(索引)
  • 講義ノート
この回では、データベースを扱う際に目にする機会の多い用語である「トランザクション」「インデックス(索引)」について、ごく簡単に説明しました。いずれも、ちゃんと説明しようとすると1コマ以上必要になるテーマですが、本講義の目的が「RDBMSを使う」ということに主眼を置いているため、RDBMSの内部実装に関連の深いトランザクションや索引は、必要最小限にとどめました。興味のある人は、データベースに関する書籍などを参照してみて下さい。

2007年7月9日月曜日

岡山理科大学「データベース」第12回

  • 実施日: 2007-07-05(木) 7・8限
  • 内容: 表の設計(1) (関数従属性、第2正規形)
  • 講義ノート
この回は、表の設計の一つの指針として、関数従属性、表の正規形ということについてお話しました。

ここまでいろいろな表の例を出してきましたが、これらの表をどうやって設計すればよいかについてはお話してきませんでした。ともすると1枚の表にいろいろなデータを押し込んでしまいがちですが、これはあまりいい設計ではありません。講義でお話した通り、表の内容を更新しようとしたときに、いろいろと不都合が起こるからです。

関係データベースでは、このような不都合を解消するために、「1つの表がひとまとまりのデータを表す」程度にまで表を分割するという方法がよくとられます。今回ご紹介した関数従属性は、「ひとまとまりのデータ」というものを形式的に扱うための道具であり、キーと密接な関わりを持っています。今回お話した表の分割方法(正規化と言います)は知っておいてほしいと思います。この結果得られた表を第2正規形と言います。ほかに第1正規形、第3正規形などがありますが、これらはまとめて来週にお話しする予定です。

岡山県立大学「データベース」第10回

  • 実施日: 2007-06-29(金)2限
  • 内容:表の設計(正規化、関数従属性)
  • 講義ノート
この回は、関数従属性や表の正規化についてお話しました。

ここまでいろいろな表を例として用いてきましたが、どのようにこれらの表を設計するかについてはお話してきませんでした。表の設計に慣れないうちは1枚の表にデータを押し込んでしまいがちですが、あまりいい設計とは言えません。それは、この回で述べたように、データの更新時に不都合が発生してしまうことがあるからです。

今回紹介した関数従属性は、適切に表を分割するための1つの指針となる考え方です。時間の都合でかなり盛りだくさんの内容になってしまいましたが、「1つの表にはひとまとまりのデータのみ格納する」ことを形式的に扱う道具であると言えます。完全関数従属性や推移的関数従属性を用いた表の分割(正規化)の方法は是非知っておいて下さい。

2007年7月6日金曜日

岡山理科大学「データベース」第11回

  • 実施日: 2007-06-28(木) 7・8限
  • 内容: RDBMSを使う(GUIによるデータベース管理、埋め込みSQL)
  • 講義資料ページ
学会に行っていたりしたため、ブログへの投稿が遅れています。鋭意努力中ですので、もうしばらくお待ちください。

この回は、前回までお話ししてきたSQLを実際に使う方法として、Microsoft Accessに代表されるGUIによる方法、プログラムの中から使う方法の2通りを紹介しました。Accessはかなり本格的なRDBMSですが、よくできたGUIを用意しており、SQLをうまく利用者から隠しています。その反面、RDBMSを知らない人だと、何をやっているかよくわからないという印象をもたれがちだと思います。ここまでこの講義を受けられた方なら、GUIの操作を見ただけで、何をやっているのか容易におわかりいただけると思います。

プログラムの中から使う方法については、皆さんのカリキュラムを十分把握できている訳ではないこと、反応を見ているとそれほどプログラミング演習をやっているわけではないらしいこと、などの理由であまり深入りはしませんでした。資料には、PHPというプログラミング言語からRDBMSを利用する例を示しています。

2007年6月27日水曜日

休講通知:コンパイラ

出張のため、7/4(水)の「コンパイラ」は休講とします。

「コンパイラ」第11回

  • 実施日: 2007-06-27(水) 1限
  • 講義内容: S属性定義、L属性定義、実行時環境(導入)
  • 配布資料あり(7〜9章)
今回は、意味解析やコード生成での重要な技術である翻訳スキームのうち、性質のいいものとしてS属性定義とL属性定義のお話をしました。これらはいずれも、プログラム断片付き解析木を深さ優先に1回走査するだけで、ある計算を行うことができる翻訳スキームです。

「解析木を深さ優先に1回走査する」ということに拘るのには理由があります。講義でもお話した通り、コンパイラでは、解析木が大きくなる可能性があるため、走査の回数はなるべく減らしたほうが効率がよくなるのです。

ただし、講義では述べなかった理由がもう1つあります。LL(1)文法に基づく予測型構文解析では、トークン列を順次読みながら、根から葉に向かって解析木を成長させていきます。このとき、非終端記号と同名の関数を再帰的に呼び出していくのでしたね。予測型構文解析の場合,この関数の呼び出しは、ちょうど解析木を深さ優先探索にたどるのと同じ順番で行われます。ということは、解析木を実際に作らなくても、関数の再帰的な呼び出しを行うことで、あたかも解析木を深さ優先探索にたどるのと同等な処理ができるということになります。この関数の中に、S属性定義やL属性定義のプログラム断片を埋め込むと、何が起こりますか?解析木を作らなくても、翻訳スキームの計算が行えることになります。しかも、構文解析と意味解析が同時に行えてしまいます。現実のコンパイラの設計では、むしろこの理由のほうが重要なのです。

今日の講義では、最後のトピックであるコード生成の話に向けた準備として、プログラム実行時にCPUやレジスタ、メモリ周辺で何が起こっているか、簡単にお話しました。この話の基本的なところは先行科目「計算機アーキテクチャA」で説明があったはずです。ただし、現実のプログラムでは、実行時の記憶領域割り付け(局所変数やmalloc()など)、関数呼び出しなど、より複雑なことを考えねばなりません。次回はこの辺の話をして、さらにコード生成について簡単にお話したいと思っています。

レポート課題:形式言語理論

「形式言語理論」の受講者は以下のレポート課題を提出して下さい。これをもって定期試験の代わりとし、成績評価を行います。
  1. 課題内容:教科書の練習問題のうち、問2.5.1, 問4.4.2, 問5.3.2, 問5.4.1
  2. 提出場所:2610。部屋の前に提出用の箱、もしくは袋を出しておきます。
  3. 提出期限:2007/07/31(火) 17:00
  4. レポート形式:A4サイズの紙を使うこと。そのほかは自由。

休講通知:形式言語理論

出張のため、7/3(火)の「形式言語理論」は休講とします。

「形式言語理論」第10回

  • 実施日: 2007-06-26(火) 1限
  • 講義内容: プッシュダウンオートマトン
  • 教科書6.1節, 6.1.1〜6.1.2項
今回はプッシュダウンオートマトンを紹介しました。直観的には、プッシュダウンオートマトンはスタックを1本持つ非決定性の有限機械であり、文脈自由文法と等価な言語表現能力を持ちます。有限オートマトンと異なり,プッシュダウンオートマトンには、受理する言語の定義が2通りあります。入力を読み切ったとき(1)受理状態にたどりついていれば受理(2)スタックが空になっていれば受理、というものです。

次回はこの講義の最終回として、この2つの受理の定義が等価であること、そしてプッシュダウンオートマトンと文脈自由文法が等価であること、この2点について説明をします。

2007年6月26日火曜日

岡山県立大学「データベース」第9回

  • 実施日: 2007-06-22(金) 2限
  • 内容: SQL(SELECT文以外の構文)、一貫性制約、外部キー制約
  • 講義ノート
今回はSQLのうち、SELECT文以外の構文の主なものについてざっとお話をしました。岡山理科大学の講義との違いはほとんどありません。VARCHAR(可変長文字列のデータ型)についてもご紹介した程度だと思います。

SQLと言えばSELECT文が最も有名なのは間違いないところで、いちばん教えやすい構文でもあります。ですが、講義の最初にお話をした通り、 SELECTだけでは関係データベースは全く使えません。私が皆さんのように大学生だった頃、やはり講義と現実のシステムとのギャップに苦しみました。そ んな経験もあって、関係データベースを実際に使う局面を想定して、必要となる構文を簡単にご紹介しました。

今回の講義では、もうひとつ、一貫性制約(integrity constraints)という考え方をお話しました。これは、関係データベース中の表がいついかなる瞬間でも満たさなければならない条件であり、定義域 制約、キー制約、外部キー制約など(他にもいくつかあります)があります。CREATE TABLE文で表を作成するときにこれらの制約を書いておくと、関係データベースが自ら、これらの制約が成立しているかどうかを検査してくれるのです。こ れは、データベースを利用するプログラムを開発する人にとっては、とても大きな利点になります。(実際にプログラムを書かないとこのご利益はなかなか実感 できないと思いますが…)

外部キー制約は、この講義で初めて登場しました。データベースの教科書では厳密さを重視して数式による定義をしがちですが、この講義では厳密さよりも分か りやすさを追求し、直観的な説明を行いました。表でデータを整理するとき、外部キーの考え方は結構頻繁に登場しますので、どのようなものか理解しておいて ほしいと思います。

岡山理科大学「データベース」第10回

  • 実施日: 2007-06-21(木) 7・8限
  • 内容: SQL(SELECT文以外の主要構文)、一貫性制約、外部キー制約
  • 講義ノート
今回はSQLのうち、SELECT文以外の構文の主なものについてざっとお話をしました。

SQLと言えばSELECT文が最も有名なのは間違いないところで、いちばん教えやすい構文でもあります。ですが、講義の最初にお話をした通り、SELECTだけでは関係データベースは全く使えません。私が皆さんのように大学生だった頃、やはり講義と現実のシステムとのギャップに苦しみました。そんな経験もあって、関係データベースを実際に使う局面を想定して、必要となる構文を簡単にご紹介しました。

今回の講義では、もうひとつ、一貫性制約(integrity constraints)という考え方をお話しました。これは、関係データベース中の表がいついかなる瞬間でも満たさなければならない条件であり、定義域制約、キー制約、外部キー制約など(他にもいくつかあります)があります。CREATE TABLE文で表を作成するときにこれらの制約を書いておくと、関係データベースが自ら、これらの制約が成立しているかどうかを検査してくれるのです。これは、データベースを利用するプログラムを開発する人にとっては、とても大きな利点になります。(実際にプログラムを書かないとこのご利益はなかなか実感できないと思いますが…)

外部キー制約は、この講義で初めて登場しました。データベースの教科書では厳密さを重視して数式による定義をしがちですが、この講義では厳密さよりも分かりやすさを追求し、直観的な説明を行いました。表でデータを整理するとき、外部キーの考え方は結構頻繁に登場しますので、どのようなものか理解しておいてほしいと思います。

2007年6月22日金曜日

「コンパイラ」第10回

  • 実施日: 2007-06-20(水) 1限
  • 内容: 記号表、翻訳スキーム
  • 配布資料あり(6章)
今回から意味解析に入ります。意味解析では、構文解析まででは検査できない制約を解析しますが、字句解析や構文解析のようにすべて数学的な背景があるわけではありません。変数の宣言に関する制約(使用される前に宣言されていなければならない)は、記号表というデータ構造を使うことで、プログラム技術として解決されることが多いです。

この講義では、記号表について簡単に触れた後、意味解析で用いられる理論的道具として翻訳スキームと呼ばれるものを紹介します。これは解析木にプログラムの断片を埋め込み、これを深さ優先に1回走査して順次実行することで、解析木に対する処理を実行しようというもので、属性文法と呼ばれる理論の特別な場合にあたります。意味解析ばかりでなく、コード生成にも用いられる技術です。

今回は翻訳スキームの応用例として、中置記法の式を後置記法の式に変換する方法を紹介しました。また、翻訳スキームで用いられる変数の制限についても紹介しました。次回は、これを基に、どのようなプログラム断片なら翻訳スキームに用いることができるのか、もう少し考察を加えます。なお、中置記法、後置記法については、コンパイラとは関係なく有用な考え方ですので、知っておいて下さい。

2007年6月19日火曜日

「形式言語理論」第9回

  • 実施日: 2007-06-19(火) 1限
  • 内容: 文脈自由文法の性質・応用、構文木との関係
  • テキスト5章
講義の回数が残り少なくなってきたため、内容を選びながら駆け足でお話をしつつあります。今日は、前回に引き続き、文脈自由文法についての説明を行いました。ざっともう一度文脈自由文法を復習した後、構文木(解析木)、文法の曖昧性、応用例(構文解析系、構造化文書の構文の定義)についてお話しました。次回から、次のトピックとしてプッシュダウンオートマトンの話をします。
テクノラティプロフィール

2007年6月15日金曜日

岡山県立大学「データベース」第8回

  • 実施日: 2007-06-15(金) 2限
  • 内容: SQL(自己結合、ORDER BY, GROUP BY, HAVING、入れ子問合せ)
  • 講義ノート
今日の講義では、SELECT文の続きとして、自己結合、表の加工、入れ子問合せについてお話しました。表の加工はあまり理論的な話ではありませんが、現実には使う頻度が高い(特にORDER BY)ので、知っておいて損はないと思います。

今日の講義ノートには、時間の関係で講義中では簡単にお話したところも説明を加えています。興味のある人は読んでみて下さい。また、集計関数COUNTの説明が少し間違っていたので直しておきました(次回の講義の最初に説明します)。

次回は、SELECT文以外のSQLの構文についてお話していきます。

岡山理科大学「データベース」第9回

  • 実施日: 2007-06-14(木) 7・8限
  • 内容: SQL(自己結合、SELECT文のORDER BY, GROUP BY, HAVING、入れ子問合せ)
  • 講義ノート
SELECT文の最後として、関係代数には含まれない機能である表の加工について主にお話しました。今日の内容はあまり理論的なものではありませんが、実際にSQLを使う場合、並べ替えや集計は割と使う機能ですので、知っておくと便利だと思います。

なお、今回の講義ノートには、時間の関係で講義中では省略した説明を「発展的な話」として入れています。興味のある人は読んでみて下さい。また、集計関数のうちCOUNTについて、講義では少し間違った説明をしてしまいました。講義ノートでは直してあります(次回の最初に説明しようと思います)。

次回はSQLの落ち穂拾いとして、SELECT文以外の構文についてお話していきます。

2007年6月14日木曜日

「コンパイラ」第9回

  • 実施日: 2007-06-13(水) 1限
  • 内容: LL(1)文法(FOLLOW()関数、判定法)、構文解析プログラム
  • 配布資料5.3節、5.4節(5.5節は時間の都合で割愛)
前回に引き続きLL(1)文法の説明を行い、最後にLL(1)文法に対する予測型構文解析プログラムの概略を説明しました。前回説明したFIRST()関数に比べて、FOLLOW()関数は、どういうものか、なんのために必要か、ややつかみにくいかと思います。そのため、かなり時間をかけて説明をしました(その結果、プログラムの説明の時間がなくなってしまいました…)。

講義で使った例(配布資料を作成した後に考えた例なので、資料には載っていません)を再掲します。
S→aAB, A→b|c|ε, B→d
このような文法に対して、終端記号列adの構文解析を考えてみます。最初の文字aを読んで、SをaABに展開します(Sの子節点にa, A, Bを作成して解析木を成長させる)。次の文字dを読んで、Aを展開しようとしますが、A→b|c|εについて、FIRST(b), FIRST(c), FIRST(ε)のいずれにもdは含まれません。では構文解析は失敗なのか…というと、そうではなく、Aをεに展開し、さらにBをdに展開すると、成功します。この例から分かるように、FIRST()関数だけでは、次に出現し得る終端記号を列挙し切れない場合があるわけです。これがFOLLOW()関数を導入する理由です。

FIRST()関数、FOLLOW()関数、LL(1)文法かどうかの判定は、是非自分で手を動かして計算してみて下さい。

次回から意味解析に入ります。

「形式言語理論」第8回

  • 実施日: 2007-06-12(火) 1限
  • 内容: DFAの状態数最小化、文脈自由文法
  • 教科書4.4節、5.1節
長らくかかった有限オートマトンの話の最後として、DFAの状態数最小化アルゴリズムについてお話しました。理論的にも実用的にも興味深いものなので、アルゴリズム、これによって何が嬉しいのか、等の点について知っておくと後々役に立つこともあるかと思います。

次のトピックとして、文脈自由文法とプッシュダウンオートマトンを取り上げます。文脈自由文法については学部講義の「コンパイラ」でもお話しましたので、今回はその復習がてら、どのようなものであったかをざっとお話ししました。残り回数が少々心配になってきたので、この講義では、文脈自由文法と構文木(「コンパイラ」では解析木と言っていたもの)の関連、そして文脈自由文法と等価なオートマトンであるプッシュダウンオートマトンとの関連について、主にお話していこうと思っています。

2007年6月8日金曜日

岡山県立大学「データベース」第7回

  • 実施日: 2007-06-08(金) 2限
  • 講義内容: SQL(1) (SELECT文の概要)
  • 講義ノート
今日の講義から、この講義の第2のヤマ、SQLの説明に入りました。SQLの構文は多岐に渡りますが、その中で最も代表的なSELECT文をまず取り上げます。SELECT文は SELECT ... FROM ... WHERE ... という形をしており(他の句がつくこともあります)、概ね「FROM句で指定した表からWHERE句で指定した条件を満たす組についてSELECT句で指定された書式の表を出力する」という意味になります。今日の講義で示した通り、これらの句の指定をいろいろ代えることで、関係代数の選択、射影、結合、自然結合(これは来週取り上げます)に相当する問合せを記述することができるようになっています。

今日の講義で説明したJOIN句は、教科書になりそうな書籍には書かれていない構文ですが、実際の関係データベースでは結合を表す構文として使われています。まずはJOIN句を使わない書き方ができるようになって頂ければよいと思いますが、実際にはJOIN句も使われますので、そのつもりで知っておいて頂ければと思います。

岡山理科大学「データベース」第8回

  • 実施日: 2007-06-07(木) 7・8限
  • 内容: SQL(2) (SELECT文のWHERE句)
  • 講義ノート
前回に引き続き、SQLのSELECT文の説明です。今日はWHERE句の使い方について説明しました。WHERE句は組を選び分ける条件を記述する部分で、関係代数で言うところの選択条件や結合条件に相当します。1つの表を対象にすると選択条件に、2つ以上の表を対象にすると結合条件になるわけです。SELECT文は選択、射影、結合、自然結合などをすべてカバーする構文になっているのですね。

講義中でお話した通り、結合については、最近JOIN句を用いた新たな構文も使われるようになっています。教科書に使われるような書籍ではあまり触れられていない構文ですが実際に使われているので、この講義ではご紹介するようにしました。

「コンパイラ」第8回

  • 実施日: 2007-06-06(水) 1限
  • 内容: 構文解析(1) …文脈自由文法との関係、LL(1)文法(概要、FIRST())
  • 配布資料あり(第5章)
前回までお話した文脈自由文法を基に、構文解析の話を始めました。構文解析には大きく分けて下向き構文解析と上向き構文解析がありますが、この講義では下向き構文解析、しかもその特殊な場合である予測型構文解析についてのみ扱います。

文脈自由文法は導出を繰り返すことで終端記号列を得る仕掛けであり、一方構文解析はトークン列(終端記号列)を順次読んで解析木を得る処理です。両者は関係ありそうで関係なさそう、というように見えます。一つの解釈としては、導出により得られた記号列(文形式)を先頭から順次入力記号列と照合していき、その過程で解析木を作っていく、というものが考えられます。この講義では、この解釈に基づいて文脈自由文法と下向き構文解析を結びつけました。この解釈に従えば、予測型構文解析は、導出の際、どの規則を用いて非終端記号の展開を行うかが一意に決められるような下向き構文解析であり、対象とする文脈自由文法には制限があります。このような文法の一つがLL(1)文法です。

ある文法がLL(1)であるかどうかは機械的に判断することができます。その手法で用いられる考え方がFIRSTとFOLLOWです。今回はまずFIRSTについてお話しました。注意しなければならない点は、文脈自由文法では、非終端記号からεが導出される(つまり非終端記号から終端記号列が全く生成されない)ことがある、ということです。この事を念頭に置いて、FIRSTやFOLLOWの求め方、LL(1)文法の判定を読んで下さい。

2007年6月5日火曜日

「形式言語理論」第7回

  • 実施日:2007-06-05(火) 1限
  • 講義内容:閉包性を持つ正則言語の演算(4.2節)、反復補題(4.1節)、オートマトンの状態数最小化(4.4節、アイデアのみ)
有限オートマトンや正則表現に関する最後の話題として、正則言語に関する性質を取り上げます。この章で重要なのは、正則言語にどのような演算を施すと正則言語になるのか(閉包性)、どのような言語が正則ではないのか(反復補題)、それにオートマトンの状態数最小化です。

日程の都合上、閉包性に関してはほとんど事実のみを示し、共通部分の証明(直積構成法)のみ概略を示しました。また反復補題についても、正則でない言語の典型例である {0^n 1^n | n ≧ 1} についてのみ概略を示すにとどめました。学問を追究するという意味では不十分ですが、時間を考慮して、アイデアの理解を優先した結果です。興味のある方はテキストなりでより深く勉強していただければと思います。

オートマトンの状態数最小化については、実用上も重要な技術なので、時間を割いて説明するつもりです。まず今日のところは、おおざっぱなストーリーだけ示しました。次回、手法の詳細について説明します。

2007年6月1日金曜日

岡山県立大学「データベース」第6回

  • 実施日: 2007-06-01(金) 2限
  • 講義内容: 関係代数(商)、関係論理、SQLの導入
  • 講義ノート
今回はまず練習問題の解答例を述べた後、関係代数で唯一残った演算である商を説明しました。その次に、関係データベースのもう一つの数学的理論である関係論理について、ほんのさわりだけ説明しました。関係論理は現実のデータベースシステムで使われるわけではありませんし、割と記述が難しいので、あまり深くは述べません。組についての性質を論理式で記述する、という点において、次に述べるSQLと類似性があります。その点のみ理解しておいて下さい。

SQLについては、今回は、代表的構文であるSELECT文の例を2つほど出すにとどめました。次回に述べるつもりですが、SQLは、関係データベース管理システムの構成と深く関連しています。そこで、まず関係データベース管理システムについて詳しく説明した後、SQLの話に入っていこうと思っています。

岡山理科大学「データベース」第7回

  • 実施日:2007-05-31(木) 7・8限
  • 内容:関係データベース管理システムの概要、SQL(1)
  • 講義ノート
今日からこの講義の第2のヤマ、SQLの話に入りました。SQLというと、とかくSELECT文のみが取り上げられることが多いです。

確かにSELECT文が代表的であることは間違いないですし、講義をしていても面白い部分です。ですが、SQLはSELECT文だけではなく、そのほかに非常に多くの構文を含んでいます。そして、それらの構文は一般的な関係データベース管理システムの構成、使われ方に深く関わりがあります。そのためこの講義では、SQLに入る前に関係データベース管理システムの構成、使われ方等についてかなり時間をかけて説明しました。その後、SELECT文のお話を始めました。

今回はまずSELECT句、FROM句の役割についてのみ、例を用いて説明しました。次回はWHERE句の役割から話を始める予定です。

2007年5月30日水曜日

「コンパイラ」第7回

  • 実施日:2007-05-30(水) 1限
  • 内容:最左導出、最右導出、文法の曖昧性、左再帰とその除去方法、文脈自由文法の限界(4章最後まで)
早いもので、もう前期の講義の折り返し点なんですね。果たしてコード生成まで行くのか、かなり不安が残りますが、まあそれはともかく。

今日は、配布資料の4章の最後までをお話ししました。次週から構文解析の手法に入りますが、その際に最左導出がひじょうに関係してきます。また、曖昧でなく左再帰のない文法を対象とします。その意味で、今日の話は次週以降に関連してきますので、理解しておいてほしいと思います。

最後にお話しした文脈自由文法の限界はどう感じられたでしょうか。コンパイラで用いられる手法には、正則表現や文脈自由文法といった理論的なものの他に、かなり泥臭いものもあります。それは、ここでお話ししたように理論的な手法に限界があって、現実的な手法で解決したほうが楽である、という理由によることも多いです。こういう「清濁合わせ飲む」みたいなところが、コンパイラの話をややこしくしている一つの原因のような気がしているのですが、なるべく整理をしてお話ししていきたいと思っています。

2007年5月25日金曜日

岡山県立大学「データベース」第5回

  • 実施日: 2007-05-25(金) 2限
  • 内容: 関係代数(2)…直積、結合、自然結合
  • 講義ノート
今日は関係代数の2回目として、直積、結合、自然結合という演算について述べました。これらが2つの表から1つの表を作り出す基本的な演算であり、特に自然結合は頻繁に用いられます。講義の最後に、どう自然結合を使うかという例を一つ示しました。この使い方が典型例ですので、よく理解しておいて下さい。

ところで、今日の最後に出した練習問題のうち、(1)がどうも間違っていたような気がします。正しくは「県大生がアルバイトをしている会社名」です。「名前」と書いたような気がして仕方ないのですが、名前では何のことやら分かりませんよね。正しい問題を講義ノートのほうに書いてありますので、参考にして下さい。

2007年5月24日木曜日

岡山理科大学「データベース」第6回

  • 実施日:2007-05-24(木) 7・8限
  • 内容:関係代数(商)、練習問題の解説
  • 講義ノート
今回は、関係代数の演算のうち説明できていなかった商について説明した後、前回お配りした練習問題についての解説を行いました。今日の解説で分かる通り、関係代数による問合せは多くの場合以下のような形になります。
  • 入力となる表が1つの場合:選択で組を絞り込み→射影で必要な属性を残す
  • 入力となる表が2つ以上の場合:自然結合で1つの表にまとめ→選択で組を絞り込み→射影で必要な属性を残す
今回の練習問題の大半はこのパターンです(一つだけ、これにあてはまらない問題が含まれています)。

ただし、問題を解くには(そして実際にデータベースを操作するときには)まず日本語で書かれた問合せの意味を読み取る必要があります。また、今日の解説では具体的な表の例を出して説明をしましたが、実際の問題では、表の例は示さず、表のスキーマだけ示して問合せを書いてもらうことになると思います。関係の操作に慣れていない場合は、表のスキーマから具体的な表の例を作り、それを基に問合せを考えるようにして下さい。

2007年5月23日水曜日

休講:形式言語理論

5/29(火)は創立記念日のため、「形式言語理論」の講義は休講とします。

「コンパイラ」第6回

  • 実施日: 2007-05-23(水) 1限
  • 内容: 文脈自由文法(4.1〜4.2節あたり)
  • 配布資料あり(第4章)
今日から次のトピックである構文解析の話に入りました。今回はまず、構文解析とはどのようなものなのか復習がてらお話しした後、その理論的背景になっている文脈自由文法について、定義、意味をお話ししました。ポイントは、文脈自由文法は文字列を導出する道具であり、導出の過程が木で表現できること、導出の過程を表す木(解析木)が構文解析の出力になること、トークン列を順次読みながら解析木の生成を行うことが構文解析であること、などです。

文脈自由文法に関する性質のうち、構文解析で必要ないくつかについては次週に、そのほかの詳細については、大学院の講義「形式言語理論」でお話しする予定です。

2007年5月22日火曜日

「形式言語理論」第6回

  • 実施日: 2007-05-22(火) 1限
  • 内容: 3.2節(正則表現とFAの等価性)、4.2.1節(正則言語の集合和、補集合に関する閉包性)

2007年5月18日金曜日

岡山県立大学「データベース」第4回

  • 実施日: 2007-05-18(金) 2限
  • 講義内容: 関係代数(1)…集合演算、選択、射影
  • 講義ノート
今回から2回程度をかけて、この講義の最初のヤマである関係代数の紹介をします。関係代数を構成する演算はいずれも表に対するものであり、閉包性があります。今回お話した選択、射影は特に重要な演算ですので、どういうものか充分理解しておいて下さい。

定期試験には、最後に出した練習問題のような形の問題を出すつもりです。次回の最初に解答例を示しますので、今日の講義の内容の確認のつもりで考えてみて下さい。

岡山理科大学「データベース」第5回

  • 実施日: 2007-05-17(木) 7・8限
  • 講義内容: 関係代数(2) … 射影、直積、結合、自然結合
  • 講義ノート
前回に引き続き、関係代数の演算を紹介しました。これで、残るはあと1つ(商)となりました。次回はこの紹介と、具体的に表に対してある操作を行いたいとき、関係代数でどのように表現すればよいか、練習問題を通してお話ししたいと思います。

最後のほうのお話はあまりうまくしゃべれませんでした。直積や結合、自然結合では、異なる表2つを対象とするとは限りません。同じ表に対して直積や結合、自然結合を適用することも可能である、ということがお話ししたかったのでした。もう少しいい例を考えて、改めて皆さんに示したいと思っています。

2007年5月11日金曜日

岡山県立大学「データベース」第3回

  • 実施日:2007-05-11(金) 2限
  • 内容:キー(超キー、候補キー、主キー)
  • 講義ノート
今日は「関係中の組を識別する」というテーマで、キーという考え方について説明しました。前回にも述べた通り、関係は組の集合であり、組の出現順、属性の出現順は任意です。したがって、行数や列数に頼らずに組を指し示す必要があります。そのための概念がキー(key)です。関係データベースではよく用いられる概念なので、どういうものか、超キー/候補キー/主キーの区別、キー制約などについて理解しておいて下さい。

次回から関係代数の説明に入ります。

休講:形式言語理論

5/15(火)の形式言語理論は休講とします。

2007年5月10日木曜日

岡山理科大学「データベース」第5回

  • 実施日:2007-05-10(木) 7・8限
  • 内容:関係代数(1)…集合演算、選択
  • 講義ノート
今日から、本講義のヤマの一つ、関係代数の話を始めました。関係代数を構成する演算はいずれも表を入力として表を出力するものであり、閉包性を持っています。そのため、表に加工を繰り返し、目的となる表を得るという操作ができるわけです。

今日はまず、表に対して演算(操作)をするとはどういうことか、慣れてもらうために、ひじょうに丁寧にお話をしました。特に選択は関係代数の中でも極めて重要な演算の一つです。次回は続きとして、関係代数の残りの演算についてお話をする予定です。

2007年5月9日水曜日

休講:「コンパイラ」

5/16(水) のコンパイラの講義は休講とします。

「コンパイラ」第5回

  • 実施日:2007-05-09(水) 1限
  • 内容:字句解析プログラム(配布資料3.4.1〜3.4.3節)
  • 資料の訂正
    • p.21 1行目:int initial_state; → int start;
今日は、実際の字句解析プログラムの中身についてかなり丁寧にお話ししました。学生さんの傾向として、アルゴリズムを考えることはできても、それを実際のプログラムに直すことができない、という例をたくさん見てきました。そのために、アルゴリズムからプログラムに直す例としてお話を進めたつもりです。

3.4.4節、3.5節は省略し、次回から構文解析に入ります。

2007年5月8日火曜日

「形式言語理論」第5回

  • 実施日:2007-05-08(火) 1限
  • 内容:ε-NFA, 正則表現とその代数的性質
  • 教科書2.5節、3.1節、3.4節
来週の講義は休講にするかもしれません(まだ未定)。休講の場合は、掲示を出すとともにここのブログにその旨投稿しますので、注意しておいて下さい。

2007年5月2日水曜日

「コンパイラ」第4回

  • 実施日: 2007-05-02(水)1限
  • 講義内容:字句解析(1) (配布資料3.3節まで)
  • 配布資料あり
今日は字句解析の話を始めました。まず基本的な枠組について述べた後、正則表現/有限オートマトンを利用した字句解析の方法、考慮しなければならない問題と解決策(オートマトンの優先順位、先読み)についてお話ししました。次週は続きとして、具体的な字句解析プログラムについて述べる予定です。

2007年5月1日火曜日

「形式言語理論」第4回

  • 実施日: 2007-05-01(火) 1限
  • 内容: DFAとNFAの等価性、FAの応用(テキスト検索)
  • 教科書2.4.3節まで
前半では、言語クラス、等価性、模倣(simulation)の話をしました。いずれも教科書ではあまりはっきり書かれていませんが、この講義の内容を理解する上で基本となる考え方なので、丁寧に話してみました。「ある」言語/DFA/NFA/…と「すべての」言語/DFA/NFA/…の違いに充分注意しておいて下さい。

教科書を申し込まれた方は、次回の講義時に2,734円を釣り銭のないように持ってきて下さい。

2007年4月26日木曜日

岡山理科大学「データベース」第3回

  • 実施日時: 2007-04-26(木) 7・8限
  • 内容: スキーマ、キー
  • 講義ノート
今日はスキーマとキーについて話しました。両方ともデータベースに関わる場合は普通に目にする用語ですが、それ以外の分野であまり目にしません。そのつもりで、比較的丁寧にお話ししたつもりです。

講義の最後に触れた主キー(primary key)については、もう少しお話ししていない性質があります。講義ノートには書いていますが、「空値であってはいけない」という性質です。これは重要な性質なのですが、もう少し関係データベースのイメージがつかめてからのほうがよいだろうと考え、今日はお話ししませんでした。いずれ期を見て、データベースの満たすべき制約(一貫性制約)としてまとめてお話ししようと思っています。

2007年4月25日水曜日

「コンパイラ」第3回

  • 実施日: 2007-04-25(水)
  • 内容:正則表現、有限オートマトン
  • 配布物なし(前回配布の第2章の残りを使用)

2007年4月24日火曜日

「形式言語理論」第3回

  • 実施日:2007-04-24(火) 1限
  • 講義内容: 決定性有限オートマトン(DFA), 非決定性有限オートマトン(NFA)
  • 教科書2.2節、2.3.1節、2.3.2節に相当
  • 今日は講義ノートはありません。

2007年4月20日金曜日

岡山県立大学(情報システム工学科)「データベース」休講の案内

4/27(金)の「データベース」(岡山県立大学・情報システム工学科)の講義は休講とします。

岡山県立大学(情報システム工学科)「データベース」第2回

  • 実施日: 2007-04-20(金)
  • 内容: 予備知識、関係、組、第1正規形
  • 講義ノート
今日は、この講義で扱うデータの整理方法である表(関係)を扱う数学的枠組についてお話ししました。講義の最後にまとめを行いましたが、関係は組の集合とみなすことができ、その結果、関係の操作は集合演算の一種としてとらえられます。まとめの部分はよく理解しておいて下さい。

なお、講義ノートのうち、スキーマの話は時間が足りなくて今回は取り上げませんでした。回を改めてお話しすることにします。また、元々のシラバスにあった情報システムに関する話は、この講義の最後のほうで、時間が余ればお話しすることにします。

2007年4月19日木曜日

岡山理科大学「データベース」第2回

  • 実施日: 2007-04-19(木)
  • 内容: 予備知識、組(tuple)、関係、第1正規形
  • 講義ノート
今日から本格的に講義に入りました。講義ノートを見ていただくと分かる通り、当初はもう少し数学的に踏み込んだ話をするつもりだったのですが、学生さんの反応がよくなかったので、途中で方針を切り替え、直観的な説明を中心にしました。その結果、最後のほうの話(定義域に関する制約)はもう一つ分かりにくくなったかもしれません。集合の直積や定義域制約はもう少しちゃんとお話ししたほうがいいかもしれませんので、来週の講義で少し補足説明をするかもしれません。

2007年4月18日水曜日

「コンパイラ」第2回

  • 実施日: 2007-04-18(水)
  • 内容: 正則表現の説明に入る準備(形式言語の基礎知識)
  • 配布プリントがあります。必要な人は国島まで申し出て下さい。なお、配布したプリントは来週も使いますので、来週の講義に持ってきて下さい。

2007年4月17日火曜日

「形式言語理論」第2回

  • 実施日:2007-04-17(火)
  • 内容
    • この講義でよく用いる用語の説明(アルファベット、文字列、言語など)
    • 有限オートマトンの例
  • 講義ノート

2007年4月16日月曜日

SINET岡山大学ノードの機器障害

下記のように、SINET岡山大学ノードで現在機器障害が起こっており、岡山県立大学も外部との通信ができません(プロキシサーバ経由でWWWだけは閲覧できます)。メールも学外と学内との間で途絶している状態が続いています。

そのため、「形式言語理論」でテキストの購入を希望する場合はメールで連絡を下さいとアナウンスしていましたが、明日の講義の際に購入希望を書いてもらうようにします。また、障害の復旧状況を考慮しながらメールによる購入希望の期限を延長します(詳細は後日掲載)。

http://www.okayama-u.ac.jp/user/cc/osirase/stop.htm#sinetより:

学外への通信障害について

18:28現在の状況です:
見当を付けていた部品交換では復旧できませんでした。
まだ作業中であり、復旧の予定は不明です。
---
16:00現在の状況です:
交換部品が17時頃に到着しますので、18時頃には復旧できる見
通しです。
(100%確実に復旧できるとは限りませんのでご了承ください)
---
>先程からSINET岡山大学ノードで障害が発生し、学外とつながらない状況になって
>います。現在復旧作業中です。ご迷惑をおかけしております。

---
期間:平成19年4月16日(月)12:00頃から
影響:学外との接続ができない
大変ご迷惑をおかけしますがよろしくお願いいたします。

2007年4月13日金曜日

2007年度「データベース」(岡山県立大・情報システム工学科)開講

4/13より、情報システム工学科3年次を対象に「データベース」の講義を始めます。本ブログに日程、試験その他の情報などを掲載していきますので、適宜チェックして下さい。また、資料等も公開可能なものは下記WWWで公開していきます。
同一名称の科目を岡山理科大学でも開講しているので、混乱しないよう、充分注意して下さい。情報システム工学科向けの「データベース」に関する記事には、このブログでは、「データベース(システム)」というラベルをつけています。

2007年4月12日木曜日

2007年度岡山理科大学「データベース」開講

4/12より、岡山理科大学総合情報学部生物地球システム学科の講義「データベース」を開講します。
同一名称の講義を岡山県立大学でも開講しています。ページや本ブログの記事を間違えないようにしてください。本ブログでは、岡山理科大学の「データベース」の講義に関する記事は必ず「データベース(理大)」というラベルをつけるようにしています。

2007年4月11日水曜日

2007年度(平成19年度)「コンパイラ」開講

4/11より「コンパイラ」の講義を開講します(通信3年次)。講義の日程(休講、試験日程など)、資料へのポインタなどはこのブログに掲示していきますので、受講生は適宜チェックを行って下さい。
この日の講義では配布資料があります(諸事情でWWWに掲載するかどうかは未定)。残部がありますので、必要な人は国島の部屋まで取りにきて下さい。

2007年4月9日月曜日

2007年度(平成19年度)「形式言語理論」開講

4/10より「形式言語理論」の講義を開講します。

2007年3月30日金曜日

平成19年度前期の開講予定(追加)

もう公開してもよさそうなので、こちらに書いておきます。

先に書いた開講予定科目に加え、以下の科目を新たに開講します。
  • データベース(情報システム工学科・3年前期、金曜2限)
昨年まで加藤先生が担当されていた科目ですが、諸事情により、今年度は私が担当します。来年度以降も私が担当することになる可能性が高いですが、今のところは未定です。

なお、原則として情報通信工学科の学生の受講は認めません。情報通信工学科で開講されている「データ工学」を受講して下さい。

2007年3月19日月曜日

平成19年度前期の開講予定

平成19年度前期の開講予定は以下のようになっています。
  • コンパイラ(通信3年対象, 水曜1限)
  • 形式言語理論(通信修士1年対象, 火曜1限)
  • データベース(岡山理科大学・生物地球システム学科, 3年対象, 木曜7・8限)
随時こちらのブログでスケジュールなどを公開していきます。

2007年2月14日水曜日

2006年度「計算機言語II」定期試験結果

以下は合格です。
  • 21160xx のうち、xx が以下の者
    01, 02, 03, 07, 09, 10, 14, 15, 16, 18, 19, 20, 23, 25, 26, 27, 28, 31, 32, 33, 34, 37, 39, 42, 43, 44, 46, 47, 48, 50, 52, 55, 57, 59
  • 2118057
  • 2115019, 2115027, 2115043
以下は追加判定課題を提出することにより合格(C判定)となる可能性があります。追加判定を受ける意思がある場合は、2610まで課題を取りにきて下さい。
  • 21160xx のうち xx が以下の者
    04, 05, 11, 12, 17, 21, 30, 38, 40, 51, 53, 58
  • 2115045

2007年2月11日日曜日

2006年度「計算機言語I」定期試験結果

以下は合格です。
  • 21170xx のうち、xx が以下の者。
    01, 02, 03, 04, 05, 08, 11, 13, 15, 17, 18, 19, 22, 23, 24, 25, 29, 30, 34, 35, 38, 41, 44, 47, 48, 49, 50, 51, 57, 58, 62
  • 2115024, 2115044, 2115062, 2115070
以下はレポート提出により追加判定を受けることができます。希望する者は 2610 までレポート課題を取りに来てください。
  • 21170xx のうち、xx が以下の者。
    06, 09, 12, 14, 20, 21, 27, 28, 33, 39, 42, 43, 59, 60, 64
  • 2114029
  • 2115001, 2115004, 2115019, 2115025, 2115027, 2115045, 2115051, 2115069