Back

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

更新日／Last updated on	2014/09/27
授業の概要 ／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 and software. 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)	Thomas H. Cormen, Introduction to Algorithms 1 and 2. Robert Sedgewick, Algorithms in C 1 and 2.
成績評価の方法・基準 ／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/~yutaka/courses/algo/ http://judge.u-aizu.ac.jp/onlinejudge/course.jsp

Back

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

更新日／Last updated on	2014/09/27
授業の概要 ／Course outline	“How efficiently and how accurately can we transmit the information.” is one of the most important propositions in modern digital society. "Information theory." is a theoretical solution of this question. Information theory shows clear mathematical solution about both more efficient compression and more accurate transmission code based on only statistical characteristics of information, where information theory is based on probability and statistics theorem. Information theory is widely applied to the field of image data compression, cryptology, satellite communication and so on in the modern society.
授業の目的と到達目標 ／Objectives and attainment goals	As fundamentals of information theory, information amount, information source, entropy, information source coding, communication channel coding, error correction coding, sampling theorem, quantization theory, cryptology and so on are learned.
授業スケジュール ／Class schedule	・Probability and statics, average and variance, conditional probability ・History of information theory ・Instantaneous code, Kraft's inequality, uniquely decodable code ・Average code length, entropy ・Source coding theorem, huffman coding ・Markov source, transition chart, stationary probability ・Run-length coding and ZL coding ・Information quantity, conditional entropy, mutual information ・Channel capacity, binary symmetry channel, maximum likeli-hood decoding ・Error correcting code, parity check, channel coding ・Rectangular code, triangular code, humming code, linear code, cyclic code ・Generation matrix, parity check matrix, syndrome ・Primitive polynomial, code generation polynomial ・Sampling theorem, quantization ・(basics of cryptography, secret and public key cryptography)
教科書 ／Textbook(s)	Sin-ichi Oishi, "Rei ni motoduku jouhouriron nyuumon", Kodansha. Handouts.
成績評価の方法・基準 ／Grading method/criteria	Mid-term exam (30%), final exam (30%), quizzes and so on (40%).
履修上の留意点 ／Note for course registration	F3 Discrete Systems Formal prerequisites:F3 Discrete Systems
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.)	http://web-int.u-aizu.ac.jp/~asada/class/IT.html (Prof. Asada)

Back

開講学期 ／Semester	2014年度／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	2014/09/27
授業の概要 ／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 Hal [2] Discrete Mathematics. S. Lipschutz (McGraw-Hill), translated by Hiroshi Narushima. Ohm-sha.
成績評価の方法・基準 ／Grading method/criteria	Attendance. Exercises. Exams.
履修上の留意点 ／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	2014年度／Academic Year 　後期 ／Second Semester
対象学年 ／Course for;	2nd year
単位数 ／Credits	4.0
責任者 ／Coordinator	Hiroshi Saito
担当教員名 ／Instructor	Robert H. Fujii , Wanming Chu , Satoshi Nishimura , Hiroshi Saito , Naohito Nakasato , Abderazek Ben Abdallah
推奨トラック ／Recommended track	－
履修規程上の先修条件 ／Prerequisites	－

更新日／Last updated on	2014/09/27
授業の概要 ／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	Mid-term/final examination, reports, homework, etc (Depends on instructors)
履修上の留意点 ／Note for course registration	Related courses: Discrete Systems，Advanced Logic Circuit Design，Computer Architecture，VLSI Design Formal prerequisites:None

Back

