AY 2018 Undergraduate School Course Catalog

Foundations of CSE

2019/01/30

Back
開講学期
／Semester		 2018年度／Academic Year 　2学期 ／Second Quarter
対象学年
／Course for;		 2nd year
単位数
／Credits		 4.0
責任者
／Coordinator		 Yutaka Watanobe
担当教員名
／Instructor		 Jie Huang, Wenxi Chen, Yutaka Watanobe, Yan Pei, Wanming Chu, Qiangfu Zhao
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/12/15
授業の概要
／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, Sort I
3 Data Structures
4 Search I, Hash
5 Recursion, Divide and Conquer
6 Sorting II
7 Tree
8 Binary Search Tree
9 Heap
10 Dynamic Programming
11 Graph
12 Graph Algorithms
13 Heuristic Search
14 String Matching
教科書
／Textbook(s)		 Textbooks
Thomas H. Cormen, Introduction to Algorithms 1.

Supplementary reader
Thomas H. Cormen, Introduction to Algorithms 2.
Y. Watanobe, Algorithms and Data Structures for Programming Contest.
成績評価の方法・基準
／Grading method/criteria		 Assignment 50%
Examination 50%
履修上の留意点
／Note for course registration		 Formal prerequisites:P1 Intro.Programming or P2 C Programing
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Couse Web Site
http://web-int.u-aizu.ac.jp/course/alg1/

Web Site for exercises
https://onlinejudge.u-aizu.ac.jp/

References
Thomas H. Cormen, Charles E. Leiserson,  Ronald L. Rivest, Clifford Stein, Introduction to Algorithms (MIT Press).
Robert Sedgewick, Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms.

Office hours
Office hours will be provided on the course Web site.


Back
開講学期
／Semester		 2018年度／Academic Year 　4学期 ／Fourth Quarter
対象学年
／Course for;		 1st year
単位数
／Credits		 4.0
責任者
／Coordinator		 Yutaka Watanobe
担当教員名
／Instructor		 Yutaka Watanobe, Yan Pei, Jie Huang, Wenxi Chen, Wanming Chu, Qiangfu Zhao
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/12/15
授業の概要
／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, Sort I
3 Data Structures
4 Search I, Hash
5 Recursion, Divide and Conquer
6 Sorting II
7 Tree
8 Binary Search Tree
9 Heap
10 Dynamic Programming
11 Graph
12 Graph Algorithms
13 Heuristic Search
14 String Matching
教科書
／Textbook(s)		 Textbooks
Thomas H. Cormen, Introduction to Algorithms 1.

Supplementary reader
Thomas H. Cormen, Introduction to Algorithms 2.
Y. Watanobe, Algorithms and Data Structures for Programming Contest.
成績評価の方法・基準
／Grading method/criteria		 Assignment 50%
Examination 50%
履修上の留意点
／Note for course registration		 Formal prerequisites:P1 Intro.Programming or P2 C Programing
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Couse Web Site
http://web-int.u-aizu.ac.jp/course/alg1/

Web Site for exercises
https://onlinejudge.u-aizu.ac.jp/

References
Thomas H. Cormen, Charles E. Leiserson,  Ronald L. Rivest, Clifford Stein, Introduction to Algorithms (MIT Press).
Robert Sedgewick, Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms.

Office hours
Office hours will be provided on the course Web site.


Back
開講学期
／Semester		 2018年度／Academic Year 　4学期 ／Fourth Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Hirohide Demura
担当教員名
／Instructor		 Hirohide Demura, Shigeo Takahashi, Anh T. Pham, Takeaki Sampe
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2018/06/26
授業の概要
／Course outline		 This course “Information Theory and Data Compression” gives knowledge and basic skills as follows. Transmitting information efficiently and accurately is one of the important technical challenges in the modern digital society. Information theory is rooted in mathematical formulation and provides a theoretical solution to this problem. The idea of ​​information theory makes it possible to construct an efficient coding for information communication and error correction by utilizing the probability and the statistical theorem. Information theory plays an important role in fields such as image data compression, cryptology theory, network communication, information quantity evaluation, etc.
授業の目的と到達目標
／Objectives and attainment
goals		 The main contents of this course are mathematical formulation of source coding and channel coding, efficient construction method of coding, and entropy for measuring information ambiguity and information volume. This course includes basis of probability and statistics.
授業スケジュール
／Class schedule		 # 1 Guidance, About the information theory
# 2 Conditional Probability and Law of Large Numbers
# 3 Instantaneous code
# 4 Code space
# 5 Source coding theory · Huffman code
# 6 Various source codings
# 7 Entropy
# 8 Mutual information
# 9 Maximum likelihood decoding
# 10 Hamming distance
# 11 Channel Coding Theory
# 12 Hamming code
# 13 Generator matrix
# 14 Primitive polynomial
教科書
／Textbook(s)		 Introduction to information theory based on examples  (in Japanese)
ISBN 978-4-06-153803-0
Shinichi Oishi (1993) Kodansha
成績評価の方法・基準
／Grading method/criteria		 ・Final exam 50%
・Quiz/Exercise 50%
履修上の留意点
／Note for course registration		 N/A
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 N/A


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

