本文へジャンプ

学科概要
  • HOME
  • 学科概要
  • 学生による学科紹介

学生による学科紹介

2年生冬学期

ハードウェア構成法 | 構成法 小林 芳直
開講時間: | 必修科目
シラバス
ASIC の論理回路設計の説明をする。 組合せ回路、同期式回路設計、ステートマシンによる同期、 順序制御、排他制御、演算回路。
要約
5学期に行われるハードウェア実験、6学期に行われるプロセッサ実験のための準備として、デジタル回路設計の基本を学習します。
論理演算を使用して高速な乗算器や簡単なステートマシンの設計ができるようになることを目指します。
学習すること
授業の一番初めは、1と0だけからなる論理演算(ブール演算)と論理圧縮から入ります。
その後は大まかに言うと、学期の前半は組み合わせ回路、後半は順序回路のしくみと設計方法を学びます。

組み合わせ回路とは、論理演算子(ANDやORやNOTなど)のパーツを組み合わせることによって、ある入力に対して一意な出力を与えるものです。
例えば整数同士の加算器は、足す数と足される数を与えると加算結果が1つに決まり、それを出力として返してくれるので組み合わせ回路の一例と言えます。

授業では、まずハーフ・アダーという2進数での1桁(1ビット)同士の加算を行うパーツが、論理演算子を使って簡単に構成されることが説明されます。
次に、ハーフ・アダーを基本とするパーツをいくつも組み合わせることで、何桁でも計算できる立派な加算器が作られるということを学びます。
このような過程で、ある複雑な演算回路もより簡単なパーツの集まりで構成されていることが理解できるようになります。

一方で順序回路とは、組み合わせ回路と違って、入力と回路内部の状況によって出力が決まるものです。
例えばアップダウン・カウンタは、回路内部が保持している値と「+1又は-1せよ」という外部からの入力(命令)の2つがあってはじめて、カウントアップ、またはカウントダウンした値を出力します。
値を保持するためにはフリップフロップというパーツが使用されますが、これも論理演算子の組み合わせで構成することができます。
思考が数学寄りな人は、授業中ここでちょっとつまづいてしまうこともあるかもしれませんが、順序回路を正確に理解することができれば、回路設計ができるようになるための大きな一歩となります。
コンピュータが行う「計算」のイメージは組み合わせ回路に近いかもしれません。
しかし、コンピュータがその演算の計算結果を記憶したり、繰り返し演算を行ったりするためには順序回路が不可欠なのです。

以上のように基本的な知識がそろえば、それを利用して減算器、乗算器、比較器などの作り方を勉強します。
それぞれ整数の引き算、掛け算、大小の比較を行なうものですが、実際のCPUではこれらをまとめてALU(演算論理装置)と呼んだりします。
さらに進んで、小数(正確には浮動小数点数)用の四則演算などを行なう演算ユニット(FPUと呼びます)や、ステートマシン(いくつかの状態を入力に応じて遷移するような構造を実現する回路で、順序回路で構成する)を利用したメモリアクセスの方法まで勉強します。
浮動小数点数は絶対値が極端に大きい値と極端に小さい(0に近い)値を表せるようにするため、データが指数部と仮数部という2つの領域に分かれています。
浮動小数点数の加減乗除は指数部と仮数部で別々の処理を行なわなければならず、それぞれの演算結果が互いに影響を及ぼしあう(丸め処理)ので複雑な演算回路になります。
また、メモリアクセスを行なうための制御回路はデータを要求するクロックと受け取るクロックなど、正確なタイミング制御が必要です。そのような場合は、しっかりとあらゆるパターンのタイミングチャートを書いて回路が正しく動作するか手作業で確認したりすることもあります。