開講学期 ／Semester	2014年度／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	2014/09/27
授業の概要 ／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	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. 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	- Outline of computer architecture - Instruction set architecture(ISA), Performance evaluation method (2 periods) - MIPS instruction set simple program examples (2 periods) - Operation method on computer (2 periods) - Datapath and Control (2 periods) - Cycle and multi cycle implementation (2 periods) - Pipeline and lightening the hazard (2 periods) - Memory hierarchy(Cache and Virtual memory) (2 periods)
教科書 ／Textbook(s)	Computer Organization and Design - The Hardware/Software Interface. David. A. Patterson and John L. Hennessy, 4th edition, Morgan Kaufmann Publishers, ISBN 0123747503 (In the 4th edition, the multi-cycle implementation issue is not described. Thus, some contents related to the issue in the following 3 edition will be used in the lecture.) Computer Organization and Design - The Hardware/Software Interface. David. A. Patterson and John L. Hennessy, 3rd edition, Morgan Kaufmann Publishers, ISBN 0123706068
成績評価の方法・基準 ／Grading method/criteria	-Liu, Chu Final test(45%), Exercise report(45%), Attendance(10%). (No makeup examination) -Nishimura, Ben Abderazek -Miyazaki, Kitamichi, Nakasato Examination(50%), Exercise report(50%). (No makeup examination)
履修上の留意点 ／Note for course registration	Prerequisites: -Introduction to Computer Systems -Logic circuit design Related courses -Operating Systems -Comp. Organ. and Design -Parallel Computer Architecture -Embedded Systems Formal prerequisites:L4 Intro. Computer Systems F4 Logic Circuit Design
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.)	Course website: Announce in the first class Related literature “HDLによるVLSI設計ーVerilogHDLとVHDLによるCPU設計　第2版” 深山正幸　他著

Back

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

更新日／Last updated on	2014/09/27
授業の概要 ／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 Machanizm 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, 2008. 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	Final examination, midterm, experimental reports, and class participation.
履修上の留意点 ／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	2014年度／Academic Year 　前期 ／First Semester
対象学年 ／Course for;	3rd year
単位数 ／Credits	3.0
責任者 ／Coordinator	Subhash Bhalla
担当教員名 ／Instructor	Subhash Bhalla , Wanming Chu , Maxim Mozgovoy
推奨トラック ／Recommended track	CF,CM,SE
履修規程上の先修条件 ／Prerequisites	－

更新日／Last updated on	2014/09/27
授業の概要 ／Course outline	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.
授業の目的と到達目標 ／Objectives and attainment goals	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.
授業スケジュール ／Class schedule	1 Apr  8  Data Model+Operations  1-30     1,3  help exercises + HomeWork 2 Apr 15  Datbase Query Languages31-60    3,4  Model Database + Homework 3 Apr 22  Relational Algebra     61-90    4    Database I + HW 4 May 13  Relational Calculus    91-136   4    DatabaseII + HW 5 May 20  Dictionary and storage 61-136   2    Design of a Database + HW 6 May 27  Storage Indexing      136-165       Complete  Hw + Ex ( Part I ) -----------------------Mid-Term exam ( May 24 )-------------------------- 7 Jun  3 Objects - Relations     1-20    5    startup(PostgreSQL O-RDBMSs) 8 Jun 10 Data Integrity         21-40    8    loading database 9 Jun 17 DBMS Architecture       41-60   1,2  simple SQL queries 10Jun 24 SQL  -  Programming    61-80    3    complex SQL queries 11Jul  1 Relational databases   81-100   4    SQL functions and procedures 12Jul  8 Views,XML,O-RDBMS     100-120  22    Database modifications 13Jul 15 Postgres Internals    120-140  10    Web database programming 14Jul 22 Web Data              140-160  10  Complete  Hw + Ex ( Part II) 15Jul 29 Postgres APIs         160-190
教科書 ／Textbook(s)	Database Systems Concepts, 6th edition, by Korth, H.A., Silberschatz, A., and Sudershan, S., McGrawHill Book Co., 2010.
成績評価の方法・基準 ／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	Algorithms and Data Structures I and II, Computer Programming I Formal prerequisites:None

Back

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

更新日／Last updated on	2014/09/27
授業の概要 ／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	Week 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. Weeks 2--4. 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. Weeks 5 -- 8. 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 Weeks 9 -- 12. 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. Weeks 13 -- 15. 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.
教科書 ／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. Formal prerequisites:None
参考(授業ホームページ、図書など) ／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. *P. Linz: An Introduction to Formal Languages and Automata(3 ed.), Jones and Bartlett, 2001. *J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages, and Computation(3rd ed.), Addison-Wesley, 2006.

Back

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

更新日／Last updated on	2014/09/27
授業の概要 ／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: http://hare.u-aizu.ac.jp/classaa/2013 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);

Back

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

