AY 2017 Undergraduate School Course Catalog

Foundations of CSE

2018/01/30

Back
開講学期
／Semester		 2017年度／Academic Year 　前期 ／First Semester
対象学年
／Course for;		 2nd year
単位数
／Credits		 4.0
責任者
／Coordinator		 Yutaka Watanobe
担当教員名
／Instructor		 Jie Huang, Taro Suzuki, Wenxi Chen, Yutaka Watanobe, Yodai Watanabe, Yen Neil Yuwen, Yan Pei
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 P1 or P2

更新日／Last updated on 2017/01/30
授業の概要
／Course outline		 Computers are machines that manipulates information. Fundamental study of computer science includes the problems how information is organized in the computer, how it can be manipulated, and how it can be utilized. The efficiency of programming and data processing is directly linked to algorithms and the structures of the data being processed. Thus, it is crucial for students of computer science to understand the concepts of information organization, information manipulation and algorithms.
In this course, students learn a range of algorithms and data structures as well as how to implement them through programming exercises.
授業の目的と到達目標
／Objectives and attainment
goals		 Students will be able to evaluate the strengths and weaknesses of data structures and algorithms as well as to develop efficient algorithms. In addition, the students will be able to apply the state-of-the-art of data structures and algorithms for solving problems and developing software. The aim of the exercises is to solve practical problems under limited resources and know from experience that the efficiency of an algorithm is much more important than that of hardware. Acquired knowledge and techniques will be used for their state-of-the-art research and software development in the future.
授業スケジュール
／Class schedule		 1 Introduction
2 Analysis of Algorithms
3 Array, Lists
4 Stack, Queue
5 Recursion, Divide and Conquer
6 Sorting I
7 Sorting II
8 Searching
9 Tree
10木 Binary Tree
11 Heap
12 Hash
13 Graph
14 Graph Algorithms
15 Dynamic Programming
教科書
／Textbook(s)		 Textbooks
Thomas H. Cormen, Introduction to Algorithms 1 and 2.
Robert Sedgewick, Algorithms in C 1 and 2.

Supplementary reader
Y. Watanobe, Algorithms and Data Structures for Programming Contest.
成績評価の方法・基準
／Grading method/criteria		 Attendance 10%
Assignment 40%
Examination 50%

This syllabus only contains basic information of this course. For more details about text books, course schedule, student evaluation, please follow the course instructors.
履修上の留意点
／Note for course registration		 Formal prerequisites:P1 Intro.Programming or P2 C Programing
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 http://www.u-aizu.ac.jp/course/alg1/
http://web-int.u-aizu.ac.jp/course/alg1/
http://judge.u-aizu.ac.jp/


Back
開講学期
／Semester		 2017年度／Academic Year 　後期 ／Second Semester
対象学年
／Course for;		 2nd year
単位数
／Credits		 2.0
責任者
／Coordinator		 Shigeo Takahashi
担当教員名
／Instructor		 Shigeo Takahashi, Hirohide Demura, Mohamed Hamada
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 F3

更新日／Last updated on 2017/01/30
授業の概要
／Course outline		 Efficiently and accurately transmitting information is one of the most important technical problem in modern digital society. Information theory provides a theoretical solution to this problem in the sense that it emerges from clear mathematical formulation. Ideas of information theory allows to compose efficient codes for compression and error correction by taking advantage of probability and statistical theorems. This subject is quite important because information theory plays a fundamental role in the fields of image data compression, cryptography, network communication, information content measurement, etc.
授業の目的と到達目標
／Objectives and attainment
goals		 The primary challenge of this course lies in understanding the mathematical formulations of information source coding and communication channel coding and effective methods for composing such codes, together with the concept of entropy that measures unpredictability of information or information content. Fundamentals of probability and statistics are also converted in this course.
授業スケジュール
／Class schedule		 * Sets, probability, means and variances,
* Conditional probability, Markov processes
* Information source coding, Instantaneous codes,
* Craft's inequality, uniquely decodable codes
* Mean code length, entropy, Information source coding theorem
* Huffman coding, compact coding
* Markov information source, Shannon diagram, Ergodicity
* Run-length code, Ziv-Lempel code
* Information content, Characteristics of Entropy
* Conditional entropy, mutual information
* Channel capacity, binary symmetric channel, maximum-likelihood method
* Hamming distance, Channel coding
* Channel coding theorem
* Parity check, rectangular code, triangle code
* Hamming coding, generator matrix, parity check matrix, syndrome
* Primitive polynomial, generator polynomial
教科書
／Textbook(s)		 Shin-ichi Oishi, "Introduction to Information Theory with Examples (in Japanese (Rei ni motoduku jouhouriron nyuumon)", Kodansha.
成績評価の方法・基準
／Grading method/criteria		 Mid-term exam(1/3), final exam(1/3), quizzes and so on(1/3).
履修上の留意点
／Note for course registration		 No prerequisite.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 http://www.u-aizu.ac.jp/~shigeo/course/it/ (Shigeo Takahashi)