更新日／Last updated on 2018/02/23
授業の概要
／Course outline		 "Discrete Systems (DS)" is called "Discrete Mathematics". This course
deals and analyzes mathematically various discrete events and objects,
and has been developed as mathematical concept and fundamental
methodology for computer and its networks, programming and
algorithms. In that sense, course DS is mathematical foundation for
computer science and technology, and has many fundamental studies and
various applications. In the freshmen of University education, DS is
completely different from "Linear Algebra" and "Calculus". DS is
universal infrastructure and common language to represent modern ICT
(Information and Communication Technology).
授業の目的と到達目標
／Objectives and attainment
goals		 As described in "Course Outline", DS is mathematics for Computer
Science and Engineering, and is supporting foundation of modern ICT.
Objectives of this course is that students can understand and
represent various discrete events (phenomena) using DS as a universal
language and infrastructure. Moreover, students are recommended to
implement programs using theories studied in DS.
授業スケジュール
／Class schedule		 Students will study in the following four lecture classes and six
exercise sessions.

       Sugiyama   Mori           Lubashevsky     K.Asai
       C1,C2         C3,C4        C5,ITCG             C6
       M5                M6              M7                        M8
       Tue,Fri         Mon,Thu    Mon,Thu             Mon,Thu
       7,8,9            6,7,8           6,7,8                    6,7,8

     Exercise classes and assigned professors (room)

C1: M.Sugiyama (M5)
C2: N.Asai (M6)
C3: K.Mori (M6)
C4: Y.Watanabe(M9)
C5: I.Lubashevsky(M7)
C6: K.Asai(M8)

Contents of lecture and Exercise are constructed 4 Blocks with 14
sessions.

The first block "Basic" contains "Set and Logic", "Functions" and
"Relations", which are fundamentals for further study in
DS. Operations for subsets, set family contains set elements, injection
(one-to-one mapping) and surjection, definition and representation of
binary relation, equivalent relation and set partition. It is necessary
for students to understand and apply this "Basic".

The second block "Counting and Combinatorics" contains basic property
of integers, recursive definition and counting of events and
objects. "Module calculation" covers basic property and calculation of
integer module, "Recursion and Induction" covers principle of
mathematical induction, recursive definition, In "Combinatorics"
covers principles of sum and product, pigeon hole principle,
permutation and combination, various counting techniques.

The third block "Graph theory" contains general idea of graphs and
applications of graphs. Practical events and relations are represented
and understood using concept of graphs. "Basics of Graphs" covers
fundamental notions of graph theory; vertex, edge, face and path,
fundamental properties of graphs, and matrix representation of graphs
for computation implementation. "Directed graphs (DAG)" covers graphs
with direction (orientation) to represent more practical
modeling. "Planar graphs" covers Euler's theorem and polyhedron
theorem. Finally "Trees" covers tree structures as a special case of
graphs.

The fourth block "Order, Logic, Boolean algebra" contains abstract
"Order" relation which is analogy of order property for numbers.
"Lattice" is introduced as a special partially ordered set which has
algebraic structure with two binary operations. "Logic" and "Boolean
algebra" covers elementary logic and propositional calculus. "Boolean
algebra" is a special type of lattice, and related to construction of
switching circuits.

   1. Basic (3 lectures)
     - Set Theory and Logic
     - Functions
     - Relations

   2. Counting and Combinatorics (2-3 lectures)
     - Modulo calculation
     - Recursion and Induction
     - Combinatorics

     Mid-term exam (optional)

   3. Graph theory (4-5 lectures)
     - Basics of Graphs
     - Directed graphs (DAG)
     - Planar graphs
     - Tree

   4. Order, Logic, Boolean algebra (3-4 lectures)
     - Order
     - Lattice
     - Logic
     - Boolean algebra
教科書
／Textbook(s)		   Prof. M.Sugiyama's class
    S.Lipschutz, Theory and Problems of Discrete Mathematics, Ohmsha.
    
  Prof. K.Mori's class
    Texts not specified.  Necessary materials will be distributed in the
    class.

  Prof. I.Lubashevsky's class

  Prof. K.Asai's class
    Handouts delivered
成績評価の方法・基準
／Grading method/criteria		   Doing or not doing mid-term exam and grading methods are different
  professor by professor. If you have any questions, please contact to
  your class professor.

  The followings are current grading methods of each class.

  Prof. M.Sugiyama's class
     Exams (70%), [Mid-exam(30%)，Final-exam(40%)], Exercise (30%)

  Prof. K.Mori's class
     Midterm exam 30%, Final exam 40%, Exercises 30%

  Prof. I.Lubashevsky's class
     Midterm exam 30%, Final-exam 40%, Home work 30%

  Prof. K.Asai's class
    By Final Exam. and Exercise. (More than 80% of homework
    assignments should be submitted.) Full score of Final Exam. is
    approx. 150 points. The raw score "p" is converted to a scaled score
    "s" by the formula: s=75+(p-75)/3+e (p>75), s=p+e (p≦75) (in
    principle). Here, "e" is Exercise score, which is added up to s=80.