この他に、様々なテクニックによるゲート数の削減や、乗算器におけるワラスツリーやステートマシンにおけるマイナーループの除去など、高周波数クロックで動作させる上で信頼性を向上させるためのTipsや高速化のテクニックを紹介してくださいます。
プロセッサ実験で使用するCADツールは、そういった最適化のほとんどを自動化するツールなので直接的にそれらの知識を生かしてCPUを設計するわけではありません。
しかし、そういった知識に基づくセンスを養っておくと、プロセッサ実験でCPUの速さを競い合うときにとても有利になります。
授業の雰囲気
指定教科書が存在しますが、教科書通りに授業が進むことはほとんどありません。
また、デジタル回路といっても、たまにアナログ回路についての知識が必要になったり、知っているとすんなり理解できることがあります。
なので、授業中に必要に応じて半導体物性(たとえば、NANDゲートがトランジスタを用いてどのように構成されているか)も教えてくださいます。

授業終盤では、3年生のCPU実験での回路設計に用いるプログラミング言語(VHDL)を使用して回路の挙動を説明されます。
CPU実験で主流になっているパイプラインアーキテクチャに関連して、昨今のパイプライン技術について説明しだくださったりもします。

雑談もおもしろく、航空機の話をされていたかと思えば、いつまにか動作周波数についての話題に繋がっていたりと、そういった話に興味がある人にとっては楽しくて仕方がありません。
雑談のために、資料を持っていらっしゃることもあります。

わからないことがあれば、その場で質問することもできますし、授業後に伺いにいくこともできます。
筆者の経験では、ちょっとわからないことがあった時に教科書を参照して期待する答えが書いてあったのは5割程度です。
毎回、授業が終わった後はわからなかった部分やさらに進んだことを質問する学生がたくさんいます。
それに対して、先生とTAの方が丁寧に解説してくださいます。
あまりにも話が弾んでしまって守衛さんが教室を閉めにくるまで対応してくださることも多々あります。
試験について
例年、試験では「こういう動作をするような回路を設計しなさい」というお題が与えられます。
内容は、ごく簡単な組み合わせ回路を作る問題から、実際にメーカの出しているSRAMの仕様書(英語)を読んで仕様に沿ったアクセス方法を要求される問題まで様々です。
しかし共通しているのは、指定されていないことは全て自分で勝手に決めてよいという点で、かなり自由度の高い試験になっています。
問題を解くだけなら、授業でやった回路設計の基本知識だけで対応することができます。
次のステップへ
この授業の中では、実際に抵抗やコンデンサを触ったりすることが無いので、初めて回路設計を勉強する人にとっては、自分の勉強していることに対して実感が湧きにくいかもしれません。
しかし冒頭で述べた通り、この授業は5学期に行われる実験Iの中のハードウェア実験の導入に位置づけられており、ハードウェア実験では、好きなだけトランジスタなどを使って回路を作ってみたり、VHDLによる回路設計をコーディングしてみたりできます。
またFPUの設計、さらにCPU本体の設計は6学期のプロセッサ実験で本格的に行なうことになります。
この授業は、一度も回路を触ったことが無い人が情報科学科に進学してから本格的に回路を設計するための橋渡しの授業になっているのです。
形式言語理論 | 宮野 悟
開講時間: | 必修科目
シラバス
形式言語とオートマトン、および、計算可能性の初歩について講義する。 形式言語とオートマトンについては、 正則言語、有限オートマトン、文脈自由言語を中心に。 計算可能性については、チューリング機械とその停止性問題に関して。
授業情報
4学期に開講される理学部の専門授業で、情報科学科では必修授業として扱われるので、進学した場合全員履修することになります。理学部他学科の選択授業でもあるため、他学科生も見受けられ、受講人数は半々といったところです。ここ最近は金曜3限に開かれているようです。
 授業方法は教員がスクリーンにスライドを映しながら説明し、その具体的な例や解法を板書していく形式です。なお、このスライドの内容は教員から教科書という形で予め無料配布されます。しかし、この教科書は抽象的な定義が書いてある部分がほとんどで、問題の解法については「授業中に説明する」とだけ書かれていたり、間違いが存在したりします。(編註:教科書が配布され始めて2年経ちましたが、まだ存在するようです。間違いは教員が授業中に修正します。)
 上記の理由により、出来るだけ出席はした方が良いと思います。実際は、最初こそ大半が出席して授業を聞いていますが、半ばを過ぎると出席人数は3分の2ほどになり、出席している人の半分ほどはうつらうつらしています。これをどう考えるかはあなた次第です。