Back
開講学期
／Semester		 2017年度／Academic Year 　前期 ／First Semester
対象学年
／Course for;		 2nd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Lothar M. Schmitt
担当教員名
／Instructor		 Masahide Sugiyama, Lothar M. Schmitt, Kazuto Asai, Kazuyoshi Mori, Igor Lubashevskiy
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/01/31
授業の概要
／Course outline		 This course is an introduction to Discrete Mathematics. The subject is important for computer scientists and engineers since almost all computer structures are based on discrete bits.
(1) In Logic and Set Theory, the most fundamental concepts of mathematical thinking (elementary logic, sets and mathematical propositions) and basic operations on them are introduced. This yields the structures of Boolean lattices/algebras and propositional calculus. This topic is important for computing since any theoretical argument or model uses this formalism. Examples for applications: using Boolean lattices to simplify computer hardware circuits; using theoretical arguments to design fast computer algorithms. Partition of sets into disjoint subsets (equivalence classes) is also studied. Examples for applications: information classification; computer-reconstruction of noisy images.
(2) In Relations and Functions, binary relations and their expression via 0/1-matrices are studied. We study properties of relations such as reflexivity, symmetry and transitivity, order, the composition of relations and corresponding matrix expressions. This includes the study of equivalence relations and classes (see above) which have important applications in computing. Examples: automatic information-clustering (in fuzzy logic and control); automatic simplification of computer programs. Ordered structures are important for understanding information storage and access in computers.
The study of relations leads to the study of functions which are a special type of relation. For functions, injectivity, surjectivity, bijectivity are studied. As a consequence of studying bijective (invertible) functions, one can define the cardinality of sets and, in particular, countable sets. Examples for applications: estimating/counting steps in a computation; the study of logic and its consequences for computing such as the following AI question: `Which theorems can be automatically proven given a system of mathematical rules?' Other types of functions such as characteristic functions are studied. Example for applications: computer control based upon fuzzy logic.
(3) In Graph Theory & Automata, we first study basic notions such as the degree of vertices, isomorphisms of graphs, walks in graphs, paths in graphs, or the diameter of a graph. In addition, we study a number of special graphs which occur in models and applications. Graphs can be represented by matrices which is important for their computer implementation. Examples for applications: every computer network or the whole WWW can be seen as graphs; information-linkage can be described by graphs (similarity of DNA structures or writing styles among people). Trees are an important class of graphs. A computer file-directory is a tree. Many company-structures are like a tree. Minimal spanning trees and minimal weighted paths in a graph are studied in this course.] Examples for applications: cost-minimalization in transportation or in production facilities.
Automata, a formalization of computer programs and computation, are described by certain types of graphs. The simplification of automata, which yields improved software and hardware performance in computers uses a combination of the above topics such as functions and equivalence relations.
(4) Finally, Combinatorics is a topic that is connected to most of the above, in particular, if one wants to determine the number of instances for a particular mathematical structure. Several principles of counting are studied, and basic notions such as binomial coefficients, permutations, combinations, repeated permutations, multinomial expansion, and (ordered) partitions. This includes studying mathematical induction. Combinatorics is important to count and estimate the number of computing steps and computing time in applications.
授業の目的と到達目標
／Objectives and attainment
goals		 Logic, Set Theory, Boolean algebras, Relations, Order, Functions, Graph Theory, Finite Automata, and Combinatorics.
授業スケジュール
／Class schedule		 Logic, Set Theory, Boolean algebras, Relations, Order, Functions, Graph Theory, Finite Automata, and Combinatorics.
教科書
／Textbook(s)		 [1] Discrete Mathematical Structures.
B. Kolman, R.C. Busby, S.C. Ross.
Prentice Hall
[2] Discrete Mathematics.
S. Lipschutz (McGraw-Hill),
Translated by Hiroshi Narushima. Ohm-sha.
成績評価の方法・基準
／Grading method/criteria		 Attendance (10%). Exercises (20%). Exams (30% Midterm, 40% Final).
2/3 attendance, and 2/3 homework submission are a requirement to pass.
履修上の留意点
／Note for course registration		 This is a basic course with essentially high school mathematics as prerequisite.
Formal prerequisites: none
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Discrete Mathematical Structures. / B. Kolman, R.C. Busby, S.C. Ross. / Prentice Hall Int. Inc.
Discrete Mathematics (McGraw-Hill). / S. Lipschutz, / translated by Hiroshi Narushima. Ohm-sha.


Back
開講学期
／Semester		 2017年度／Academic Year 　後期 ／Second Semester
対象学年
／Course for;		 2nd year
単位数
／Credits		 4.0
責任者
／Coordinator		 Hiroshi Saito
担当教員名
／Instructor		 Junji Kitamichi, Yukihide Kohira, Wanming Chu, Satoshi Nishimura, Hiroshi Saito, Abderazek Ben Abdallah, Yoichi Tomioka
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/01/29
授業の概要
／Course outline		 Logic circuit design is a design process in digital VLSIs. The main objective of logic circuit design is to design　functionalities implemented in a VLSI using logics variables that take 0 or 1
and logic operations (AND, OR, NOT). The term "design" implies that there are good designs and bad designs. Good designs mean optimum designs in terms of cost,　performance, and so on. Therefore, designers must consider design optimality so that an optimum logic circuit is designed.
授業の目的と到達目標
／Objectives and attainment
goals		 The main purpose of this course is to study the basic knowledge, design method, and optimization method for logic circuit design so that students can design an optimum logic circuit from a given specification.

In exercises, students design logic circuits from pre-defined specifications. Then, students simulate the designed circuits to verify the correctness of the designed circuits using Cadence software.
授業スケジュール
／Class schedule		 (Although the schedule is different by lecturers, the most of the course teaches the following contents)
1 Representation of numbers (binary
value，positive/negative value，addition/subtraction)
2 Boolean algebra
3 Two-level logic and two-level logic minimization
4 Various representations of logic functions
5 Delays and hazards
6 Combinational circuit designs (Functional units, modular designs)
7 Memory logic designs
8 Sequential circuit designs (Finite state machine，synchronous circuits)
9 Logic verification
教科書
／Textbook(s)		 (Depends on instructors)
成績評価の方法・基準
／Grading method/criteria		 (Depends on instructors)

Saito, H. (Ben, A-B.)      Mid-term Exam. 30%, Final Exam. 30%, Reports 40%
Nishimura, S. (Chu, W.)  Final Exam. 50%, Reports 50%
Kohira, Y. (Tomioka, Y.)  Mid-term Exam. 25%, Final Exam. 25%, Reports 50%
履修上の留意点
／Note for course registration		 Related courses:
Discrete Systems，Advanced Logic Circuit Design，Computer Architecture，VLSI Design
Formal prerequisites:None


Back
開講学期
／Semester		 2017年度／Academic Year 　前期 ／First Semester
対象学年
／Course for;		 3rd year
単位数
／Credits		 4.0
責任者
／Coordinator		 Toshiaki Miyazaki
担当教員名
／Instructor		 Wanming Chu, Satoshi Nishimura, Yong Liu, Junji Kitamichi, Toshiaki Miyazaki, Naohito Nakasato, Abderazek Ben Abdallah
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 L4 & F4

更新日／Last updated on 2017/01/26
授業の概要
／Course outline		 Students will learn fundamental issues of computer architecture with its design approach, and performance evaluation methods. A computer consists of a central processing unit, memory, I/O devices, and so on. In this course, the students will understand how a computer is established by combining some computing and control units which are composed of logic circuits learned in “Logic Circuit Design” course. More precisely, the students will learn abovementioned issues using MIPS processor as an example. In the exercises, the students will implement a simplified MIPS processor by using CAD (Computer Aided Design) tools such as Cadence. In addition, the students will study how a program runs on a processor through developing some programs using an assembly programming language.
授業の目的と到達目標
／Objectives and attainment
goals		 1. Understand the main principles of computer architecture.
2. Learn the fundamental of assembly programming.
3. Use CAD tools and a hardware description language, and learn the abstract of processor design
授業スケジュール
／Class schedule		 1. Introduction
2. Instruction set & assembly language
3. Instruction set & assembly language 2
4. Performance evaluation
5. Arithmetic for computer: addition, subtraction, ALU, etc
6. Arithmetic for computer2: multiplication, division, floating point
7. Datapath
8. Controller
9. Pipeline
10. Pipeline 2: hazards
11. Memory hierarchy: cache
12. Memory hierarchy: virtual memory
13. Storage & other I/Os: RAID, etc
14. Parallel processor: SIMD/MIMD, Vector
15. Parallel processor 2: cache coherency, recent trends, etc
教科書
／Textbook(s)		 Computer Organization and Design - The Hardware/Software Interface. David. A. Patterson and John L. Hennessy, 5th edition, Morgan Kaufmann Publishers, ISBN 0124077269

(邦訳）パターソン＆ヘネシー,「コンピュータの構成と設計　第５版 (上), (下)」, 日経ＢＰ社
成績評価の方法・基準
／Grading method/criteria		 Final examination(50%), Exercise report(50%). (No makeup examination)
履修上の留意点
／Note for course registration		 [Prof. Liu's class] The lecture will be offered in English
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Course website:
Will be announced in the first class

Related literature
“HDLによるVLSI設計―VerilogHDLとVHDLによるCPU設計　第2版” 深山正幸　他著

Prerequisites and other related courses which include important concepts relevant to the course
Prerequisites:
-Introduction to Computer Systems
-Logic circuit design

Related courses
-Operating Systems
-Comp. Organ. and Design
-Parallel Computer Architecture
-Embedded Systems


Back
開講学期
／Semester		 2017年度／Academic Year 　後期 ／Second Semester
対象学年
／Course for;		 2nd year
単位数
／Credits		 4.0
責任者
／Coordinator		 Alexander P. Vazhenin
担当教員名
／Instructor		 Yong Liu, Alexander P. Vazhenin, Hitoshi Oi, Konstantin Markov, Yohei Nishidate, Peng Li, Kohei Otsuyama, Kazuya Matsumoto
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 L4

更新日／Last updated on 2017/01/28
授業の概要
／Course outline		 Operating systems are an essential part of any computer system. Similarly, a course on operating systems is an essential part of any computer-science education. The operating system provides certain services to programs and to the users of those programs in order to make the programming task easier. In this course, four parts of the core of operating systems will be mainly learned. They are process management, memory and storage management, file system management, and I/O system management. Also, some abstract concepts such as cooperation of multi-process and deadlock will be discussed. We do not concentrate on any particular operating system or hardware. Instead, we discuss fundamental concepts that are applicable to a variety of systems. We present a large number of examples that pertain specifically to UNIX and to other popular operating systems.
授業の目的と到達目標
／Objectives and attainment
goals		 1. To learn the concepts about OS.
2. To get the knowledge about process management, including process concept, inter-process communication, and CPU scheduling.
3. To learn memory management including page management and virtual memory.
4. To learn the design and implementation of file system.
5. To get the knowledge about software and hardware of I/O system.
授業スケジュール
／Class schedule		 1. Operating System Concepts and Components
Topics to study:
OS Concepts
Computer-system components
Evolution Steps
OS Components
OS Services

2. PROCESSES
Topics to study:
Process Concept
Process States and Scheduling
Operations on Processes
Cooperating Processes
Threads
Inter-process Communication

3. CPU Scheduling
Topics to study:
Basic Concepts
Scheduling Criteria
Scheduling Algorithms
Algorithm Evaluation
Conclusion

4. Process Synchronization and Deadlocks
Topics to study:
Background
Critical Section Problem
Semaphores
Classical Problems
Necessary Conditions of Deadlocks
Resource Allocation Graph
Deadlock Prevention
Deadlock Avoidance
Deadlock Detection
Recovery from a Deadlock

5. Memory Management
Topics to study:
Background
Logical versus Physical Address Space
Swapping
Contiguous Allocation
Paging Model of Logical and Physical Memory
Implementation of a Page Table
Multilevel Paging
Inverted Page Table
Segmentation: Basic Methods
Segmentation with Paging
Demand Paging
Performance of Demand Paging
Page Replacement Algorithms
Allocation Frames
Thrashing
Demand Segmentations

6. File Management
Topics to study:
File-System Concepts
File Attributes
File Operations and Access Methods
Directory Structure and Implementation
Protection Mechanizm
File-System Organization
Allocation Methods
Free-Space Management
Directory Implementation
Efficiency and Reliability
Mass-Storage Management

7. Distributed Systems
Topics to study:
Background
Motivation
Topology
Network Types
Communication Strategies
Design Strategies
教科書
／Textbook(s)		 1. Modern Operating Systems, by Andrew S. Tanenbaum, Prentice-Hall, Inc.
2. Operating System Concepts, 5-9, A. Silberschatz and P. B. Galvin, John Wiley & Sons, Inc.
3. Materials and handouts provided by instructors
成績評価の方法・基準
／Grading method/criteria		 This policy is used by all course instructors.
Final examination, midterm, experimental reports, and class participation.
Exercises: 40 points
Quiz, Midterm + Exam: 60 points

Reports about results of exercises should be submitted in one week after each exercise. The later submission leads to decreasing the number of points as follows:
    The submission later than one week will reduce points to 50%,
    The submission later than two weeks will reduce points to 25%,
    The submission later than four weeks will reduce points to 10%.
履修上の留意点
／Note for course registration		 Computer　Architecture or Computer Organization, Basic Algorithms and Data Structures, Programming I (C or C++) or Java

Formal prerequisites:L4 Intro. Computer Systems
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 1. Course WWW-site: http://sealpv0.u-aizu.ac.jp/moodle/
2. 「オペレーティングシステム」前川　守著 岩波書店　ISBN4000103466


Back
開講学期
／Semester		 2017年度／Academic Year 　前期 ／First Semester
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Subhash Bhalla
担当教員名
／Instructor		 Subhash Bhalla, Wanming Chu, Maxim Mozgovoy
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/02/01
授業の概要
／Course outline		 A tabular (relational) model of a data is created.
The model aims at understanding the users, Programmers and
implementation level difficulties. The course prepares the
participants to become system engineers, designers, and
software developers.  The first part, explains relational
theory and query languages for databases.
Second part contains a study of database management system.
授業の目的と到達目標
／Objectives and attainment
goals		 Database systems are commonly used for information Systems.
The course covers system architecture, and database design.
It also covers the relational database systems technology.
It provides knowledge of application development and
experiments of working with relational databases.
Concepts related to web data,  knowledge and information
extraction, and Data Mining are explained. Most of the study  uses
detailed examples and class exercises.
授業スケジュール
／Class schedule		 1 Apr  7  Data Model+Operations  1-30     1,3  help exercises + HomeWork
2 Apr 14  Datbase Query Languages31-60    3,4  Model Database + Homework
3 Apr 21  Relational Algebra     61-90    4    Database I + HW
4 May 12  Relational Calculus    91-136   4    DatabaseII + HW
5 May 19  Dictionary and storage 61-136   2    Design of a Database + HW
6 May 26  Storage Indexing      136-165       Complete  Hw + Ex ( Part I )
-----------------------Mid-Term exam ( May 26 )--------------------------
7 Jun  2 Objects - Relations     1-20    5    startup(PostgreSQL O-RDBMSs)
8 Jun 09 Data Integrity         21-40    8    loading database
9 Jun 16 DBMS Architecture       41-60   1,2  simple SQL queries
10Jun 23 SQL  -  Programming    61-80    3    complex SQL queries
11Jun 30 Relational databases   81-100   4    SQL functions and procedures
12Jul  7 Views,XML,O-RDBMS     100-120  22    Database modifications
13Jul 14 Postgres Internals    120-140  10    Web database programming
14Jul 21 Web Data              140-160  10  Complete  Hw + Ex ( Part II)
15Jul 28 Postgres APIs         160-190
教科書
／Textbook(s)		 Database Systems Concepts, 6th edition,
by Korth, H.A., Silberschatz, A., and Sudershan, S., McGrawHill Book Co., 2010.


Fundamentals of Database Systems, 7th Edition,
by Ramez Elmasri, Shamkant B. Navathe, 2016 , Pearson  
成績評価の方法・基準
／Grading method/criteria		 Mid-term Examination(30 points); Two short quizzes (40 points (20 points each))
Database Programming Assignments(30 points)
履修上の留意点
／Note for course registration		 Prerequisites Subject(s):
Algorithms and Data Structures I and II, Computer Programming I
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 link for slides/handouts and exercise sheets,
  Course material, OHPs and notes recommended by the instructor(s).


Back
開講学期
／Semester		 2017年度／Academic Year 　1学期 ／First Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Taro Suzuki
担当教員名
／Instructor		 Kazuyoshi Mori, Mohamed Hamada, Taro Suzuki
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/01/30
授業の概要
／Course outline		 Theory of automata and languages is one of the most fundamental
fields of theory of computing. The core concept is to obtain
the method to describe infinite sets which are called languages
(countable ones are dealt in this field mainly).

We study two important systems to describe them: Automata,
the recognizing/accepting systems, and Grammars, the generating
systems. We study the relation of formal languages through
grammars and automata. We focus on hierarchies of languages.

They are standard tools of the well-educated computer scientist,
who often uses them to reformulate a problem in an easily
solvable form, or to recognize the language that cannot be
feasibly handled in general.
授業の目的と到達目標
／Objectives and attainment
goals		 At the end of the course the student　should be able to:

1. know the necessity to describe infinite (countable)
   sets(= languages) correctly

2. know methods to describe languages, automata as recognizors
   and grammars as gerarators of them

3. design automata and grammars for languages

4. understand the restriction on the automata and grammars and
   the hierarchy of describing powers of languages caused by
    such restriction (Chomsky's hierarchy)

5. understand the relation between automata and grammars
授業スケジュール
／Class schedule		 1. Introduction

First, important items students should know and obey are explained.
Then, languages we study in this course is introduced, and automata
and grammars as devices for describing languages are generally explained.

2. Automata

Automata and languages accepted by them are extensively studied.
Especially we deal with following four types of automata:
Finite Autonmata, Pushdown Automata, Turing Machine and
Linear-bounded Automata.

3. Grammars

Grammars and languages generated by them are explained in detail.
Following four types of grammars and languages are explained:
Regular Grammars and Regular Languages, Context-Free Grammars
and Context-Free Languages, Context-Sensitive Grammars and
Context-Sensitive Languages, Phrase Structure Grammars and
Phrase Structure Languages

4. Relationship among Automata and Grammars

Until now, though we studied automata and grammars separately,
we can expect that there is some relation between automata and
grammars, since they are both the devices to describe languages.
Here we establish the correspondences between four types of
automata and those of grammars, that is, Finite Autonmata and
Regular Grammars, Pushdown Autoamta and Context-Free Grammars,
Linear-bounded Automata and Context-Sensitive Grammars,
Turing Machine and Phrase Structure Grammars.

5. The Hierarchy of Language Classes

We explained there are four classes of languages. We establish
a relation called Comsky Hierarchy here. In order to establish
the relation, we find some property which every language in
one class satisfies, and then using it, we show the existence
of a language which does not belong to the class. That is,
we explain followings: Properties of Regular Languages and
the Existence of Languages which are not Regular, Properties
of Context-Free Languages and the Existence of Languages which
are not Context-Free, Properties of Context-Sensitive Languages
and the Existence of Languages which are not Context-Sensitive.

6. The computability and computational complexity

We briefly explain the existence of non-computable problems
even if they are formally defined. As an example of such problems,
we introduce the Halting Problem. We also briefly explain the
introduction of computational complexity and show some topics such as
P and NP classes of computational complexity, NP complete class and
some examples of NP complete problems.
教科書
／Textbook(s)		 It depends on Professors. Each Professor will announce the text
book. Students should prepare it by the first meeting of the course.
成績評価の方法・基準
／Grading method/criteria		 The evaluation depends on followings:
1. Examination results(Midterm(s), Final)
2. Quizzes and Reports
3. Class activity and attendance

Their weights depends on professors.
At the first meeting of the class, each professor
will explain the evaluation methods.
履修上の留意点
／Note for course registration		 Prerequisites and other related courses which include important
concepts relevant to the course

Students will be expected to have taken F3 Discrete Systems course.
Moreover, they are expected to have fundamental knowledge about
not only Programming and Algorithms but also Computer hardware and
its behavior.

Language Processing Systems requires the knowledge studied in this
course. Especially, in the first part (lexical analysis and syntax
analysis) of a language processing system such as a compiler,
the knowledge of automata and grammars is indispensable.
Therefore, students who will study Language Processing Systems
are strongly recommended to enroll this course.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 J. Hopcroft, J. Ullman: Introduction to Automata Theory,
Languages and Computation, Addison-Wesley, 1979.

J. L. Hein: Theory of Computation, An Introduction,
Jones and Bartlett, 1996.

M. Sipser: Introduction to the Theory of Computation,
PWS Publishing Co., 1996.

N. Pippenger: Theories of Computability,
Cambridge Univ. Press, 1997.

R. Greenlaw, H. J. Hoover: Fundamentals of the Theory of
Computation, Morgan Kaufmann Pubs.Inc., 1998

A. Meduna: Automata and Languages, Theory and Applications,
Springer, 1999.

J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory,
Languages, and Computation(3rd ed.), Addison-Wesley, 2006.


Back
開講学期
／Semester		 2017年度／Academic Year 　2学期 ／Second Quarter
対象学年
／Course for;		 4th year
単位数
／Credits		 3.0
責任者
／Coordinator		 Nobuyoshi Asai
担当教員名
／Instructor		 Nobuyoshi Asai, Konstantin Markov
推奨トラック
／Recommended track		 CF,CM
履修規程上の先修条件
／Prerequisites		 F1

更新日／Last updated on 2017/04/07
授業の概要
／Course outline		 The study of algorithms is at the very heart of computer science. This course is intended to teach the advanced computer algorithms and techniques for their design and analysis. After the course the students will have a solid background for this type of activity, as well as for representing algorithms in the format of computer programs.
授業の目的と到達目標
／Objectives and attainment
goals		 This course will cover (but not limited to) the following contents: algorithms and their complexity, graph algorithms, heaps, B-trees, matrix multiplication, algebraic path problem, special mathematical algorithms, string pattern matching, divide-and-conquer, dynamic programming, recursion, greedy, and algorithm design techniques.
授業スケジュール
／Class schedule		 Lecture 01 - Algorithms and their Complexity;
Lecture 02 - Priority Queue and Heap;
Lecture 03 - Graphs and Representations;
Lecture 04 - Weighted Graphs;
Lecture 05 - Shortest Path Problem;
Lecture 06 - Transitive Closure;
Lecture 07 - String-Matching Problem;
                        Midterm Exam.
Lecture 09 - Algorithm Design Techniques: Greedy Algorithms;
Lecture 10 - Algorithm Design Techniques: Divide-and-Conquer;
Lecture 11 - Algorithm Design Techniques: Dynamic Programming;
Lecture 12 - Algorithm Design Techniques: Backtracking;
Lecture 13 - Random Number Generators;
Lecture 14 - Randomized Algorithms;
Lecture 15 - Models of Computations.
教科書
／Textbook(s)		 Robert Sedgewick. Algorithims in C (Addison Wesley Professional, 1990, ISBN:0-201-51425-7)
成績評価の方法・基準
／Grading method/criteria		 Lab. Exercises: 60%;
Mid-Term Exam: 20%;
Final Exam: 20%;
(Note: Alterable by the professor in charge of the class.)
履修上の留意点
／Note for course registration		 F3 Discrete Mathematics
F1 Algorithms and Data Structures
Formal prerequisites:F1 Algo.and Data Struct.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Course Website: Course Website: <a href="http://hare.u-aizu.ac.jp/classaa/2017">http://hare.u-aizu.ac.jp/classaa/2017/a>

1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms (Addison Wesley Professional, 1974, ISBN:0-201-00029-6);
2. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman(著), 野崎昭弘, 野下浩平(訳)『アルゴリズムの設計と解析I』 (サイエンス社, 1977, ISBN:4-7819-0279-0);
3. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman(著), 野崎昭弘, 野下浩平(訳)『アルゴリズムの設計と解析II』 (サイエンス社, 1977, ISBN:4-7819-0280-4);
4. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC　第１巻　基礎・整列』 (近代科学社, ISBN:4-7649-0255-9);
5. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC　第２巻　探索・文字列・計算幾何』 (近代科学社, ISBN:4-7649-0256-7);
6. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC　第３巻　グラフ・数理・トピックス』 (近代科学社, ISBN:4-7649-0257-5);
7. T. H. Cormen, et al., Introduction to Algorithms, MIT press, 2009.(日本語版：T. コルメン, 他, アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書), 近代科学社, 2013)


Back
開講学期
／Semester		 2017年度／Academic Year 　3学期 ／Third Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Mohamed Hamada
担当教員名
／Instructor		 Taro Suzuki
推奨トラック
／Recommended track		 SD
履修規程上の先修条件
／Prerequisites		 F8

更新日／Last updated on 2017/01/23
授業の概要
／Course outline		 Language Processing is a basic and mandatory course in computer science.
It is studied intensively from the beginning of 1950's, and is still
an important research area.
  This course provides basic methods of language processing and
compiler construction through lectures and a project implementing
a simple compiler front-end of a tiny language.
授業の目的と到達目標
／Objectives and attainment
goals		 The objectives of this course are
-- to give students ability to use methods of programming language
   processing in program developments,
-- to give students a motivation to learn and study theoretical issues
   in computer science,
-- to develop students' programming skills through a practical programming
   project.

Students who succesively complete this course can learn the following:
-- the role of language processors such as compilers and interpreters,
-- the importance of compilers,
-- methods of compilation of progrraming languages,
-- relationship between theories of automata and grammars with the practices
   of programming language processing.

This course provides students with the following ability:
-- to understand the nature of programming languages,
-- how to handle methods in programming language processing in program
   developments,
授業スケジュール
／Class schedule		 The topics covered in lectures:
1. Introduction: the outline of compilers, the structure of compilers,
   the role of compilers and interpreters in programming languages.
2. Lexical analysis: the role of lexical annalyzers (scanners),
   lexims(tokens), regular expressions, the definition of lexims with
   regular expression, an application of finite automata to lexical analysis.
3. Parsing: the role of parsers。top-down parsing, LL(1) parsing,
   botom-up parsing, LR(1) parsing, syntax-directed translation.
4. Compiler compilers： generation of scanners and parsers,
   scanner and parser generator tools.
5. Contextual analysis： analysis of contextual information, type checking,
   symbol tables.
6. Intermediate-code generation： intermediate languages(abstract syntax tree,
   stack representation, three address code), generation of abstract syntax
   trees and three address codes, runtime environment.
7. Intermediate-code optimization： simple optimization method
8. Target-code generation：generation of target codes from intermediate codes,
   target code generator

Exercises:
1. a project to implement a simple compiler front-end, which generates an
intermediate code (abstract syntax trees). The compiler consists of
-- a lexical analyzer,
-- a program that maintains symbol tables,
-- syntax-directed translator with parsing, contextual analysis and
   intermmediate-code generation (impmentend by a parser generator).
2. exerceses held in the lecture room to learn LL(1) and LR(1) parsing
   methods etc.
教科書
／Textbook(s)		 Compilers -- from basics of language processors to yacc/lex --
Satoshi Okawa and Taro Suzuki, Kindai-Kagaku-sha, 2008 (in Japanese).
成績評価の方法・基準
／Grading method/criteria		 1. requirements
(a) the attendance at lectures,
(b) middle and final exams (The both are mandatory),
(c) the attendance at exercises and the submission of assignments.

2. evaluation
Mid-term Exam. 30%, Final Exam. 40%, Exercise 30%
-- No make-up examination.
履修上の留意点
／Note for course registration		 It is desirable that the students who takes this course have already
successfully complete C programming, Java programming I, Algoriths and
Data Structures. It is strongly recommmended that the students have
completed Automata and Languages.


*Formal prerequisites:F8 Automata and Languages
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Other than the references listed below, the lecturer provides references,
handouts, etc. as required.

1. Compiler Design by Bergmann. WCB. Available for free download at
   http://elvis.rowan.edu/~bergmann/books.html.

2. Compilers -- Principles, Techniques and Tools by M.S. Lam, R. Sethi,
   J.D. Ullman, and A.V. Aho. Addison-Wesley. (2nd Ed.), 2006

3. Introduction to Compiler Construction in a Java World by B. Campbell,
   S. Iyer and B. Akbal-Delibas. Chapman and Hall/CRC, 2012.


Back
開講学期
／Semester		 2017年度／Academic Year 　3学期 ／Third Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Yohei Nishidate
担当教員名
／Instructor		 Yohei Nishidate, Saji N. Hameed
推奨トラック
／Recommended track		 CM,BM
履修規程上の先修条件
／Prerequisites		 F1

更新日／Last updated on 2017/01/30
授業の概要
／Course outline		 This course provides basics of numerical methods. Applications of numerical methods in all main areas of floating-point computing are covered. The course focuses on ideas and techniques that are widely used in Computational Science.
授業の目的と到達目標
／Objectives and attainment
goals		 Students who successfully complete this course will be able to: demonstrate an understanding of the main numerical methods; develop computer programs based on numerical methods; use methods of numerical analysis in practical problems.
授業スケジュール
／Class schedule		 Week 1: Introduction. Computer Precision
- Introduction to numerical analysis
- Floating-point representation
- Determination of computer parameters

Week 2: Errors of Floating-point Computations
- Loss of significance
- Error propagation
- Function evaluation

Week3: Zero of a Function
- Bisection method
- Newton's method
- Newton's method for systems

Week 4: Linear Algebraic Equations
- Vectors and matrices
- Gauss elimination with pivoting
- LU decomposition

Week 5: Matrix Inversion. Matrix Eigenvalues
- Determinant of a matrix
- Matrix inverse
- Eigenvalues of a matrix. Jacobi diagonalization

Week 6: Interpolation and Curve Fitting
- Lagrange polynomials
- Newton polynomials
- Least-squares curve fitting

Week 7: Cubic Splines
- Interpolating cubic splines
- B-splines

Week 8: Numerical Differentiation and Integration
- Forward difference and central difference
- Numerical integration. Trapezoidal rule
- Simpson’s rules
- Gauss quadrature

Week 9: Ordinary Differential Equations
- Euler’s method
- Predictor-corrector method
- Runge-Kutta methods
- First-order systems

Week 10: Partial Differential Equations
- Finite difference method
- Laplace equation
- Poisson equation
- Derivative boundary conditions

Week 11: Methods for Sparse Matrices
- Matrix storage
- Direct solution methods
- Iterative methods

Week 12: Random Number Generation and Monte Carlo Method
- Linear Congruential Generators
- Integration by Monte Carlo Method

Week 13: Finite Element Method (1)
- Galerkin method
- Variational formulation
- Finite element equations

Week 14: Finite Element Method (2)
- Discretization
- Elements
- Triangular element

Week 15: Finite Element Method (3)
- Isoparametric elements
- Assembly and solution of finite element equations.
教科書
／Textbook(s)		 Lecture notes.
数値で学ぶ計算と解析,金谷健一,共立出版.
成績評価の方法・基準
／Grading method/criteria		 Exercises 50%.
In class testing 20%
Final examination 30%.
履修上の留意点
／Note for course registration		 Prerequisites: C Programming, Algorithms and Data Structures.
Related courses: Calculus, Linear Algebra, Java Programming.

Formal prerequisites:F1 Algo.and Data Struct.


Back
開講学期
／Semester		 2017年度／Academic Year 　3学期 ／Third Quarter
対象学年
／Course for;		 4th year
単位数
／Credits		 2.0
責任者
／Coordinator		 Noriaki Asada
担当教員名
／Instructor		 Noriaki Asada
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/01/30
授業の概要
／Course outline		 Although the background of data compression technology is information theory and code theory, data compression is frequently used like a black-box software without knowledge of these theories. If fundamental algorithms are known from knowledge of information theory or image compression, there are many difficulties in programming. Goal of this class is to understand fundamentals of data compression and implementation of some data compression programs.
授業の目的と到達目標
／Objectives and attainment
goals		 Understanding fundamentals of data compression and implementation of some data compression programs.
授業スケジュール
／Class schedule		 ・ Words and history of data compression, Huffman code
・ Huffman code exercise
・ Arithmetic code
・ Arithmetic code exercise
・ Compression with moving window, LZSS
・ LZSS exercise
・ LZW
・ LZW exercise
・ Image compression, DCT
・ DCT exercise
・ Fractal
・ Fractal exercise
教科書
／Textbook(s)		 The Data Compression Book, 2nd ed. M. Nelson & J.L. Gailly, M&T Books.
成績評価の方法・基準
／Grading method/criteria		 Reports of exercises (100%).
履修上の留意点
／Note for course registration		 It is desirable to have knowledge about C language and Information Theory.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 http://web-int.u-aizu.ac.jp/~asada/class/DC.html


Back
開講学期
／Semester		 2017年度／Academic Year 　3学期 ／Third Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 2.0
責任者
／Coordinator		 Wenxi Chen
担当教員名
／Instructor		 Wenxi Chen
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/01/30
授業の概要
／Course outline		 地理情報システム（GIS）やコンピュータグラフィックス（CG）、コンピュータ援用設計（CAD）、パターン認識などでは大量の幾何図形データを高速に処理しなければならない。本科目では、コンピュータでこのような幾何学的な問題を取り扱うための効率的なアルゴリズムとデータ構造の設計と解析を勉強する。
本授業は実世界の問題を提起し、計算幾何学と結びつけ、直観的な考え方から出発し、アルゴリズムを導き出し、適切なデータ構造を用いて問題を解く手法を説明する。
プログラミング宿題の他に、プロジェクト研究課題を設け、計算幾何学知識を活かせて、実際の問題解決へのアプローチを身に付けながら計算幾何学の素晴らしさを楽しむ。
授業の目的と到達目標
／Objectives and attainment
goals		 計算幾何学の基本となるデータ構造やアルゴリズムを理解し、具体的な問題に対して応用できるようにする。
授業スケジュール
／Class schedule		 第一章 基本概念　　主要な幾何学的問題、典型的なデータ構造とアルゴリズムの復習
第二章 線分交差　　直交線分と任意線分の交差検出
第三章 凸包　　　　　定義と計算方法（直接法、包装法、Graham走査法、逐次添加法等）
第四章 ボロノイ図　　定義、性質と構成方法（直接法、逐次添加法、分割統治法、Fortune走査法）
第五章 ドローネ三角形分割　基本概念、関連術語、求め方（正当な三角形分割法、平面双対法、逐次添加法）
第六章 幾何的領域探索　　　直交領域探索の概念、1と2次元領域探索
第七章 多角形の三角形分割　問題の提起、基本概念、平面走査法
教科書
／Textbook(s)		  Computational Geometry - Algorithms and Applications
M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf 著
Springer-Verlag
又はその和訳版
 コンピュータ・ジオメトリ－計算幾何学：アルゴリズムと応用
M. ドバーグ、M. ファン・クリベルド、M. オーバマーズ、O. シュワルツコップ　著
浅野　哲夫訳、近代出版社
又は
 計算幾何学入門 - 幾何アルゴリズムとその応用
譚学厚、平田富夫 著
森北出版
成績評価の方法・基準
／Grading method/criteria		  宿題　　　　　　　　50%
プログラミング問題、4回。
プログラムの実装を通じて、計算幾何学のデータ構造とアルゴリズムに関する知識を深める。
又は
 プロジェクト研究　50%
１回。
冬休み期間を利用して、実用性のある課題を提出し、色々なリソースから調査活動を展開し、総合的に実際問題解決へのアプローチを勉強する。
及び
 期末試験　　　　　50%
１回。基本概念についての理解程度を検証する
履修上の留意点
／Note for course registration		 先修科目
 プログラミング言語（C又はJAVA）
 データ構造とアルゴリズムの基礎
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 参考ホームページ
授業用
http://i-health.u-aizu.ac.jp/CompuGeo/index.html
邦文サイト
http://www.ise.chuo-u.ac.jp/ise-labs/imai-lab/
http://www.simplex.t.u-tokyo.ac.jp/kika.html
英文サイト
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html
http://geometryalgorithms.com/
http://mathworld.wolfram.com/
http://www.diku.dk/hjemmesider/studerende/duff/Fortune/

参考図書
 計算幾何学
浅野哲夫 著
朝倉出版

 計算幾何学
今井浩、今井圭子 著
共立出版株式会社

 Computational Geometry in C
J. O'Rourke 著
Cambridge University Press

 データ構造（アルゴリズムシリーズ１）
浅野哲夫 著
近代科学社

 Algorithm in C, Vol. 2（又は同邦訳版）
Robert Sedgewick 著
Addison-Wesley


Back
開講学期
／Semester		 2017年度／Academic Year 　1学期 ／First Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Rentaro Yoshioka
担当教員名
／Instructor		 Alexander P. Vazhenin, Incheon Paik, Vitaly V. Klyuev, Rentaro Yoshioka, Yan Pei, Julian Villegas
推奨トラック
／Recommended track		 CM,SE,CN
履修規程上の先修条件
／Prerequisites		 P3

更新日／Last updated on 2017/02/28
授業の概要
／Course outline		 Software Engineering is a field concerning technologies and methods related to software development. It is about how software should be built, how they should be managed and includes a wide range of both theoretical and practical knowledge. As the presence of software in our daily life seems only to increase, the importance of software engineering is also increasing. It is also one of the fundamental knowledge of software that any engineer in the IT field should understand.
In this course, we first study the processes involved in the making of software and understand how they affect the final product. For each stage of the process, we consider issues that need to be solved and visit related technologies and methods that are available. In presentation of available technologies and methods, the goal is to understand the issues and their representative solutions. Both historical and cutting-edge technologies will be introduced as necessary. We will not cover the differences that arise with different forms of software (such as, embedded, web-based, parallel, etc.) but focus on more general and common aspects.
In summary, this course focuses on understanding the knowledge and technology sets comprising Software Engineering.
In exercises, to help the understanding of basic knowledge, students will work on concrete exercise problems. Each exercise class covers one stage of the development process, and the work required in each stage will be covered one-by-one. Each exercise is designed with a real-world application in mind it is possible to realize issues that are difficult to notice only by theory and basics. After completing all the exercises, students will experience a typical development process and understand its role and effects.
授業の目的と到達目標
／Objectives and attainment
goals		 1. Be able to explain the knowledge and technologies involved in Software Engineering
2. Be able to explain the typical stages of a development process and explain their characteristics and issues involved.
3. Be able to develop an application by employing a typical process and model
授業スケジュール
／Class schedule		 Day 1
Lecture : Introduction to Software Engineering
Exercise : Orientation and Requirements Definition 1
Day 2
Lecture: Processes & Requirements Definition
Exercise : Requirements Definition 2
Day 3
Lecture : Requirements Definition 2
Exercise : Requirements Phase - Feedback & Self-check
Day 4
Lecture : Requirements Definition 3
Exercise : Analysis 1
Day 5
Lecture : Analysis – Architectural Design
Exercise : Analysis 2
Day 6
Lecture : Analysis – Architectural Design 2
Exercise : Analysis 3
Day 7
Lecture : Analysis – Architectural Design 3
Exercise : Analysis – Feedback & Self-check
Day 8
Lecture : Design – Module Design
Exercise : Detailed Design 1
Day 9
Lecture : Design – Modules Design 2
Exercise : Detailed Design 2
Day 10
Lecture : Design – Module Design 3
Exercise : Detailed Design 3
Day 11
Lecture : Programming
Exercise : Detailed Design Phase – Feedback & Self-check
Day 12
Lecture : Test
Exercise : Development & Test
Day 13
Lecture : Unit Test
Exercise : Development & Test
Day 14
Lecture : System Test
Exercise : Development & Test
Day 15
Lecture : Summary & Future Perspective
Exercise : Development & Test Phase – Feedback & Self-check
教科書
／Textbook(s)		 Textbook：ソフトウェア工学
Author：岸 知二, 野田 夏子
Publisher：近代科学社
SBN：978-4764905092
成績評価の方法・基準
／Grading method/criteria		 1. Quiz 5%
2. Final Examination 60%
3. Exercise 35%
*Exercises are evaluated by the level at which they satisfy the requirements of the task.
* Exercises are expected to be submitted during class. The final due date of each exercise is at 24:00 of the day before the next lecture.
履修上の留意点
／Note for course registration		 * All exercises should be performed individually (Is not team work).
*Absence without lecturer’s permission will be penalized.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 http://borealis.u-aizu.ac.jp/classes/se1
Moodle http://sealpv0.u-aizu.ac.jp:20000/


Responsibility for the wording of this article lies with Student Affairs Division (Academic Affairs Section).

E-mail Address: sad-aas@u-aizu.ac.jp