2016/02/01 |
Back |
開講学期 /Semester |
2015年度/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 | 2015/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 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) |
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/~yutaka/courses/algo/ http://judge.u-aizu.ac.jp/onlinejudge/course.jsp |
Back |
開講学期 /Semester |
2015年度/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 | 2015/01/29 |
---|---|
授業の概要 /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. Basics of coding and channel coding are learned in this class. Furthermore, sampling theorem and basics for quantization in A/D conversion, image compression and some cryptographs are learned. |
授業の目的と到達目標 /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 statistics, mean and variances, conditional probability ・ History of information theory ・ Instantaneous code, Craft’s inequality, uniquely decodable ・ Mean code length, entropy ・ Information source coding theorem, Huffman code ・ Marcov information source, Shannon diagram, ergodic status ・ Run-length code, Ziv-Lempel code, Arithmetic code, Shannon code ・ Information quantity, conditional entropy, mutual information ・ Channel capacity, binary symmetric channel, most likely decode ・ Error correction code, parity check, channel code ・ Rectangular code, triangle code, linear code, cyclic redundancy check code ・ Hamming code, generation matrix, parity check matrix, syndrome ・ Primitive polynomial, generation polynomial ・ Sampling theorem, quantization ・ (Cryptology, secret key cryptography, public key cryptography) ・ (Fouriet transform, DCT, image compression) |
教科書 /Textbook(s) |
Sin-ichi Oishi, “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://web-int.u-aizu.ac.jp/~asada/class/IT.html |
Back |
開講学期 /Semester |
2015年度/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 | 2015/01/26 |
---|---|
授業の概要 /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 |
2015年度/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 | 2015/02/03 |
---|---|
授業の概要 /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 |
2015年度/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 | 2015/01/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 |
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 |
Submit all reports assigned in the exercise. |
参考(授業ホームページ、図書など) /Reference (course website, literature, etc.) |
Course website: Announce in the first class Related literature “HDLによるVLSI設計―VerilogHDLとVHDLによるCPU設計 第2版” 深山正幸 他著 |
Back |
開講学期 /Semester |
2015年度/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 , Kohei Otsuyama |
推奨トラック /Recommended track |
- |
履修規程上の先修条件 /Prerequisites |
L4 |
更新日/Last updated on | 2015/01/25 |
---|---|
授業の概要 /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, 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 |
2015年度/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 | 2015/02/02 |
---|---|
授業の概要 /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 |
Philosophy and characteristics of the subject : 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 |
--------------------------------------------------------------------------- # DATE LECTURE TOPIC OHP Text:CHAP LAB EXERCISES --------------------------------------------------------------------------- 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 29 )-------------------------- 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 ----------------------------------------------------------------------------- The Lecture classes will be held on Tuesdays. Exercises will be on Thursdays. There are 15 lecture and 15 Exercise meetings, as above. |
教科書 /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) |
参考(授業ホームページ、図書など) /Reference (course website, literature, etc.) |
Useful Links: Course link for slides/handouts and exercise sheets References: Books, Course material, OHPs and notes recommended by the instructor(s). |
Back |
開講学期 /Semester |
2015年度/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 | 2015/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 |
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. |
参考(授業ホームページ、図書など) /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 |
2015年度/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 | 2015/02/02 |
---|---|
授業の概要 /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 第1巻 基礎・整列』 (近代科学社, ISBN:4-7649-0255-9); 5. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC 第2巻 探索・文字列・計算幾何』 (近代科学社, ISBN:4-7649-0256-7); 6. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC 第3巻 グラフ・数理・トピックス』 (近代科学社, ISBN:4-7649-0257-5); |
Back |
開講学期 /Semester |
2015年度/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 | 2015/02/02 |
---|---|
授業の概要 /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 -- Evaluation is based on two examinations, exercises held in the lecture room and programming assignments in the project ONLY. -- The evaluation criteria is presented in lectures. -- 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 |
2015年度/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 | 2015/02/02 |
---|---|
授業の概要 /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 |
2015年度/Academic Year 後期 /Second Semester |
---|---|
対象学年 /Course for; |
4th year |
単位数 /Credits |
2.0 |
責任者 /Coordinator |
Noriaki Asada |
担当教員名 /Instructor |
Noriaki Asada |
推奨トラック /Recommended track |
- |
履修規程上の先修条件 /Prerequisites |
- |
更新日/Last updated on | 2015/01/28 |
---|---|
授業の概要 /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. |
履修上の留意点 /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 |
2015年度/Academic Year 後期 /Second Semester |
---|---|
対象学年 /Course for; |
3rd year |
単位数 /Credits |
2.0 |
責任者 /Coordinator |
Wenxi Chen |
担当教員名 /Instructor |
Wenxi Chen |
推奨トラック /Recommended track |
- |
履修規程上の先修条件 /Prerequisites |
- |
更新日/Last updated on | 2015/01/28 |
---|---|
授業の概要 /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% 1回。 冬休み期間を利用して、実用性のある課題を提出し、色々なリソースから調査活動を展開し、総合的に実際問題解決へのアプローチを勉強する。 及び 期末試験 50% 1回。基本概念についての理解程度を検証する |
履修上の留意点 /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 データ構造(アルゴリズムシリーズ1) 浅野哲夫 著 近代科学社 Algorithm in C, Vol. 2(又は同邦訳版) Robert Sedgewick 著 Addison-Wesley |