前提知識
この授業を学ぶにあたって予め必要な知識というのは特にありません。使用する用語や定義については授業中に説明が有るので困らないでしょう。
授業概要
「形式言語理論」という名の通り形式言語について学ぶことになります。なぜ、情報科学科で形式言語を学ぶかといえば「我々が用いているプログラミング言語は、正しいプログラムならば形式言語であるといえる」からです。まず、形式言語の一つである正則言語を学ぶために、正則言語を受理する「オートマトン」について学ぶことから始めます。そのオートマトンを用いて「正則言語」を学びます。次に形式言語の一つである「文脈自由文法」について学びます。最後にオートマトンのように働く「Turing機械」について学びます。
発展
この授業は情報科学科後期授業の「言語処理系論」「言語モデル論」「情報科学演習」「コンパイラ演習」などに発展していきます。
 「正則言語」や「文脈自由文法」はコンパイラにおける「字句解析」「構文解析」を行うのに用います。
 「言語モデル論」では「我々が普段使用している言語(自然言語)は文脈自由言語ではないか」という事について考えます。
 「Turing機械」は幅広く使用されますが、「情報科学演習」の計算可能性などに用います。
試験
試験は3月の試験期間に行われる。問題は具体的では無いが、事前にある程度ばらしてくれます。例えば「正則言語のPumping Lemmaから出します」とか「過去問から出します」といった具合である。そのため試験勉強はし易い。問題は3問構成で、「正則言語」「文脈自由構文」「アルゴリズム」から各1題出る傾向です。授業では「Turing機械」についても勉強しますが、試験にはでないようです。なお、教科書には付録として過去の試験問題があるので、それを見れば傾向は簡単に掴めます。
 しかし、問題そのものは難しいため、授業や教科書を理解できていない場合、出る範囲が分かっていても、毎年単位を取れない人もいます。
 追試験は行うこともあるし、行わないこともあるため、本試験で単位を取得するのが賢明です。
まとめ(らしきもの)
基本的にこの授業は、これ単体で何かを学ぶというよりは、3年以降の授業のための知識をつけるといったものです。かといって、この授業が良く分からなかったから3年以降の授業についていけないということはまったくありません。とりあえず気軽に先生の授業を聞くのが良いのではないでしょうか。最低限、下に書いた授業内容くらいが分かっていれば「そういえば、やったなあ」と感じます。しばらくしてからもう一度教科書を読むとちゃんと理解できると思います。
授業内容
配布される教科書によると、この授業は
1章「基本的定義と記法」
2章「有限オートマトンと正則言語」
3章「文脈自由文法」
4章「Turing機械」
という4章構成+αとなっています。
 授業では各々形式的な定義を学びますが、そんなことをここで書いても読む気もしないだろうし、面白くもないので、各章の基本的な事を簡単に説明しようと思います。
有限オートマトン 〜例1〜
オートマトンなんて言葉を聞いたことがあるでしょうか? このページを読んでいるほとんどの方は聞いたことが無いのではと思います。かく言う筆者もこの授業で初めて聞いた言葉です。言葉で説明するなら「有限個の状態、状態遷移の組み合わせのモデル」ということになります。まあ、これだけじゃ何の事なのかさっぱりなので、教科書にも載っている分かり易い問題を見てましょう。

問題1
登場人物
 わたし:名前を「あんな」といいます。
 けんじ:わたしの恋人です。でも浮気っぽいのが心配です。
 ももこ:わたしの親友です。
 なおこ:わたしの親友です。
状況
 私たち4人は、あることから離れ小島に取り残されてしまった。
