2017/09/20 |
Back |
開講学期 ／Semester |
2017年度／Academic Year 前期 ／First Semester |
---|---|
対象学年 ／Course for; |
2nd year |
単位数 ／Credits |
4.0 |
責任者 ／Coordinator |
Yutaka Watanobe |
担当教員名 ／Instructor |
Jie Huang, Taro Suzuki, Wenxi Chen, Yutaka Watanobe, Yodai Watanabe, Yen Neil Yuwen, Yan Pei |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
P1 or P2 |
更新日／Last updated on | 2017/01/30 |
---|---|
授業の概要 ／Course outline |
Computers are machines that manipulates information. Fundamental study of computer science includes the problems how information is organized in the computer, how it can be manipulated, and how it can be utilized. The efficiency of programming and data processing is directly linked to algorithms and the structures of the data being processed. Thus, it is crucial for students of computer science to understand the concepts of information organization, information manipulation and algorithms. In this course, students learn a range of algorithms and data structures as well as how to implement them through programming exercises. |
授業の目的と到達目標 ／Objectives and attainment goals |
Students will be able to evaluate the strengths and weaknesses of data structures and algorithms as well as to develop efficient algorithms. In addition, the students will be able to apply the state-of-the-art of data structures and algorithms for solving problems and developing software. The aim of the exercises is to solve practical problems under limited resources and know from experience that the efficiency of an algorithm is much more important than that of hardware. Acquired knowledge and techniques will be used for their state-of-the-art research and software development in the future. |
授業スケジュール ／Class schedule |
1 Introduction 2 Analysis of Algorithms 3 Array, Lists 4 Stack, Queue 5 Recursion, Divide and Conquer 6 Sorting I 7 Sorting II 8 Searching 9 Tree 10木 Binary Tree 11 Heap 12 Hash 13 Graph 14 Graph Algorithms 15 Dynamic Programming |
教科書 ／Textbook(s) |
Textbooks Thomas H. Cormen, Introduction to Algorithms 1 and 2. Robert Sedgewick, Algorithms in C 1 and 2. Supplementary reader Y. Watanobe, Algorithms and Data Structures for Programming Contest. |
成績評価の方法・基準 ／Grading method/criteria |
Attendance 10% Assignment 40% Examination 50% This syllabus only contains basic information of this course. For more details about text books, course schedule, student evaluation, please follow the course instructors. |
履修上の留意点 ／Note for course registration |
Formal prerequisites:P1 Intro.Programming or P2 C Programing |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
http://www.u-aizu.ac.jp/course/alg1/ http://web-int.u-aizu.ac.jp/course/alg1/ http://judge.u-aizu.ac.jp/ |
Back |
開講学期 ／Semester |
2017年度／Academic Year 後期 ／Second Semester |
---|---|
対象学年 ／Course for; |
2nd year |
単位数 ／Credits |
2.0 |
責任者 ／Coordinator |
Shigeo Takahashi |
担当教員名 ／Instructor |
Shigeo Takahashi, Hirohide Demura, Mohamed Hamada |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
F3 |
更新日／Last updated on | 2017/01/30 |
---|---|
授業の概要 ／Course outline |
Efficiently and accurately transmitting information is one of the most important technical problem in modern digital society. Information theory provides a theoretical solution to this problem in the sense that it emerges from clear mathematical formulation. Ideas of information theory allows to compose efficient codes for compression and error correction by taking advantage of probability and statistical theorems. This subject is quite important because information theory plays a fundamental role in the fields of image data compression, cryptography, network communication, information content measurement, etc. |
授業の目的と到達目標 ／Objectives and attainment goals |
The primary challenge of this course lies in understanding the mathematical formulations of information source coding and communication channel coding and effective methods for composing such codes, together with the concept of entropy that measures unpredictability of information or information content. Fundamentals of probability and statistics are also converted in this course. |
授業スケジュール ／Class schedule |
* Sets, probability, means and variances, * Conditional probability, Markov processes * Information source coding, Instantaneous codes, * Craft's inequality, uniquely decodable codes * Mean code length, entropy, Information source coding theorem * Huffman coding, compact coding * Markov information source, Shannon diagram, Ergodicity * Run-length code, Ziv-Lempel code * Information content, Characteristics of Entropy * Conditional entropy, mutual information * Channel capacity, binary symmetric channel, maximum-likelihood method * Hamming distance, Channel coding * Channel coding theorem * Parity check, rectangular code, triangle code * Hamming coding, generator matrix, parity check matrix, syndrome * Primitive polynomial, generator polynomial |
教科書 ／Textbook(s) |
Shin-ichi Oishi, "Introduction to Information Theory with Examples (in Japanese (Rei ni motoduku jouhouriron nyuumon)", Kodansha. |
成績評価の方法・基準 ／Grading method/criteria |
Mid-term exam(1/3), final exam(1/3), quizzes and so on(1/3). |
履修上の留意点 ／Note for course registration |
No prerequisite. |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
http://www.u-aizu.ac.jp/~shigeo/course/it/ (Shigeo Takahashi) |
Back |
開講学期 ／Semester |
2017年度／Academic Year 前期 ／First Semester |
---|---|
対象学年 ／Course for; |
2nd year |
単位数 ／Credits |
3.0 |
責任者 ／Coordinator |
Lothar M. Schmitt |
担当教員名 ／Instructor |
Masahide Sugiyama, Lothar M. Schmitt, Kazuto Asai, Kazuyoshi Mori, Igor Lubashevskiy |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
－ |
更新日／Last updated on | 2017/01/31 |
---|---|
授業の概要 ／Course outline |
This course is an introduction to Discrete Mathematics. The subject is important for computer scientists and engineers since almost all computer structures are based on discrete bits. (1) In Logic and Set Theory, the most fundamental concepts of mathematical thinking (elementary logic, sets and mathematical propositions) and basic operations on them are introduced. This yields the structures of Boolean lattices/algebras and propositional calculus. This topic is important for computing since any theoretical argument or model uses this formalism. Examples for applications: using Boolean lattices to simplify computer hardware circuits; using theoretical arguments to design fast computer algorithms. Partition of sets into disjoint subsets (equivalence classes) is also studied. Examples for applications: information classification; computer-reconstruction of noisy images. (2) In Relations and Functions, binary relations and their expression via 0/1-matrices are studied. We study properties of relations such as reflexivity, symmetry and transitivity, order, the composition of relations and corresponding matrix expressions. This includes the study of equivalence relations and classes (see above) which have important applications in computing. Examples: automatic information-clustering (in fuzzy logic and control); automatic simplification of computer programs. Ordered structures are important for understanding information storage and access in computers. The study of relations leads to the study of functions which are a special type of relation. For functions, injectivity, surjectivity, bijectivity are studied. As a consequence of studying bijective (invertible) functions, one can define the cardinality of sets and, in particular, countable sets. Examples for applications: estimating/counting steps in a computation; the study of logic and its consequences for computing such as the following AI question: `Which theorems can be automatically proven given a system of mathematical rules?' Other types of functions such as characteristic functions are studied. Example for applications: computer control based upon fuzzy logic. (3) In Graph Theory & Automata, we first study basic notions such as the degree of vertices, isomorphisms of graphs, walks in graphs, paths in graphs, or the diameter of a graph. In addition, we study a number of special graphs which occur in models and applications. Graphs can be represented by matrices which is important for their computer implementation. Examples for applications: every computer network or the whole WWW can be seen as graphs; information-linkage can be described by graphs (similarity of DNA structures or writing styles among people). Trees are an important class of graphs. A computer file-directory is a tree. Many company-structures are like a tree. Minimal spanning trees and minimal weighted paths in a graph are studied in this course.] Examples for applications: cost-minimalization in transportation or in production facilities. Automata, a formalization of computer programs and computation, are described by certain types of graphs. The simplification of automata, which yields improved software and hardware performance in computers uses a combination of the above topics such as functions and equivalence relations. (4) Finally, Combinatorics is a topic that is connected to most of the above, in particular, if one wants to determine the number of instances for a particular mathematical structure. Several principles of counting are studied, and basic notions such as binomial coefficients, permutations, combinations, repeated permutations, multinomial expansion, and (ordered) partitions. This includes studying mathematical induction. Combinatorics is important to count and estimate the number of computing steps and computing time in applications. |
授業の目的と到達目標 ／Objectives and attainment goals |
Logic, Set Theory, Boolean algebras, Relations, Order, Functions, Graph Theory, Finite Automata, and Combinatorics. |
授業スケジュール ／Class schedule |
Logic, Set Theory, Boolean algebras, Relations, Order, Functions, Graph Theory, Finite Automata, and Combinatorics. |
教科書 ／Textbook(s) |
[1] Discrete Mathematical Structures. B. Kolman, R.C. Busby, S.C. Ross. Prentice Hall [2] Discrete Mathematics. S. Lipschutz (McGraw-Hill), Translated by Hiroshi Narushima. Ohm-sha. |
成績評価の方法・基準 ／Grading method/criteria |
Attendance (10%). Exercises (20%). Exams (30% Midterm, 40% Final). 2/3 attendance, and 2/3 homework submission are a requirement to pass. |
履修上の留意点 ／Note for course registration |
This is a basic course with essentially high school mathematics as prerequisite. Formal prerequisites: none |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
Discrete Mathematical Structures. / B. Kolman, R.C. Busby, S.C. Ross. / Prentice Hall Int. Inc. Discrete Mathematics (McGraw-Hill). / S. Lipschutz, / translated by Hiroshi Narushima. Ohm-sha. |
Back |
開講学期 ／Semester |
2017年度／Academic Year 後期 ／Second Semester |
---|---|
対象学年 ／Course for; |
2nd year |
単位数 ／Credits |
4.0 |
責任者 ／Coordinator |
Hiroshi Saito |
担当教員名 ／Instructor |
Junji Kitamichi, Yukihide Kohira, Wanming Chu, Satoshi Nishimura, Hiroshi Saito, Abderazek Ben Abdallah, Yoichi Tomioka |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
－ |
更新日／Last updated on | 2017/01/29 |
---|---|
授業の概要 ／Course outline |
Logic circuit design is a design process in digital VLSIs. The main objective of logic circuit design is to design functionalities implemented in a VLSI using logics variables that take 0 or 1 and logic operations (AND, OR, NOT). The term "design" implies that there are good designs and bad designs. Good designs mean optimum designs in terms of cost, performance, and so on. Therefore, designers must consider design optimality so that an optimum logic circuit is designed. |
授業の目的と到達目標 ／Objectives and attainment goals |
The main purpose of this course is to study the basic knowledge, design method, and optimization method for logic circuit design so that students can design an optimum logic circuit from a given specification. In exercises, students design logic circuits from pre-defined specifications. Then, students simulate the designed circuits to verify the correctness of the designed circuits using Cadence software. |
授業スケジュール ／Class schedule |
(Although the schedule is different by lecturers, the most of the course teaches the following contents) 1 Representation of numbers (binary value，positive/negative value，addition/subtraction) 2 Boolean algebra 3 Two-level logic and two-level logic minimization 4 Various representations of logic functions 5 Delays and hazards 6 Combinational circuit designs (Functional units, modular designs) 7 Memory logic designs 8 Sequential circuit designs (Finite state machine，synchronous circuits) 9 Logic verification |
教科書 ／Textbook(s) |
(Depends on instructors) |
成績評価の方法・基準 ／Grading method/criteria |
(Depends on instructors) Saito, H. (Ben, A-B.) Mid-term Exam. 30%, Final Exam. 30%, Reports 40% Nishimura, S. (Chu, W.) Final Exam. 50%, Reports 50% Kohira, Y. (Tomioka, Y.) Mid-term Exam. 25%, Final Exam. 25%, Reports 50% |
履修上の留意点 ／Note for course registration |
Related courses: Discrete Systems，Advanced Logic Circuit Design，Computer Architecture，VLSI Design Formal prerequisites:None |
Back |
開講学期 ／Semester |
2017年度／Academic Year 前期 ／First Semester |
---|---|
対象学年 ／Course for; |
3rd year |
単位数 ／Credits |
4.0 |
責任者 ／Coordinator |
Toshiaki Miyazaki |
担当教員名 ／Instructor |
Wanming Chu, Satoshi Nishimura, Yong Liu, Junji Kitamichi, Toshiaki Miyazaki, Naohito Nakasato, Abderazek Ben Abdallah |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
L4 & F4 |
更新日／Last updated on | 2017/01/26 |
---|---|
授業の概要 ／Course outline |
Students will learn fundamental issues of computer architecture with its design approach, and performance evaluation methods. A computer consists of a central processing unit, memory, I/O devices, and so on. In this course, the students will understand how a computer is established by combining some computing and control units which are composed of logic circuits learned in “Logic Circuit Design” course. More precisely, the students will learn abovementioned issues using MIPS processor as an example. In the exercises, the students will implement a simplified MIPS processor by using CAD (Computer Aided Design) tools such as Cadence. In addition, the students will study how a program runs on a processor through developing some programs using an assembly programming language. |
授業の目的と到達目標 ／Objectives and attainment goals |
1. Understand the main principles of computer architecture. 2. Learn the fundamental of assembly programming. 3. Use CAD tools and a hardware description language, and learn the abstract of processor design |
授業スケジュール ／Class schedule |
1. Introduction 2. Instruction set & assembly language 3. Instruction set & assembly language 2 4. Performance evaluation 5. Arithmetic for computer: addition, subtraction, ALU, etc 6. Arithmetic for computer2: multiplication, division, floating point 7. Datapath 8. Controller 9. Pipeline 10. Pipeline 2: hazards 11. Memory hierarchy: cache 12. Memory hierarchy: virtual memory 13. Storage & other I/Os: RAID, etc 14. Parallel processor: SIMD/MIMD, Vector 15. Parallel processor 2: cache coherency, recent trends, etc |
教科書 ／Textbook(s) |
Computer Organization and Design - The Hardware/Software Interface. David. A. Patterson and John L. Hennessy, 5th edition, Morgan Kaufmann Publishers, ISBN 0124077269 (邦訳）パターソン＆ヘネシー,「コンピュータの構成と設計 第５版 (上), (下)」, 日経ＢＰ社 |
成績評価の方法・基準 ／Grading method/criteria |
Final examination(50%), Exercise report(50%). (No makeup examination) |
履修上の留意点 ／Note for course registration |
[Prof. Liu's class] The lecture will be offered in English |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
Course website: Will be announced in the first class Related literature “HDLによるVLSI設計―VerilogHDLとVHDLによるCPU設計 第2版” 深山正幸 他著 Prerequisites and other related courses which include important concepts relevant to the course Prerequisites: -Introduction to Computer Systems -Logic circuit design Related courses -Operating Systems -Comp. Organ. and Design -Parallel Computer Architecture -Embedded Systems |
Back |
開講学期 ／Semester |
2017年度／Academic Year 後期 ／Second Semester |
---|---|
対象学年 ／Course for; |
2nd year |
単位数 ／Credits |
4.0 |
責任者 ／Coordinator |
Alexander P. Vazhenin |
担当教員名 ／Instructor |
Yong Liu, Alexander P. Vazhenin, Hitoshi Oi, Konstantin Markov, Yohei Nishidate, Peng Li, Kohei Otsuyama, Kazuya Matsumoto |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
L4 |
更新日／Last updated on | 2017/01/28 |
---|---|
授業の概要 ／Course outline |
Operating systems are an essential part of any computer system. Similarly, a course on operating systems is an essential part of any computer-science education. The operating system provides certain services to programs and to the users of those programs in order to make the programming task easier. In this course, four parts of the core of operating systems will be mainly learned. They are process management, memory and storage management, file system management, and I/O system management. Also, some abstract concepts such as cooperation of multi-process and deadlock will be discussed. We do not concentrate on any particular operating system or hardware. Instead, we discuss fundamental concepts that are applicable to a variety of systems. We present a large number of examples that pertain specifically to UNIX and to other popular operating systems. |
授業の目的と到達目標 ／Objectives and attainment goals |
1. To learn the concepts about OS. 2. To get the knowledge about process management, including process concept, inter-process communication, and CPU scheduling. 3. To learn memory management including page management and virtual memory. 4. To learn the design and implementation of file system. 5. To get the knowledge about software and hardware of I/O system. |
授業スケジュール ／Class schedule |
1. Operating System Concepts and Components Topics to study: OS Concepts Computer-system components Evolution Steps OS Components OS Services 2. PROCESSES Topics to study: Process Concept Process States and Scheduling Operations on Processes Cooperating Processes Threads Inter-process Communication 3. CPU Scheduling Topics to study: Basic Concepts Scheduling Criteria Scheduling Algorithms Algorithm Evaluation Conclusion 4. Process Synchronization and Deadlocks Topics to study: Background Critical Section Problem Semaphores Classical Problems Necessary Conditions of Deadlocks Resource Allocation Graph Deadlock Prevention Deadlock Avoidance Deadlock Detection Recovery from a Deadlock 5. Memory Management Topics to study: Background Logical versus Physical Address Space Swapping Contiguous Allocation Paging Model of Logical and Physical Memory Implementation of a Page Table Multilevel Paging Inverted Page Table Segmentation: Basic Methods Segmentation with Paging Demand Paging Performance of Demand Paging Page Replacement Algorithms Allocation Frames Thrashing Demand Segmentations 6. File Management Topics to study: File-System Concepts File Attributes File Operations and Access Methods Directory Structure and Implementation Protection Mechanizm File-System Organization Allocation Methods Free-Space Management Directory Implementation Efficiency and Reliability Mass-Storage Management 7. Distributed Systems Topics to study: Background Motivation Topology Network Types Communication Strategies Design Strategies |
教科書 ／Textbook(s) |
1. Modern Operating Systems, by Andrew S. Tanenbaum, Prentice-Hall, Inc. 2. Operating System Concepts, 5-9, A. Silberschatz and P. B. Galvin, John Wiley & Sons, Inc. 3. Materials and handouts provided by instructors |
成績評価の方法・基準 ／Grading method/criteria |
This policy is used by all course instructors. Final examination, midterm, experimental reports, and class participation. Exercises: 40 points Quiz, Midterm + Exam: 60 points Reports about results of exercises should be submitted in one week after each exercise. The later submission leads to decreasing the number of points as follows: The submission later than one week will reduce points to 50%, The submission later than two weeks will reduce points to 25%, The submission later than four weeks will reduce points to 10%. |
履修上の留意点 ／Note for course registration |
Computer Architecture or Computer Organization, Basic Algorithms and Data Structures, Programming I (C or C++) or Java Formal prerequisites:L4 Intro. Computer Systems |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
1. Course WWW-site: http://sealpv0.u-aizu.ac.jp/moodle/ 2. 「オペレーティングシステム」前川 守著 岩波書店 ISBN4000103466 |
Back |
開講学期 ／Semester |
2017年度／Academic Year 前期 ／First Semester |
---|---|
対象学年 ／Course for; |
3rd year |
単位数 ／Credits |
3.0 |
責任者 ／Coordinator |
Subhash Bhalla |
担当教員名 ／Instructor |
Subhash Bhalla, Wanming Chu, Maxim Mozgovoy |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
－ |
更新日／Last updated on | 2017/02/01 |
---|---|
授業の概要 ／Course outline |
A tabular (relational) model of a data is created. The model aims at understanding the users, Programmers and implementation level difficulties. The course prepares the participants to become system engineers, designers, and software developers. The first part, explains relational theory and query languages for databases. Second part contains a study of database management system. |
授業の目的と到達目標 ／Objectives and attainment goals |
Database systems are commonly used for information Systems. The course covers system architecture, and database design. It also covers the relational database systems technology. It provides knowledge of application development and experiments of working with relational databases. Concepts related to web data, knowledge and information extraction, and Data Mining are explained. Most of the study uses detailed examples and class exercises. |
授業スケジュール ／Class schedule |
1 Apr 7 Data Model+Operations 1-30 1,3 help exercises + HomeWork 2 Apr 14 Datbase Query Languages31-60 3,4 Model Database + Homework 3 Apr 21 Relational Algebra 61-90 4 Database I + HW 4 May 12 Relational Calculus 91-136 4 DatabaseII + HW 5 May 19 Dictionary and storage 61-136 2 Design of a Database + HW 6 May 26 Storage Indexing 136-165 Complete Hw + Ex ( Part I ) -----------------------Mid-Term exam ( May 26 )-------------------------- 7 Jun 2 Objects - Relations 1-20 5 startup(PostgreSQL O-RDBMSs) 8 Jun 09 Data Integrity 21-40 8 loading database 9 Jun 16 DBMS Architecture 41-60 1,2 simple SQL queries 10Jun 23 SQL - Programming 61-80 3 complex SQL queries 11Jun 30 Relational databases 81-100 4 SQL functions and procedures 12Jul 7 Views,XML,O-RDBMS 100-120 22 Database modifications 13Jul 14 Postgres Internals 120-140 10 Web database programming 14Jul 21 Web Data 140-160 10 Complete Hw + Ex ( Part II) 15Jul 28 Postgres APIs 160-190 |
教科書 ／Textbook(s) |
Database Systems Concepts, 6th edition, by Korth, H.A., Silberschatz, A., and Sudershan, S., McGrawHill Book Co., 2010. Fundamentals of Database Systems, 7th Edition, by Ramez Elmasri, Shamkant B. Navathe, 2016 , Pearson |
成績評価の方法・基準 ／Grading method/criteria |
Mid-term Examination(30 points); Two short quizzes (40 points (20 points each)) Database Programming Assignments(30 points) |
履修上の留意点 ／Note for course registration |
Prerequisites Subject(s): Algorithms and Data Structures I and II, Computer Programming I |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
link for slides/handouts and exercise sheets, Course material, OHPs and notes recommended by the instructor(s). |
Back |
開講学期 ／Semester |
2017年度／Academic Year 1学期 ／First Quarter |
---|---|
対象学年 ／Course for; |
3rd year |
単位数 ／Credits |
3.0 |
責任者 ／Coordinator |
Taro Suzuki |
担当教員名 ／Instructor |
Kazuyoshi Mori, Mohamed Hamada, Taro Suzuki |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
－ |
更新日／Last updated on | 2017/01/30 |
---|---|
授業の概要 ／Course outline |
Theory of automata and languages is one of the most fundamental fields of theory of computing. The core concept is to obtain the method to describe infinite sets which are called languages (countable ones are dealt in this field mainly). We study two important systems to describe them: Automata, the recognizing/accepting systems, and Grammars, the generating systems. We study the relation of formal languages through grammars and automata. We focus on hierarchies of languages. They are standard tools of the well-educated computer scientist, who often uses them to reformulate a problem in an easily solvable form, or to recognize the language that cannot be feasibly handled in general. |
授業の目的と到達目標 ／Objectives and attainment goals |
At the end of the course the student should be able to: 1. know the necessity to describe infinite (countable) sets(= languages) correctly 2. know methods to describe languages, automata as recognizors and grammars as gerarators of them 3. design automata and grammars for languages 4. understand the restriction on the automata and grammars and the hierarchy of describing powers of languages caused by such restriction (Chomsky's hierarchy) 5. understand the relation between automata and grammars |
授業スケジュール ／Class schedule |
1. Introduction First, important items students should know and obey are explained. Then, languages we study in this course is introduced, and automata and grammars as devices for describing languages are generally explained. 2. Automata Automata and languages accepted by them are extensively studied. Especially we deal with following four types of automata: Finite Autonmata, Pushdown Automata, Turing Machine and Linear-bounded Automata. 3. Grammars Grammars and languages generated by them are explained in detail. Following four types of grammars and languages are explained: Regular Grammars and Regular Languages, Context-Free Grammars and Context-Free Languages, Context-Sensitive Grammars and Context-Sensitive Languages, Phrase Structure Grammars and Phrase Structure Languages 4. Relationship among Automata and Grammars Until now, though we studied automata and grammars separately, we can expect that there is some relation between automata and grammars, since they are both the devices to describe languages. Here we establish the correspondences between four types of automata and those of grammars, that is, Finite Autonmata and Regular Grammars, Pushdown Autoamta and Context-Free Grammars, Linear-bounded Automata and Context-Sensitive Grammars, Turing Machine and Phrase Structure Grammars. 5. The Hierarchy of Language Classes We explained there are four classes of languages. We establish a relation called Comsky Hierarchy here. In order to establish the relation, we find some property which every language in one class satisfies, and then using it, we show the existence of a language which does not belong to the class. That is, we explain followings: Properties of Regular Languages and the Existence of Languages which are not Regular, Properties of Context-Free Languages and the Existence of Languages which are not Context-Free, Properties of Context-Sensitive Languages and the Existence of Languages which are not Context-Sensitive. 6. The computability and computational complexity We briefly explain the existence of non-computable problems even if they are formally defined. As an example of such problems, we introduce the Halting Problem. We also briefly explain the introduction of computational complexity and show some topics such as P and NP classes of computational complexity, NP complete class and some examples of NP complete problems. |
教科書 ／Textbook(s) |
It depends on Professors. Each Professor will announce the text book. Students should prepare it by the first meeting of the course. |
成績評価の方法・基準 ／Grading method/criteria |
The evaluation depends on followings: 1. Examination results(Midterm(s), Final) 2. Quizzes and Reports 3. Class activity and attendance Their weights depends on professors. At the first meeting of the class, each professor will explain the evaluation methods. |
履修上の留意点 ／Note for course registration |
Prerequisites and other related courses which include important concepts relevant to the course Students will be expected to have taken F3 Discrete Systems course. Moreover, they are expected to have fundamental knowledge about not only Programming and Algorithms but also Computer hardware and its behavior. Language Processing Systems requires the knowledge studied in this course. Especially, in the first part (lexical analysis and syntax analysis) of a language processing system such as a compiler, the knowledge of automata and grammars is indispensable. Therefore, students who will study Language Processing Systems are strongly recommended to enroll this course. |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. J. L. Hein: Theory of Computation, An Introduction, Jones and Bartlett, 1996. M. Sipser: Introduction to the Theory of Computation, PWS Publishing Co., 1996. N. Pippenger: Theories of Computability, Cambridge Univ. Press, 1997. R. Greenlaw, H. J. Hoover: Fundamentals of the Theory of Computation, Morgan Kaufmann Pubs.Inc., 1998 A. Meduna: Automata and Languages, Theory and Applications, Springer, 1999. J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages, and Computation(3rd ed.), Addison-Wesley, 2006. |
Back |
開講学期 ／Semester |
2017年度／Academic Year 2学期 ／Second Quarter |
---|---|
対象学年 ／Course for; |
4th year |
単位数 ／Credits |
3.0 |
責任者 ／Coordinator |
Nobuyoshi Asai |
担当教員名 ／Instructor |
Nobuyoshi Asai, Konstantin Markov |
推奨トラック ／Recommended track |
CF,CM |
履修規程上の先修条件 ／Prerequisites |
F1 |
更新日／Last updated on | 2017/04/07 |
---|---|
授業の概要 ／Course outline |
The study of algorithms is at the very heart of computer science. This course is intended to teach the advanced computer algorithms and techniques for their design and analysis. After the course the students will have a solid background for this type of activity, as well as for representing algorithms in the format of computer programs. |
授業の目的と到達目標 ／Objectives and attainment goals |
This course will cover (but not limited to) the following contents: algorithms and their complexity, graph algorithms, heaps, B-trees, matrix multiplication, algebraic path problem, special mathematical algorithms, string pattern matching, divide-and-conquer, dynamic programming, recursion, greedy, and algorithm design techniques. |
授業スケジュール ／Class schedule |
Lecture 01 - Algorithms and their Complexity; Lecture 02 - Priority Queue and Heap; Lecture 03 - Graphs and Representations; Lecture 04 - Weighted Graphs; Lecture 05 - Shortest Path Problem; Lecture 06 - Transitive Closure; Lecture 07 - String-Matching Problem; Midterm Exam. Lecture 09 - Algorithm Design Techniques: Greedy Algorithms; Lecture 10 - Algorithm Design Techniques: Divide-and-Conquer; Lecture 11 - Algorithm Design Techniques: Dynamic Programming; Lecture 12 - Algorithm Design Techniques: Backtracking; Lecture 13 - Random Number Generators; Lecture 14 - Randomized Algorithms; Lecture 15 - Models of Computations. |
教科書 ／Textbook(s) |
Robert Sedgewick. Algorithims in C (Addison Wesley Professional, 1990, ISBN:0-201-51425-7) |
成績評価の方法・基準 ／Grading method/criteria |
Lab. Exercises: 60%; Mid-Term Exam: 20%; Final Exam: 20%; (Note: Alterable by the professor in charge of the class.) |
履修上の留意点 ／Note for course registration |
F3 Discrete Mathematics F1 Algorithms and Data Structures Formal prerequisites:F1 Algo.and Data Struct. |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
Course Website: Course Website: <a href="http://hare.u-aizu.ac.jp/classaa/2017">http://hare.u-aizu.ac.jp/classaa/2017/a> 1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms (Addison Wesley Professional, 1974, ISBN:0-201-00029-6); 2. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman(著), 野崎昭弘, 野下浩平(訳)『アルゴリズムの設計と解析I』 (サイエンス社, 1977, ISBN:4-7819-0279-0); 3. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman(著), 野崎昭弘, 野下浩平(訳)『アルゴリズムの設計と解析II』 (サイエンス社, 1977, ISBN:4-7819-0280-4); 4. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC 第１巻 基礎・整列』 (近代科学社, ISBN:4-7649-0255-9); 5. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC 第２巻 探索・文字列・計算幾何』 (近代科学社, ISBN:4-7649-0256-7); 6. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC 第３巻 グラフ・数理・トピックス』 (近代科学社, ISBN:4-7649-0257-5); 7. T. H. Cormen, et al., Introduction to Algorithms, MIT press, 2009.(日本語版：T. コルメン, 他, アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書), 近代科学社, 2013) |
Back |
開講学期 ／Semester |
2017年度／Academic Year 3学期 ／Third Quarter |
---|---|
対象学年 ／Course for; |
3rd year |
単位数 ／Credits |
3.0 |
責任者 ／Coordinator |
Mohamed Hamada |
担当教員名 ／Instructor |
Taro Suzuki |
推奨トラック ／Recommended track |
SD |
履修規程上の先修条件 ／Prerequisites |
F8 |
更新日／Last updated on | 2017/01/23 |
---|---|
授業の概要 ／Course outline |
Language Processing is a basic and mandatory course in computer science. It is studied intensively from the beginning of 1950's, and is still an important research area. This course provides basic methods of language processing and compiler construction through lectures and a project implementing a simple compiler front-end of a tiny language. |
授業の目的と到達目標 ／Objectives and attainment goals |
The objectives of this course are -- to give students ability to use methods of programming language processing in program developments, -- to give students a motivation to learn and study theoretical issues in computer science, -- to develop students' programming skills through a practical programming project. Students who succesively complete this course can learn the following: -- the role of language processors such as compilers and interpreters, -- the importance of compilers, -- methods of compilation of progrraming languages, -- relationship between theories of automata and grammars with the practices of programming language processing. This course provides students with the following ability: -- to understand the nature of programming languages, -- how to handle methods in programming language processing in program developments, |
授業スケジュール ／Class schedule |
The topics covered in lectures: 1. Introduction: the outline of compilers, the structure of compilers, the role of compilers and interpreters in programming languages. 2. Lexical analysis: the role of lexical annalyzers (scanners), lexims(tokens), regular expressions, the definition of lexims with regular expression, an application of finite automata to lexical analysis. 3. Parsing: the role of parsers。top-down parsing, LL(1) parsing, botom-up parsing, LR(1) parsing, syntax-directed translation. 4. Compiler compilers： generation of scanners and parsers, scanner and parser generator tools. 5. Contextual analysis： analysis of contextual information, type checking, symbol tables. 6. Intermediate-code generation： intermediate languages(abstract syntax tree, stack representation, three address code), generation of abstract syntax trees and three address codes, runtime environment. 7. Intermediate-code optimization： simple optimization method 8. Target-code generation：generation of target codes from intermediate codes, target code generator Exercises: 1. a project to implement a simple compiler front-end, which generates an intermediate code (abstract syntax trees). The compiler consists of -- a lexical analyzer, -- a program that maintains symbol tables, -- syntax-directed translator with parsing, contextual analysis and intermmediate-code generation (impmentend by a parser generator). 2. exerceses held in the lecture room to learn LL(1) and LR(1) parsing methods etc. |
教科書 ／Textbook(s) |
Compilers -- from basics of language processors to yacc/lex -- Satoshi Okawa and Taro Suzuki, Kindai-Kagaku-sha, 2008 (in Japanese). |
成績評価の方法・基準 ／Grading method/criteria |
1. requirements (a) the attendance at lectures, (b) middle and final exams (The both are mandatory), (c) the attendance at exercises and the submission of assignments. 2. evaluation Mid-term Exam. 30%, Final Exam. 40%, Exercise 30% -- No make-up examination. |
履修上の留意点 ／Note for course registration |
It is desirable that the students who takes this course have already successfully complete C programming, Java programming I, Algoriths and Data Structures. It is strongly recommmended that the students have completed Automata and Languages. *Formal prerequisites:F8 Automata and Languages |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
Other than the references listed below, the lecturer provides references, handouts, etc. as required. 1. Compiler Design by Bergmann. WCB. Available for free download at http://elvis.rowan.edu/~bergmann/books.html. 2. Compilers -- Principles, Techniques and Tools by M.S. Lam, R. Sethi, J.D. Ullman, and A.V. Aho. Addison-Wesley. (2nd Ed.), 2006 3. Introduction to Compiler Construction in a Java World by B. Campbell, S. Iyer and B. Akbal-Delibas. Chapman and Hall/CRC, 2012. |
Back |
開講学期 ／Semester |
2017年度／Academic Year 3学期 ／Third Quarter |
---|---|
対象学年 ／Course for; |
3rd year |
単位数 ／Credits |
3.0 |
責任者 ／Coordinator |
Yohei Nishidate |
担当教員名 ／Instructor |
Yohei Nishidate, Hameed Saji N. |
推奨トラック ／Recommended track |
CM,BM |
履修規程上の先修条件 ／Prerequisites |
F1 |
更新日／Last updated on | 2017/01/30 |
---|---|
授業の概要 ／Course outline |
This course provides basics of numerical methods. Applications of numerical methods in all main areas of floating-point computing are covered. The course focuses on ideas and techniques that are widely used in Computational Science. |
授業の目的と到達目標 ／Objectives and attainment goals |
Students who successfully complete this course will be able to: demonstrate an understanding of the main numerical methods; develop computer programs based on numerical methods; use methods of numerical analysis in practical problems. |
授業スケジュール ／Class schedule |
Week 1: Introduction. Computer Precision - Introduction to numerical analysis - Floating-point representation - Determination of computer parameters Week 2: Errors of Floating-point Computations - Loss of significance - Error propagation - Function evaluation Week3: Zero of a Function - Bisection method - Newton's method - Newton's method for systems Week 4: Linear Algebraic Equations - Vectors and matrices - Gauss elimination with pivoting - LU decomposition Week 5: Matrix Inversion. Matrix Eigenvalues - Determinant of a matrix - Matrix inverse - Eigenvalues of a matrix. Jacobi diagonalization Week 6: Interpolation and Curve Fitting - Lagrange polynomials - Newton polynomials - Least-squares curve fitting Week 7: Cubic Splines - Interpolating cubic splines - B-splines Week 8: Numerical Differentiation and Integration - Forward difference and central difference - Numerical integration. Trapezoidal rule - Simpson’s rules - Gauss quadrature Week 9: Ordinary Differential Equations - Euler’s method - Predictor-corrector method - Runge-Kutta methods - First-order systems Week 10: Partial Differential Equations - Finite difference method - Laplace equation - Poisson equation - Derivative boundary conditions Week 11: Methods for Sparse Matrices - Matrix storage - Direct solution methods - Iterative methods Week 12: Random Number Generation and Monte Carlo Method - Linear Congruential Generators - Integration by Monte Carlo Method Week 13: Finite Element Method (1) - Galerkin method - Variational formulation - Finite element equations Week 14: Finite Element Method (2) - Discretization - Elements - Triangular element Week 15: Finite Element Method (3) - Isoparametric elements - Assembly and solution of finite element equations. |
教科書 ／Textbook(s) |
Lecture notes. 数値で学ぶ計算と解析,金谷健一,共立出版. |
成績評価の方法・基準 ／Grading method/criteria |
Exercises 50%. In class testing 20% Final examination 30%. |
履修上の留意点 ／Note for course registration |
Prerequisites: C Programming, Algorithms and Data Structures. Related courses: Calculus, Linear Algebra, Java Programming. Formal prerequisites:F1 Algo.and Data Struct. |
Back |
開講学期 ／Semester |
2017年度／Academic Year 3学期 ／Third Quarter |
---|---|
対象学年 ／Course for; |
4th year |
単位数 ／Credits |
2.0 |
責任者 ／Coordinator |
Noriaki Asada |
担当教員名 ／Instructor |
Noriaki Asada |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
－ |
更新日／Last updated on | 2017/01/30 |
---|---|
授業の概要 ／Course outline |
Although the background of data compression technology is information theory and code theory, data compression is frequently used like a black-box software without knowledge of these theories. If fundamental algorithms are known from knowledge of information theory or image compression, there are many difficulties in programming. Goal of this class is to understand fundamentals of data compression and implementation of some data compression programs. |
授業の目的と到達目標 ／Objectives and attainment goals |
Understanding fundamentals of data compression and implementation of some data compression programs. |
授業スケジュール ／Class schedule |
・ Words and history of data compression, Huffman code ・ Huffman code exercise ・ Arithmetic code ・ Arithmetic code exercise ・ Compression with moving window, LZSS ・ LZSS exercise ・ LZW ・ LZW exercise ・ Image compression, DCT ・ DCT exercise ・ Fractal ・ Fractal exercise |
教科書 ／Textbook(s) |
The Data Compression Book, 2nd ed. M. Nelson & J.L. Gailly, M&T Books. |
成績評価の方法・基準 ／Grading method/criteria |
Reports of exercises (100%). |
履修上の留意点 ／Note for course registration |
It is desirable to have knowledge about C language and Information Theory. |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
http://web-int.u-aizu.ac.jp/~asada/class/DC.html |
Back |
開講学期 ／Semester |
2017年度／Academic Year 3学期 ／Third Quarter |
---|---|
対象学年 ／Course for; |
3rd year |
単位数 ／Credits |
2.0 |
責任者 ／Coordinator |
Wenxi Chen |
担当教員名 ／Instructor |
Wenxi Chen |
推奨トラック ／Recommended track |
－ |
履修規程上の先修条件 ／Prerequisites |
－ |
更新日／Last updated on | 2017/01/30 |
---|---|
授業の概要 ／Course outline |
地理情報システム（GIS）やコンピュータグラフィックス（CG）、コンピュータ援用設計（CAD）、パターン認識などでは大量の幾何図形データを高速に処理しなければならない。本科目では、コンピュータでこのような幾何学的な問題を取り扱うための効率的なアルゴリズムとデータ構造の設計と解析を勉強する。 本授業は実世界の問題を提起し、計算幾何学と結びつけ、直観的な考え方から出発し、アルゴリズムを導き出し、適切なデータ構造を用いて問題を解く手法を説明する。 プログラミング宿題の他に、プロジェクト研究課題を設け、計算幾何学知識を活かせて、実際の問題解決へのアプローチを身に付けながら計算幾何学の素晴らしさを楽しむ。 |
授業の目的と到達目標 ／Objectives and attainment goals |
計算幾何学の基本となるデータ構造やアルゴリズムを理解し、具体的な問題に対して応用できるようにする。 |
授業スケジュール ／Class schedule |
第一章 基本概念 主要な幾何学的問題、典型的なデータ構造とアルゴリズムの復習 第二章 線分交差 直交線分と任意線分の交差検出 第三章 凸包 定義と計算方法（直接法、包装法、Graham走査法、逐次添加法等） 第四章 ボロノイ図 定義、性質と構成方法（直接法、逐次添加法、分割統治法、Fortune走査法） 第五章 ドローネ三角形分割 基本概念、関連術語、求め方（正当な三角形分割法、平面双対法、逐次添加法） 第六章 幾何的領域探索 直交領域探索の概念、1と2次元領域探索 第七章 多角形の三角形分割 問題の提起、基本概念、平面走査法 |
教科書 ／Textbook(s) |
Computational Geometry - Algorithms and Applications M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf 著 Springer-Verlag 又はその和訳版 コンピュータ・ジオメトリ－計算幾何学：アルゴリズムと応用 M. ドバーグ、M. ファン・クリベルド、M. オーバマーズ、O. シュワルツコップ 著 浅野 哲夫訳、近代出版社 又は 計算幾何学入門 - 幾何アルゴリズムとその応用 譚学厚、平田富夫 著 森北出版 |
成績評価の方法・基準 ／Grading method/criteria |
宿題 50% プログラミング問題、4回。 プログラムの実装を通じて、計算幾何学のデータ構造とアルゴリズムに関する知識を深める。 又は プロジェクト研究 50% １回。 冬休み期間を利用して、実用性のある課題を提出し、色々なリソースから調査活動を展開し、総合的に実際問題解決へのアプローチを勉強する。 及び 期末試験 50% １回。基本概念についての理解程度を検証する |
履修上の留意点 ／Note for course registration |
先修科目 プログラミング言語（C又はJAVA） データ構造とアルゴリズムの基礎 |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
参考ホームページ 授業用 http://i-health.u-aizu.ac.jp/CompuGeo/index.html 邦文サイト http://www.ise.chuo-u.ac.jp/ise-labs/imai-lab/ http://www.simplex.t.u-tokyo.ac.jp/kika.html 英文サイト http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html http://geometryalgorithms.com/ http://mathworld.wolfram.com/ http://www.diku.dk/hjemmesider/studerende/duff/Fortune/ 参考図書 計算幾何学 浅野哲夫 著 朝倉出版 計算幾何学 今井浩、今井圭子 著 共立出版株式会社 Computational Geometry in C J. O'Rourke 著 Cambridge University Press データ構造（アルゴリズムシリーズ１） 浅野哲夫 著 近代科学社 Algorithm in C, Vol. 2（又は同邦訳版） Robert Sedgewick 著 Addison-Wesley |
Back |
開講学期 ／Semester |
2017年度／Academic Year 1学期 ／First Quarter |
---|---|
対象学年 ／Course for; |
3rd year |
単位数 ／Credits |
3.0 |
責任者 ／Coordinator |
Rentaro Yoshioka |
担当教員名 ／Instructor |
Alexander P. Vazhenin, Incheon Paik, Vitaly V. Klyuev, Rentaro Yoshioka, Yan Pei, Julian Villegas |
推奨トラック ／Recommended track |
CM,SE,CN |
履修規程上の先修条件 ／Prerequisites |
P3 |
更新日／Last updated on | 2017/02/28 |
---|---|
授業の概要 ／Course outline |
Software Engineering is a field concerning technologies and methods related to software development. It is about how software should be built, how they should be managed and includes a wide range of both theoretical and practical knowledge. As the presence of software in our daily life seems only to increase, the importance of software engineering is also increasing. It is also one of the fundamental knowledge of software that any engineer in the IT field should understand. In this course, we first study the processes involved in the making of software and understand how they affect the final product. For each stage of the process, we consider issues that need to be solved and visit related technologies and methods that are available. In presentation of available technologies and methods, the goal is to understand the issues and their representative solutions. Both historical and cutting-edge technologies will be introduced as necessary. We will not cover the differences that arise with different forms of software (such as, embedded, web-based, parallel, etc.) but focus on more general and common aspects. In summary, this course focuses on understanding the knowledge and technology sets comprising Software Engineering. In exercises, to help the understanding of basic knowledge, students will work on concrete exercise problems. Each exercise class covers one stage of the development process, and the work required in each stage will be covered one-by-one. Each exercise is designed with a real-world application in mind it is possible to realize issues that are difficult to notice only by theory and basics. After completing all the exercises, students will experience a typical development process and understand its role and effects. |
授業の目的と到達目標 ／Objectives and attainment goals |
1. Be able to explain the knowledge and technologies involved in Software Engineering 2. Be able to explain the typical stages of a development process and explain their characteristics and issues involved. 3. Be able to develop an application by employing a typical process and model |
授業スケジュール ／Class schedule |
Day 1 Lecture : Introduction to Software Engineering Exercise : Orientation and Requirements Definition 1 Day 2 Lecture: Processes & Requirements Definition Exercise : Requirements Definition 2 Day 3 Lecture : Requirements Definition 2 Exercise : Requirements Phase - Feedback & Self-check Day 4 Lecture : Requirements Definition 3 Exercise : Analysis 1 Day 5 Lecture : Analysis – Architectural Design Exercise : Analysis 2 Day 6 Lecture : Analysis – Architectural Design 2 Exercise : Analysis 3 Day 7 Lecture : Analysis – Architectural Design 3 Exercise : Analysis – Feedback & Self-check Day 8 Lecture : Design – Module Design Exercise : Detailed Design 1 Day 9 Lecture : Design – Modules Design 2 Exercise : Detailed Design 2 Day 10 Lecture : Design – Module Design 3 Exercise : Detailed Design 3 Day 11 Lecture : Programming Exercise : Detailed Design Phase – Feedback & Self-check Day 12 Lecture : Test Exercise : Development & Test Day 13 Lecture : Unit Test Exercise : Development & Test Day 14 Lecture : System Test Exercise : Development & Test Day 15 Lecture : Summary & Future Perspective Exercise : Development & Test Phase – Feedback & Self-check |
教科書 ／Textbook(s) |
Textbook：ソフトウェア工学 Author：岸 知二, 野田 夏子 Publisher：近代科学社 SBN：978-4764905092 |
成績評価の方法・基準 ／Grading method/criteria |
1. Quiz 5% 2. Final Examination 60% 3. Exercise 35% *Exercises are evaluated by the level at which they satisfy the requirements of the task. * Exercises are expected to be submitted during class. The final due date of each exercise is at 24:00 of the day before the next lecture. |
履修上の留意点 ／Note for course registration |
* All exercises should be performed individually (Is not team work). *Absence without lecturer’s permission will be penalized. |
参考(授業ホームページ、図書など) ／Reference (course website, literature, etc.) |
http://borealis.u-aizu.ac.jp/classes/se1 Moodle http://sealpv0.u-aizu.ac.jp:20000/ |