履修上の留意点
／Note for course registration		   Doing or not doing mid-term exam and grading methods are different
  professor by professor.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		   Prof. M.Sugiyama's class
    http://web-int.u-aizu.ac.jp/~sugiyama/Lecture/DS/2017/welcome.html

  Prof. K.Mori's class

    Seymour Lipschutz, Hiroshi Narushima, "Discrete Mathematics",
    Ohmsha. translated version (Revised Third Edition)

    Seymour Lipschutz, Marc Lipson, "Discrete Mathematics", Series of
    Schaum's Outline Series, Fundamental Mathematics in Computer
    Science, McGraw Hill.

  Prof. I.Lubashevsky's class

  Prof. K.Asai's class
    Directory for Asai's class: ~k-asai/classes/disc/
    Handouts and Exercises for Asai's class:
    http://web-ext.u-aizu.ac.jp/~k-asai/classes/class-texts.html


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

更新日／Last updated on 2017/12/13
授業の概要
／Course outline		 Logic circuit design is a design process in digital VLSIs such as processors. The main objective of logic circuit design is to design functional requirements implemented on digital VLSIs using logic variables which take 0 or 1 and logic operations (AND, OR, NOT). Not only circuits are designed from a specification correctly but also it is necessary to design optimum circuits to satisfy design requirements such as cost and performance.
授業の目的と到達目標
／Objectives and attainment
goals		 In lectures, students study the basic knowledge, design method, and optimization method
for logic circuit design. In exercises, students design logic circuits from specification
such as truth table using a schematic editor. In addition, students verify whether the
designed circuits are correct or not by using a logic simulator.

The goals of this course are as follows:
1. Students can design the minterm cannonical disjunctive form from truth tables
2. Students can minimize two-level logic functions using Karnaugh map
3. Students can design sequential circuits using finite state machine
授業スケジュール
／Class schedule		 1. Introduction
2. Representation of numbers
3. Boolean algebra
4. Two-level logic minimization using Karnaugh map
5. Various representations of logic functions
6. Delay and performance of logic circuits.
7. Mid-term examination
8. Combinational circuits 1
9. Combinational circuits 2
10. Memory logics
11. Design of sequential circuits
12. Design of sequential circuits using finite state machine
13. Summary
14. Others
教科書
／Textbook(s)		 Not assigned
成績評価の方法・基準
／Grading method/criteria		 Mid-term examination 20%
Final examination 40%
Reports 40%

No re-examination


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

更新日／Last updated on 2017/12/14
授業の概要
／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		 (Lecture)
1. Introduction (Chapter 1)
2. Performance evaluation (Chapter 1)
3. Instruction set & assembly language (Chapter 2)
4. Instruction set & assembly language 2 (Chapter 2)
5. Arithmetic for computer: addition, subtraction, ALU, etc (Chapter 3)
6. Arithmetic for computer2: multiplication, division, floating point (Chapter 3)
7. Datapath (Chapter 4)
8. Controller (Chapter 4)
9. Pipeline (Chapter4)
10. Pipeline 2: hazards (Chapter 4)
11. Memory hierarchy: cache (Chapter 5)
12. Memory hierarchy: virtual memory (Chapter 5)
13. Storage & other I/Os:, RAID, etc (Chapter 5 +α)
14. Parallel processor: SIMD/MIMD, Vector processors, etc (Chapter 6)