そこには二人乗りのボートがあるが、運転できるのは私だけです。
全員を岸まで運びたいのですが、けんじは浮気っぽいのでけんじとももこ、
けんじとなおこを二人だけにするのは危険なので嫌です。
さて、どのように運べば良いでしょうか?


 さて、この問題は「小島と岸に誰がいるかという状態」「ボートで人を運ぶ状態遷移」を考えていけば解ける。実際にこの状態遷移図を書いてみると以下のようになります。


この状態遷移図が「オートマトン」です。少しはオートマトンのイメージが掴めたでしょうか?
有限オートマトン 〜例2〜
この有限オートマトンは様々な分野で利用されますが、情報科学では0と1の文字を言語として扱うので以下のようなオートマトンを扱うようになります。

問題2
集合{x∈{0,1}*|[x]は3の倍数}を受理する有限オートマトンはどのようになるか
[x]は記号列xを2進数の整数とみた値


さて、オートマトンを作るには状態と状態遷移が必要です。3の倍数かどうかは3で割った余りを見ると分かります。そこで状態は

* 3で割った余りが0(状態q0)
* 3で割った余りが1(状態q1)
* 3で割った余りが2(状態q2)

の3つとすることが出来ます。次に状態遷移を考えます。
現在の状態、例えば11010が入力だとすると、110=6まで読み込んだ場合3で割った余りが0の状態です。次に読み込むのは1で、値としては1101 =13となります。これは現在の値100を2倍して1を足しているのと同じことです。(分かりにくい方は10進数で同じことを考えてみてください、 110→1101にするには10倍して1を足します)このように考えると、現在の値xとして2x+0or1を考えて状態遷移すればいいことになります。よって

* 3で割った余りが0の時、次が0の場合3で割った余りが0、次が1の場合3で割った余りが1
* 3で割った余りが1の時、次が0の場合3で割った余りが2、次が1の場合3で割った余りが0
* 3で割った余りが2の時、次が0の場合3で割った余りが1、次が1の場合3で割った余りが2

となります。したがってオートマトンは

となるわけです。

オートマトンについては他にも学ぶのですが、形式的な事になってくるので省略します。
正則(正規)言語
この授業では、上記の有限オートマトンによって受理される言語の集合を「正則(正規)言語」と定義します。例えば、先ほどの問題2であればその集合は(・・・・・・)となります。正則言語については「正則言語のPumping Lemma」という定理を学びます。これはその言語が正則でないことを証明する(正則か否かを判断する)定理です。具体的な説明は有限オートマトンについて学んでからでないと難しいと思うので、ここでは省略します。使いかたを簡単に説明すると、ある言語を正則だと仮定すると「Pumping Lemma」の定理において矛盾が生じる、といった背理法で用いられます。
 これに付随して、正則言語の表現方法として「正則(正規)表現」を学びます。基本的な形を簡単に説明すると、以下のようなものがあります。
 r?:rが0個か1個 例、"colou?r" = "color" or "colour"
 r*:rが0個以上 例、"go*gle" = "ggle" or "gogle" or "google" or ...
 r+:rが1個以上   例、"yaho+" = "yaho" or "yahoo" or "yahooo" or ...
といった表現です。
 最終的には、正規表現と有限オートマトンの関係を学びます。つまり、正規表現をオートマトンに直したり、逆にオートマトンを正規表現に直したりします。

(正則言語ってこれ以外に説明するべき事あるかしら、というか説明する意味があるかなー?)

* 文脈自由文法

 この言葉も聞いたことがある人は少ないと思います。単純にいうと「A → α」という形の生成規則だけで作られる言語の事です。よくわかりませんね、例を見てみましょう。

問題3
 次のような生成規則からはどのような言語が作られるでしょう? Sから始めてx,y,zになると終了とします。

S → E
E → (E + E)
E → x
E → y
E → z


 これならば大体想像がつくのではないでしょうか。例えば

S → E
→ (E + E)
→ ((E + E) + E)
→ ((x + E) + E)
→ ((x + y) + E)
→ ((x + y) + z)