更新日／Last updated on	2014/09/27
授業の概要 ／Course outline	言語の処理は、コンピュータ科学において基本的かつ必須の科目であり、1950年代初めから精力的に研究され、今日でも重要な研究分野である。 以下のような理由から、この科目は学部のカリキュラムにおいて重要な 位置を占めている。 --言語をより良く理解し正当に評価する能力を養う。 -- プログラムを開発するときに、プログラミング言語処理に用いられる技法を活用することができる。 -- コンピュータ科学の理論的な課題を学ぶ必要性に対する動機付けになる。
授業の目的と到達目標 ／Objectives and attainment goals	コンパイラ、トランスレータなどのプログラミング言語の処理系の役割、コンパイラの重要性、処理の方法などを学ぶ。 さらに、理論と実際との関係(すなわち、オートマトンや文法とプログラミング言語の処理系との関係)を理解する。
授業スケジュール ／Class schedule	本科目は、14回の講義と期末試験からなり、講義では以下の内容を扱う(特に、コンパイラの前半部を重点的に講義する)。 1. 概論: コンパイラの概説。 コンパイラの構成。プログラミング 言語の処理におけるコンパイラの役割。オートマトン言語理論の復習とそれの コンパイラにおける役割 2. 字句解析: 字句解析器(スキャナ)の役割。字句(トークン)。正規表現。 正規表現による字句の定義。有限オートマトンの字句解析への応用。 3. 構文解析:構文解析器(パーザ)の役割。トップダウン構文解析技法。 ＬＬ(k)構文解析。ボトムアップ構文解析技法。ＬＲ(k)構文解析。 構文主導型変換法。 4. コンパイラの自動生成系：スキャナ、パーザの自動生成。自動生成の ためのツール解説。 5. 意味解析： 型の種類、型検査の概要。静的/動的型検査。 6. 中間表現： 中間言語。抽象構文木。有効無閉路グラフ(ＤＡＧ)。制御グラフ。 スタック表現(後置表現)。3番地コード。 7. コード最適化：簡単な最適化技法の紹介 8. コード生成：中間コードからのコード生成。コード生成器。
教科書 ／Textbook(s)	Will be given in Lecture
成績評価の方法・基準 ／Grading method/criteria	評価方法は、担当教員に依存するが、本科目の基本方針は以下の通り。 1. 科目としての要求 o (a) 講義への出席 o (b) 試験(中間試験、定期試験) o (c) 演習への参加、課題の提出 2. 評価 o 再試験の実施は、担当教員に委ねられる。 o 評価方法の詳細は、担当教員に委ねられる。
履修上の留意点 ／Note for course registration	C/Javaプログラミング。データ構造とアルゴリズム、オートマトンと言語理論 履修規程上の先修条件：F8 オートマトンと言語理論 Formal prerequisites:F8 Automata and Languages
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.)	以下の参考書の他に、担当教員が参考書、ハンドアウト、その他の教材の情報を必要に応じて随時提供する。 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 Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, and Alfred V. Aho. Addison-Wesley. Second Edition. ISBN-13: 978-0321486813 ISBN: 0321486811. Pub. Date: 2006/10/15 3. Modern Compiler Implementation in Java by A.W. Appel. ISBN: 0-521-58388-8

Back

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

更新日／Last updated on	2014/09/27
授業の概要 ／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	2014年度／Academic Year 　後期 ／Second Semester
対象学年 ／Course for;	4th year
単位数 ／Credits	2.0
責任者 ／Coordinator	Noriaki Asada
担当教員名 ／Instructor	Noriaki Asada
推奨トラック ／Recommended track	－
履修規程上の先修条件 ／Prerequisites	－

更新日／Last updated on	2014/09/27
授業の概要 ／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 ・Arithmetic code ・Compression with moving window ・Image compression ・Fractal compression
成績評価の方法・基準 ／Grading method/criteria	Reports of exercises. (100%)
履修上の留意点 ／Note for course registration	It is desirable to master Information Theory. Formal prerequisites:None
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.)	URL: http://web-int.u-aizu.ac.jp/~asada/class/DC.html Reference book: "The Data Compression Book", 2nd ed. M. Nelson & J.L. Gailly, M&T Books.