(Exercise)
1. Introduction
2. Assembly Programming Language (Basic instructions only)
3. Assembly Programming Language (Develop a multiply routine using immediate instructions）
4. Assembly Programming Language (JAL and sub-routine call)
5. Understand mechanisms of RF and ALU（Confirm using a simulator）
6. Develop a simple CPU and confirm its behavior using basic instructions
7. Develop a simple CPU and confirm its behavior using the multiply rotine developed in Ex. 3
8. Develop a simple CPU and confirm its behavior using the program calling sub-routines, which is developed in Ex. 4
9. Reserve day for catching up delay of Ex 5-7, and review
10. Pipeline (Solve ex. problems in the textbook)
11. Cache (Solve ex. problems in the textbook)
12. Vertual memory (Solve ex. problems in the textbook)
13. Integrated final exercise 1 (or Ex for multicore, or review of previous exercises. Depending on the progress of the class)
14. Integrated final exercise 2 (or Ex for multicore, or review of previous exercises. Depending on the progress of the class)
教科書
／Textbook(s)		 Computer Organization and Design - The Hardware/Software Interface. David. A. Patterson and John L. Hennessy, 5th edition, Morgan Kaufmann Publishers, ISBN 0124077269

Course website:
Will be announced in the first class
成績評価の方法・基準
／Grading method/criteria		 Final examination(50%), Exercise report(50%). (No makeup examination)
履修上の留意点
／Note for course registration		 Prof. Ben's class: The lecture will be offered in English

Courses should be taken before taking this course:
-Introduction to Computer Systems
-Logic circuit design

Related courses
-Operating Systems
-Parallel Computer Architecture
-Embedded Systems
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Related literature
“HDLによるVLSI設計―VerilogHDLとVHDLによるCPU設計　第2版” 深山正幸　他著


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

更新日／Last updated on 2017/12/12
授業の概要
／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		 2018年度／Academic Year 　4学期 ／Fourth Quarter
対象学年
／Course for;		 2nd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Taro Suzuki
担当教員名
／Instructor		 Taro Suzuki, Mohamed Hamada, Kazuyoshi Mori
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/12/14
授業の概要
／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 recognizers
   and grammars as generators 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

5. understand the relation between automata and grammars
授業スケジュール
／Class schedule		 Although class schedule depends on professors, each professor deals with the following topics (the order depends on professors).

1. Introduction

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. We deal with finite automata(FA) and pushdown automata(PDA). Three classes of finite automata (deterministic finite automata(DFA), nondeterministic finite automata(NFA), nondeterministic finite automata with empty moves(λ-NFA, also known as ε-NFA)) and their relationship is explained. We also deal with minimization of DFAs.

3. Grammars

Grammars and languages generated by them are explained in detail. Following four types of grammars and languages are explained: regular grammars(RG) and regular languages(RL), context-free grammars(CFG) and context-free languages(CFL). We deal with regular expressions(RE) as an expression of regular languages. Normal forms of context-free grammar (Chomsky normal form(CNF) and Griebach Normal form(GNF) are also explained.

4. Relationship between Automata and Grammars

We learn relationship between automata and grammars as the devices to describe languages. Correspondences between finite automata and regular grammars, pushdown automata and context-free grammars are explained,

5. The Hierarchy of Language Classes

We establish a hierarchy among language classes and show 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.

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.

Class schedule for each professor is as follows.

Kazuyoshi Mori
1,2.
Mathematical Introduction. Introduction to Languages and their
Operations. Introduction to Automata and Grammars.
3,4,5.
Finite Automata (FA) (Deterministic (DFA), Nondeterministic (NFA), and
Nondeterministic with ε-moves (ε-NFA)). Regular Languages(RL).
Relationship between DFA, NFA, and ε-NFA Languages which not Regular
(Pumping Lemma). Minimization of Deterministic Finite Automata.
6,7.
Pushdown Automata (PDA)(Deterministic (DPDA) and Nondeterministic (NPDA)).
Context-Free Languages (CFL). Languages which not Context-Free (Pumping
Lemma for CFL).
8.
Midterm Examination.
9,10,11.
Regular Grammars (RG). Regular Expressions (RE).
Relationship between FA, RG, RE, and RL.
12,13.
Context-Free Grammars (CFG). Relationship between NPDA, CFG, and CFL.
Chomsky Normal Forms (CNF). Griebach Normal Forms(GNF).
14.
Other Computing Models, Grammars, and Languages.
Hierarchy of Language Classes.
Computability and Computational Complexity.

Mohamed Hamada
1. Mathematical background
2. Introduction to Automata and Languages
3. Finite Automata (FA) (deterministic finite automata (DFA) and
   nondeterministic finite automata (NFA)), NFA to DFA conversion
4. Nondeterministic Finite Automata with empty move (λ-NFA) and
   conversion to NFA
5. Regular Expression (RE), RE to λ-NFA conversion, DFA to RE
   conversion
6. DFA Minimization
7. Midterm exam
8. Regular Grammar (RG), Regular Language (RL), Context free grammar (CFG)
   and Context-free language (CFL)
9. Context-free grammar, parsing, and grammar ambiguity
10. Normal forms: Chomsky Normal form (CNF), CFG to CNF conversion,
    Griebach Normal form (GNF)
11. Non-regular languages and Pumping lemma, Non-context free lang. and PL
12. Push down automata (PDA)
13. Conversion between PDA and CFL
14. Introduction to computability

Taro Suzuki
1. Introduction to automata, grammars and language theory
2. Mathematical introduction
3. Deterministic finite automata (DFA)
4. Nondeterministic finite automata (NFA), Nondeterministic finite automata
   with empty moves (λ-NFA)
5. Equivalence of DFA, NFA and λ-NFA
6. DFA Minimization
7. Pushdown automata (PDA)
8. Midterm exam
9. Grammars and languages
10. Classification of grammars (Regular grammars (RG), Context-free
    grammars (CFG), Regular languages (RL), Context-free languages (CFL))
11. Normal forms of Context-free grammars (Chomsky Normal form (CNF),
     Griebach Normal forms (GNF))
12. Correspondences between automata and grammars
13. Hierarchy of Language Classes (Languages which not Regular and Pumping
    Lemma for RL, Languages which not Context-free and Pumping for CFL).
14. Computability and Computational Complexity

The correspondence between classes and topics described above   may be changed according to the progress of the course.
教科書
／Textbook(s)		 No textbook is used. Materials will be distributed from each professor.
成績評価の方法・基準
／Grading method/criteria		 The weights of the final exam is 40%. The other grading methods and criteria depend on professors.

Kazuyoshi Mori.
Midterm exam: 30%  Exercise: 30%

Mohamed Hamada
the class activities: 14% (1% per class)  Midterm exam: 20%  Exercise: 26%

Taro Suzuki
Midterm exam: 30%  Exercise: 30%
履修上の留意点
／Note for course registration		 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.

P. Linz: An Introduction to Formal Languages and
Automata(5 ed.), Jones and Bartlett, 2012.


Back
開講学期
／Semester		 2018年度／Academic Year 　3学期 ／Third 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/12/14
授業の概要
／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 recognizers
   and grammars as generators 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

5. understand the relation between automata and grammars
授業スケジュール
／Class schedule		 Although class schedule depends on professors, each professor deals with the following topics (the order depends on professors).

1. Introduction

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. We deal with finite automata(FA) and pushdown automata(PDA). Three classes of finite automata (deterministic finite automata(DFA), nondeterministic finite automata(NFA), nondeterministic finite automata with empty moves(λ-NFA, also known as ε-NFA)) and their relationship is explained. We also deal with minimization of DFAs.

3. Grammars

Grammars and languages generated by them are explained in detail. Following four types of grammars and languages are explained: regular grammars(RG) and regular languages(RL), context-free grammars(CFG) and context-free languages(CFL). We deal with regular expressions(RE) as an expression of regular languages. Normal forms of context-free grammar (Chomsky normal form(CNF) and Griebach Normal form(GNF) are also explained.

4. Relationship between Automata and Grammars

We learn relationship between automata and grammars as the devices to describe languages. Correspondences between finite automata and regular grammars, pushdown automata and context-free grammars are explained,

5. The Hierarchy of Language Classes

We establish a hierarchy among language classes and show 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.

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.

Class schedule for each professor is as follows.

Kazuyoshi Mori
1,2.
Mathematical Introduction. Introduction to Languages and their
Operations. Introduction to Automata and Grammars.
3,4,5.
Finite Automata (FA) (Deterministic (DFA), Nondeterministic (NFA), and
Nondeterministic with ε-moves (ε-NFA)). Regular Languages(RL).
Relationship between DFA, NFA, and ε-NFA Languages which not Regular
(Pumping Lemma). Minimization of Deterministic Finite Automata.
6,7.
Pushdown Automata (PDA)(Deterministic (DPDA) and Nondeterministic (NPDA)).
Context-Free Languages (CFL). Languages which not Context-Free (Pumping
Lemma for CFL).
8.
Midterm Examination.
9,10,11.
Regular Grammars (RG). Regular Expressions (RE).
Relationship between FA, RG, RE, and RL.
12,13.
Context-Free Grammars (CFG). Relationship between NPDA, CFG, and CFL.
Chomsky Normal Forms (CNF). Griebach Normal Forms(GNF).
14.
Other Computing Models, Grammars, and Languages.
Hierarchy of Language Classes.
Computability and Computational Complexity.

Mohamed Hamada
1. Mathematical background
2. Introduction to Automata and Languages
3. Finite Automata (FA) (deterministic finite automata (DFA) and
   nondeterministic finite automata (NFA)), NFA to DFA conversion
4. Nondeterministic Finite Automata with empty move (λ-NFA) and
   conversion to NFA
5. Regular Expression (RE), RE to λ-NFA conversion, DFA to RE
   conversion
6. DFA Minimization
7. Midterm exam
8. Regular Grammar (RG), Regular Language (RL), Context free grammar (CFG)
   and Context-free language (CFL)
9. Context-free grammar, parsing, and grammar ambiguity
10. Normal forms: Chomsky Normal form (CNF), CFG to CNF conversion,
    Griebach Normal form (GNF)
11. Non-regular languages and Pumping lemma, Non-context free lang. and PL
12. Push down automata (PDA)
13. Conversion between PDA and CFL
14. Introduction to computability

Taro Suzuki
1. Introduction to automata, grammars and language theory
2. Mathematical introduction
3. Deterministic finite automata (DFA)
4. Nondeterministic finite automata (NFA), Nondeterministic finite automata
   with empty moves (λ-NFA)
5. Equivalence of DFA, NFA and λ-NFA
6. DFA Minimization
7. Pushdown automata (PDA)
8. Midterm exam
9. Grammars and languages
10. Classification of grammars (Regular grammars (RG), Context-free
    grammars (CFG), Regular languages (RL), Context-free languages (CFL))
11. Normal forms of Context-free grammars (Chomsky Normal form (CNF),
     Griebach Normal forms (GNF))
12. Correspondences between automata and grammars
13. Hierarchy of Language Classes (Languages which not Regular and Pumping
    Lemma for RL, Languages which not Context-free and Pumping for CFL).
14. Computability and Computational Complexity

The correspondence between classes and topics described above   may be changed according to the progress of the course.
教科書
／Textbook(s)		 No textbook is used. Materials will be distributed from each professor.
成績評価の方法・基準
／Grading method/criteria		 The weights of the final exam is 40%. The other grading methods and criteria depend on professors.

Kazuyoshi Mori.
Midterm exam: 30%  Exercise: 30%

Mohamed Hamada
the class activities: 14% (1% per class)  Midterm exam: 20%  Exercise: 26%

Taro Suzuki
Midterm exam: 30%  Exercise: 30%
履修上の留意点
／Note for course registration		 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.

P. Linz: An Introduction to Formal Languages and
Automata(5 ed.), Jones and Bartlett, 2012.


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

更新日／Last updated on 2017/10/24
授業の概要
／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		 2018年度／Academic Year 　1学期 ／First Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Nobuyoshi Asai
担当教員名
／Instructor		 Nobuyoshi Asai, Yuichi Yaguchi, Konstantin Markov, Taro Suzuki, Yong Liu, Yen Neil Yuwen
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2018/02/28
授業の概要
／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, 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;
            07 - Midterm Exam.
Lecture 08 - Algorithm Design Techniques: Greedy Algorithms;
Lecture 09 - Algorithm Design Techniques: Divide-and-Conquer;
Lecture 10 - Algorithm Design Techniques: Dynamic Programming;
Lecture 11 - Algorithm Design Techniques: Backtracking;
Lecture 12 - Random Number Generators;
Lecture 13 - Randomized Algorithms;
Lecture 14 - Models of Computations.
教科書
／Textbook(s)		 T. H. Carmen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms 3rd Ed. (MIT Press, ISBN-10: 0262033844, ISBN-13: 978-0262033848, soft cover: ISBN-10: 0262533057, ISBN-13: 978-0262533058)
or its Japanese translation:
T. H. Carmen, C. E. Leiserson, R. L. Rivest, C. Stein, 浅野 哲夫 (訳),‎ 岩野 和生 (訳),‎ 梅尾 博司 (訳),‎ 山下 雅史 (訳),‎ 和田 幸一 (訳)アルゴリズムイントロダクション 第3版(世界標準MIT教科書)近代科学社,  第1巻: 基礎・ソート・データ構造・数学(ISBN-10: 4764904063, ISBN-13: 978-4764904064), 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム（ISBN-10: 4764904071, ISBN-13: 978-4764904071）, または総合版 (ISBN-10: 476490408X, ISBN-13: 978-4764904088)
成績評価の方法・基準
／Grading method/criteria		 Asai, Yaguchi class:
Lab. Exercises: 50%;
Mid-Term Exam: 25%;
Final Exam: 25%;

Markov class:
Lab. Exercises: 40%;
Mid-Term Exam: 30%;
Final Exam: 30%;
履修上の留意点
／Note for course registration		 The knowledge and skill of the following classes are required:
Linear Algebras 1, 2,
Discrete Systems,
Programming C,
and the following classes are preferred to have been taken:
Algorithms and Data Structures 1
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 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);


Reference (coursewebsite, literature, etc.)
Course Website: http://hare.u-aizu.ac.jp/classaa/2018  (N. Asai class)  


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

更新日／Last updated on 2017/12/12
授業の概要
／Course outline		 Languages processing is a fundamental and vital subject in computer science. It is a subject which has been studied intensively since the early 1950’s and continues to be an important research field today. Languages processing is an important part of the undergraduate curriculum for many reasons:
1. It provides students with a better understanding of and appreciation for       programming languages.
2. The techniques used in languages processing can be used in other applications with command languages.
3. It provides motivation for the study of theoretic topics.
授業の目的と到達目標
／Objectives and attainment
goals		 Students understand the role of languages processing systems such as compilers and translators, the processing methods of languages, the importance of compilers, and the relation between theory and practice (that is, formal language theory and languages processing systems).
授業スケジュール
／Class schedule		 1. Introduction to compiler and interpreter
2. Anatomy of the compiler and compiler structure
3. Introduction to Lexical Analysis, regular expression and regular definition
4. Lexical Analysis and finite automata
5. LEX tools for automatic generation of lexical analyzer
6. Syntax analysis and top-down parsing techniques
7. Syntax analysis and bottom-up parsing techniques
8. Midterm exam
9. YACC tools for automatic generation of syntax analyzer
10. Semantics analysis: Abstract syntax tree and scope
11. Semantics analysis: symbol table and type checker
12. Intermediate representations and intermediate code generation
13. Introduction to abstract machine and code generation
14. Final review
教科書
／Textbook(s)		 Several book recommendations and other reading materials will be described in lectures
成績評価の方法・基準
／Grading method/criteria		 Class activities: 14 %
Exercise: 26 %
Midterm exam: 20 %
Final Exam: 40 %
履修上の留意点
／Note for course registration		 Automata theory
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Will be given in lecture


Back
開講学期
／Semester		 2018年度／Academic Year 　4学期 ／Fourth Quarter
対象学年
／Course for;		 3rd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Yohei Nishidate
担当教員名
／Instructor		 Yohei Nishidate, Kohei Kitazato, Yong Liu
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2017/12/13
授業の概要
／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 nonlinear system of equations

Week 4: Linear Algebraic Equations
- Vectors and matrices
- Gauss elimination
- 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:  Mid-term Examination

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 for one-dimensional problems
- One-dimensional elements
- Galerkin method
- Variational formulation
- Finite element equations

Week 14: Review
教科書
／Textbook(s)		 Lecture notes.
成績評価の方法・基準
／Grading method/criteria		 Exercises 50%.
Midterm examination 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.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 数値で学ぶ計算と解析,金谷健一,共立出版.


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

更新日／Last updated on 2017/12/07
授業の概要
／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, Integration Test, and System Test
Exercise : Development & Test
Day 14
Lecture : Summary & Future Perspective
Exercise : Development & Test Phase – Feedback & Self-check
教科書
／Textbook(s)		 Handouts for each lecture and exercises will be downloadable from course web-sight.
Related reading material will be instructed during lectures.
成績評価の方法・基準
／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.
*Final exam will include problems to check understanding of the exercise topics as well.
履修上の留意点
／Note for course registration		 * All exercises should be performed individually (Is not team work).
*Discussions with fellow students is recommended, but copying of work of others is strictly prohibited and will be penalized.
*Students are requested, if necessary, to self-study necessary knowledge and skills (including, details of UML, Java, Astah) outside of course hours.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 http://borealis.u-aizu.ac.jp/classes/se1
Moodle http://sealpv0.u-aizu.ac.jp:20000/


Back
開講学期
／Semester		 2018年度／Academic Year 　2学期 ／Second Quarter
対象学年
／Course for;		 2nd year
単位数
／Credits		 3.0
責任者
／Coordinator		 Evgeny Pyshkin
担当教員名
／Instructor		 Evgeny Pyshkin, Maxim Mozgovoy, Julian Villegas, Wanming Chu, Yen Neil Yuwen, Kenta Ofuji
推奨トラック
／Recommended track		 －
履修規程上の先修条件
／Prerequisites		 －

更新日／Last updated on 2018/05/21
授業の概要
／Course outline		 This is an introductory course among the disciplines focused on different aspects of data management. In this course, we introduce major concepts of data presentation, acquisition and processing, and give primary understanding of information management to the students, to let them have a necessary background for selecting further specialized courses in this domain.
The course is focuses on representing the following conceptual units (please see the class schedule for implementation details):
- Foundation Concepts necessary for introducing basic data management principles;
- Data modeling approaches, implementation and practical use;
- Methods and organization of data storage, versioning, distribution and backup;
- Accessing and storing data with using database systems and specialized data management systems.
授業の目的と到達目標
／Objectives and attainment
goals		 The objective of this course is to introduce data management as a research and technology domain with its distinct agenda, to explain data models and modeling approaches used in present-day information systems. A particular emphasis will be made on real-life daily scenarios of data modeling, storage, and retrieval methods. The course will serve as a basis for subsequent specialized courses such as Database management systems, or Operating systems.
After course completion the students will have the following learning outcomes:
- Understanding concepts of information and data.
- Knowledge about genesis of information systems and ability to create entity-relationship data models.
- Understanding data representation levels and ability to develop conceptual and physical data models.
- Ability to determine which information management methods and/or techniques are appropriate for a given problem or within the given subject domain.
- Understanding data lifecycle phases and necessary techniques relevant to a particular phase.
- Understanding a concept of metadata, knowledge about existing metadata standards and ability to use appropriate metadata formats.
- Understanding a concept of persistent data structure, knowledge about existing approaches for managing stored data and ability to deploy and use version control systems.
- Understanding approaches, models and conventions for data sharing, storage and reuse.
- Understanding object-oriented models of data and processes ad ability to use modeling tools (UML).
- Understanding the models and concepts used to build structured data storage systems, such as databases.
授業スケジュール
／Class schedule		 Class 1. Introducing the course. Foundation Concepts.
Understanding information. What is data? How data and information are connected. Clustering and classification. Information systems. Research data lifecycle. From data to knowledge.
Data and metadata. What is metadata? Metadata standards and examples. Connection to data lifecycle.
Data processing. Basic information storage and retrieval concepts. Understanding acquisition, representation, digitalization, processing and transformation.
Intro to entity-relationship models.

Class 2.  Entity-Relationship Model.
Intro to data modeling. Understanding data modeling. Why do we create models?
Entity Relationship model (ER model): purpose, limitation, major elements. Mapping natural language. ER model in use.
Creating an ER model. From subject domain to information system vision.
Example of ER modeling: course registration system.

Class 3. Data Modeling (part 1).
Data modeling and abstraction, data and information storage: concepts, mechanisms, implementations.
Data modeling foundations. Conceptual models (entity-relationship) revisited. Relational data models. Object-oriented data models.
Connection to the project lifecycle and software engineering activities.
UML Basics.

Class 4. Data Modeling (part 2).
Object-oriented modeling and unified models.
Modeling languages and tools (e.g. UML). Semi-structured data models. Introduction to XML. UML modeling scopes. UML Diagrams.

Class 5. Persistent Structures and Versioning.
Persistence and versioning. Persistence types: partial, full, confluent, functional.
Version control systems for software developers. Motivation and three generations of VCSs. Typical operations and workflow. The problem of binary data versioning.
Introduction to continuous integration: build server + task manager + repository. The review of available tools and systems. Usage examples from our own practice.

Class 6. Version Control Systems
Version control systems. Repositories. Repository operations. Approaches: centralized (SVN) and distributed (Mercurial).
Organization of a workplace. Typical scenarios for data storage, search, organization of knowledge.

Class 7. Introduction to Database Systems (part 1).
Representing, accessing and storing data.  
File systems. Databases. Database generations.
Data representation abstractions. Data models revisited.

Class 8. Introduction to Database Systems (part 2).
Major approaches to building databases. Evolution of database systems. Data modeling and database design. Relational vs. object-oriented database design. Query languages. Storage and indexing. Query processing. Transaction processing.

Class 9. Specialized data management.
Specialized data management software: reference management (bibtex, Citavi, etc.)
Notebook organizer (OneNote). Mindmapping software (Freemind). Webpages organizer (WebResearch).

Class 10. Spreadsheets.
Spreadsheets as a data organization and management instrument.  Basic functions of spreadsheet software. Typical use cases and application areas.

Class 11. Data Backup Concepts and Techniques.
Practical backup techniques. Types of backup (incremental, differential, mirror).
Common backup software: rsync, syncthing, etc. Backup scheduling (cron, Windows Scheduler).
Backing up data to a remote location. Reliability of data media. Cloud backups. Advantages and disadvantages of cloud backup & sync services (Google drive, OneDrive, Dropbox). Installable Dropbox-like systems (Seafile, ownCloud).

Class 12. Data Storage Concepts and Techniques.
Data process. Data lifecycle phases. Consider your goals. What data are you collecting? How do you plan to keep this data? What do you need to be able to use it and share it later? Why and how to backup your data? Types of backups: incremental, differential, mirror. Redundant data storage methods. RAID arrays. Reliability of data media (flash memory, HDD, CD/DVD, tapes).
Practical data storage techniques. Difference between reliable storage and backup. Common RAID array types. Why RAID is not a substitute for a backup? Building your own RAID with available components. Software RAIDs.
Organization of a workplace. Typical scenarios for data storage, search, organization of knowledge.

Class 13. Data Models and Software.
Information systems as socio-technical systems. Human-centric development as a response to societal problem. Understanding data science and engineering. Software. Abstract data type. Data retrieval.
Human-centric development as a response to societal problem. Understanding data science and engineering.

Class 14. Optional topics. Course Summary.
Data and digital transformation.
Quality issues: reliability, scalability, efficiency, effectiveness.
Course summary: What we have learned.

教科書
／Textbook(s)		 Please see the course web page.
成績評価の方法・基準
／Grading method/criteria		 The final grade is calculated based on the following weights:
- Quizzes on lecture material – 30%
- Exercises and individual projects – 30%
- Bonus points for active participation in classroom activities – 10%
- Final test – 30%

Students who successfully performed both the lecture quizzes and the individual exercises with a score higher than 75% of possible maximum score may be allowed not to take the final test with automatic maximum score designation for the final test.
履修上の留意点
／Note for course registration		 This course is based on Programming.Intro and C.Programming delivering primary knowledge of programmable computational process and data type concepts. We also expect that the students have basic understanding of algebraic models studied in the courses of discrete mathematics.
参考(授業ホームページ、図書など)
／Reference (course
website, literature, etc.)		 Course web page: http://web-int.u-aizu.ac.jp/~pyshe/courses/idm/

We use our Moodle server to support the course. All necessary instructions are given on the course web page.

MIT Libraries Data Management. RES.STR-002 Data Management. Spring 2016. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

UML Resource Page // http://www.uml.org.

Introduction to Object Orientation and UML // http://www.agiledata.org/essays/objectOrientation101.html.


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

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