となるので((x + y) + z)という表現が可能です。周りの環境に依存すること無く「A → α」という置き換えが可能な文法なので文脈自由、というわけです。このような文脈自由文法で生成される言語を「文脈自由言語」といいます。これも形式言語の一種であり、上で書いた正規言語は文脈自由言語の一つであるといえます(ただし逆「文脈自由言語は正規言語である」は言えません)。
Turing 機械
Turingとはイギリスの数学者の名前でチューリングと読みます。チューリング機械とは彼が考えた仮想機械で

* 無限に長いテープを持ち、そのテープはセルに分割されている
* 各セルは一つの文字を記憶できる
* テープに格納された情報を読んだり書いたりするヘッドを持ち、左右に動くことが可能である
* 内部状態を保存するメモリを持つ有限制御部

を持ちます。この機械は

* ヘッドがある位置のセルの情報を読み取る
* ヘッドがある位置のセルに情報を書き込む
* 機械の内部状態を変える
* ヘッドを右か左に1セル分動かす

という動作を行います。やっぱり分かりにくいですね。例えばどのように使えるか見てみましょう。

問題4
 Turing機械を用いて数字が偶数かどうかを判断するにはどうすればよいでしょうか?



与えられる数字は2進数なので、最後の数字が0か1かで偶数かどうかが判断できます。そこで、
1、ヘッドがある位置のセルを読み取り、数字ならばヘッドを一つ右に移動させ、この動作を繰り返す
2、ヘッドがある位置のセルを読み取り、数字以外(空)ならばヘッドを一つ左に移動させる
3、ヘッドがある位置のセルを読み取り、0ならば偶数、1ならば奇数である
と言えます。
 何故こんな機械について学ぶかといえば、「計算機で原理上解ける問題はチューリング機械でも解ける」と考えられているからです。後期課程ではこのチューリング機械を用いて計算可能性を考えます。


アルゴリズムとデータ構造演習 | 五十嵐 健夫
開講時間: | 必修科目
授業内容
「アルゴリズムとデータ構造」に関する演習を、 Schemeによって行う。
プログラミング演習(Scheme, C)
Scheme は、初めて関数型言語をさわったので、最初はとまどいつつも、なれてくると「わりと楽しい言語だなぁ」とは思ったのですが、やっぱり、括弧が多いというので、みんな、おいおいと言っていました。

最終的に Scheme の インタープリタを実装したのですがはじめは、インタープリタの仕組みとか全然想像できなかったのだけど、やってみると、結構「インタープリタというのはこういうふうに書くのか」と勉強になったと思います。
この授業があったから、3年になったときに、OCAML を勉強するときに、入りやすかったという気がします。

C 言語のほうは、自分が授業を受けたときは、5〜6人のグループワークで、授業でやったアルゴリズムのうち、ハッシュ、木構造、連想記憶などを手を動かして実装するという演習でした。
授業でやったコアのアルゴリズムを実装する人や、課題を形にするために、他の人が作ったものを使用するためのインターフェースを作る人がいました。
たとえば、地図上で最短経路を示すという課題があったのですが、最短経路を求めるアルゴリズムを書く人と、それをわかりやすく表示をする人で分担して作業をしました。

IS(情報科学科)に内定し、4学期に初めて、専門科目が始まったのですが、この演習と、アセンブラだけが、実装系の課題がでる授業で、他は座学でした。この演習をやっていると、IS に内定しているんだなという実感がわきました。

ただ、2年の冬なので、まったく C が書けない人がいて、そういう人は、実装をあんまりしなくても単位がとれてしまうので、Cの勉強を 3年ですることになり、これは困るんじゃないかな、2年の後半でみんなが C が書けるようになる授業をするべきなのじゃないかなと思っていたのですが、2007年の後期からは、授業がそのように変わったと下級生の人に聞きました。今は、僕達のときと、演習内容は違うのではないかと思います。