AY 2021 Undergraduate School Course Catalog

### Foundations of CSE

 2022/01/30

開講学期／Semester 2021年度／Academic Year 　4学期 ／Fourth Quarter 1st year 4.0 WATANOBE Yutaka WATANOBE Yutaka, PEI Yan, HUANG Jie, CHEN Wenxi, CHU Wanming, ZHAO Qiangfu － － －
更新日／Last updated on 2021/03/08 Computers are machines that manipulate 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. 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. 1 Introduction2 Analysis of Algorithms, Sort I3 Data Structures4 Search I, Hash5 Recursion, Divide and Conquer 6 Sorting II7 Tree8 Binary Search Tree9 Heap10 Dynamic Programming11 Graph 12 Graph Algorithms13 Heuristic Search14 String Matching TextbooksThomas H. Cormen, Introduction to Algorithms 1.Supplementary readerThomas H. Cormen, Introduction to Algorithms 2.Y. Watanobe, Algorithms and Data Structures for Programming Contest. AA: Algorithm Assignment - Max: 100 pointsPA: Programming Assignment - Max: 120 pointsCE: Coding Examination - Max: 120 pointsPE: Paper Examination - Max: 120 pointsTheory: sqrt(AA × PE)Practice: sqrt(PA × CE)Final Score = sqrt(Theory × Practice) Students should learn Intro. Programming and C Programming. Couse Web Sitehttp://web-ext.u-aizu.ac.jp/course/alg1/Web Site for exerciseshttps://onlinejudge.u-aizu.ac.jp/ReferencesThomas H. Cormen, Charles E. Leiserson,  Ronald L. Rivest, Clifford Stein, Introduction to Algorithms (MIT Press).Robert Sedgewick, Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms.The course instructor Yan Pei has practical work experience. He worked for Neusoft Ltd. (China、CMMI5) and Alpine Electronics Europe D&R GmbH (Germany) for five years, where he attended and led software development projects (million LOC level) and teams, designed core algorithms, and applied for and obtained industrial patents. Based on these experiences, he can deliver lectures on algorithm and complexity, programming, and software engineering, etc.The course coordinator Yutaka Watanobe has practical work experience. Now he is collaborating with Givery Inc. to develop the programming skill check tool which can be useful for personnel assessment, training and education. He has provided a number of problems and related test data as one of main contents. Based on his experience, he can teach a wide range of algorithms and data structures.The course instructor Wenxi Chen has practical working experience. He had worked for Nihon Kohden Industrial Corp. for 5 years where he was involved in R&D of bioinstrumentation, signal processing and data analysis. Based on his experience, he can teach the basis of Algorithms and Data Structures.

開講学期／Semester 2021年度／Academic Year 　3学期 ／Third Quarter 3rd year 3.0 DEMURA Hirohide DEMURA Hirohide, PHAM Tuan Anh, OHTAKE Makiko, LYU Guowei － － －
更新日／Last updated on 2021/02/01 This course “Information Theory and Data Compression” gives knowledge and basic skills as follows. Transmitting information efficiently and accurately is one of the important technical challenges in the modern digital society. Information theory is rooted in mathematical formulation and provides a theoretical solution to this problem. The idea of information theory makes it possible to construct an efficient coding for information communication and error correction by utilizing the probability and the statistical theorem. Information theory plays an important role in fields such as image data compression, cryptology theory, network communication, information quantity evaluation, etc. The main contents of this course are mathematical formulation of source coding and channel coding, efficient construction method of coding, and entropy for measuring information ambiguity and information volume. This course includes basis of probability and statistics, and data compression from viewpoints of coding tree and quantization table. Lecture for Demura’s class (in Japanese)# 1/2 Guidance,  Conditional Probability and Law of Large Numbers# 3/4 Information, Information Source# 5/6 Source Coding# 7/8 Instant Code, Code space# 9/10 Communication Channel# 11/12 Channel Coding Theory# 13/14 Linear CodingLecture for Pham’s class (ITCG in English)#1 Lecture 1:  Course introduction, Intro. to Information Theory#2 Lecture 2:  Errors and Error Detecting Codes#3/4 Lecture 3 – 4: Error Correcting Codes - Repetition and Hamming codes#5/6 Lecture 5 – 6: Data compression & Huffman Code #7/8 Lecture 7 – 8: Probability & Inference Review, Probabilistic Models, Conditional Probability, Bayes’ Rule and Inference, Independence#9 Lecture 9 Independence, Review of Huffman code (for Lab 2)#10/11 Lecture 10-11: Entropy & Source Coding Theorem#12 Lecture 12: Channel & Mutual information Channel/Noisy channel/Channel relationship, Joint prob., system entropies (joint, conditional), chain rule for entropy, Mutual information#13 Lecture 13: Channel Capacity Maximizing mutual information, def. of channel capacity, Capacities of different channels#14 Lecture 14: Channel Coding Theorem The noisy-channel coding theorem (sect. 9.6 – Mackay book), Shannon theorem (10.1 and 6.11)Laboratory Exercise for all classesWe have an exercise class (two periods) a week.Class in Japanese (Profs. Demura and Ohtake)#1 MATLAB activation#2 Information, Information Source#3 Source Coding#4 Mutual information and application of entropy#5 Communication Toolbox 1 (QAM)#6 Communication Toolbox 2 (Error correction in channel coding)#7 Communication Toolbox 3 (Humming Code Generator)ITCG Class in English (Profs. Pham and Lu)#1 Lab 1 (1 session): Matlab tutorial#2 Lab 2 (1 session): Image transmission over binary symmetric channel (BSC)#3 Lab 3 (1 session): Implementation of repetition code (R3) encoder/decoder#4 Lab 4 (1 session): Implementation of Hamming code (7,4) encoder/decoder#5/6 Lab 5 (2 sessions): Implementation of Source coding (data compression) using Huffman code#7 Lab 6 (1 session): Combination of Image transmission over BSC with and without channel and source coders implemented in Lab 1-4 Demura’s class in Japanese : はじめての情報理論稲井 寛(著) 森北出版ISBN：978-4-627-84911-2Pham’s class (ITCG in English): Information Theory, Pattern Recognition, and Neural Networks (English, free)David J. C. MacKay, University of CambridgeISBN: 9780521642989 Final exam 40%, Quiz(2nd-14th lectures) 10%, Exercise 50% The course instructors has working experiences: Instructors are familiar with Information Theory and Data Compression based on telecommunication network design, etc.Communications System Toolbox, MATLABhttps://jp.mathworks.com/help/comm/

開講学期／Semester 2021年度／Academic Year 　2学期 ／Second Quarter 2nd year 3.0 MORI Kazuyoshi ASAI Kazuto, MORI Kazuyoshi, ASAI Nobuyoshi, WATANABE Yodai, LYU Guowei － － Classes C1 to C4 are Japanese.Classes C5 and C6 are English.
更新日／Last updated on 2021/01/27 "Discrete Systems (DS)" is called "Discrete Mathematics". This coursedeals and analyzes mathematically various discrete events and objects,and has been developed as mathematical concept and fundamentalmethodology for computer and its networks, programming andalgorithms. In that sense, course DS is mathematical foundation forcomputer science and technology, and has many fundamental studies andvarious applications. In the freshmen of University education, DS iscompletely different from "Linear Algebra" and "Calculus". DS isuniversal infrastructure and common language to represent modern ICT(Information and Communication Technology). As described in "Course Outline", DS is mathematics for ComputerScience and Engineering, and is supporting foundation of modern ICT.Objectives of this course is that students can understand andrepresent various discrete events (phenomena) using DS as a universallanguage and infrastructure. Moreover, students are recommended toimplement programs using theories studied in DS. Allocation of lecutures and exercises are as follows:Lectures:C1: K.AsaiC2: N.AsaiC3, C4: MoriC5, C6: LubashevskyExercises:C1: K.AsaiC2: N.AsaiC3: MoriC4: WatanabeC5: LubashevskyC6: LuContents of Lecture and Exercise are constructed 4 Blocks with 14sessions.The first block "Basic" contains "Set and Logic", "Functions" and"Relations", which are fundamentals for further study inDS. Operations for subsets, set family contains set elements, injection(one-to-one mapping) and surjection, definition and representation ofbinary relation, equivalent relation and set partition. It is necessaryfor students to understand and apply this "Basic".The second block "Counting and Combinatorics" contains basic propertyof integers, recursive definition and counting of events andobjects. "Module calculation" covers basic property and calculation ofinteger module, "Recursion and Induction" covers principle ofmathematical induction, recursive definition, In "Combinatorics"covers principles of sum and product, pigeon hole principle,permutation and combination, various counting techniques.The third block "Graph theory" contains general idea of graphs andapplications of graphs. Practical events and relations are representedand understood using concept of graphs. "Basics of Graphs" coversfundamental notions of graph theory; vertex, edge, face and path,fundamental properties of graphs, and matrix representation of graphsfor computation implementation. "Directed graphs (DAG)" covers graphswith direction (orientation) to represent more practicalmodeling. "Planar graphs" covers Euler's theorem and polyhedrontheorem. Finally "Trees" covers tree structures as a special case ofgraphs.The fourth block "Order, Logic, Boolean algebra" contains abstract"Order" relation which is analogy of order property for numbers."Lattice" is introduced as a special partially ordered set which hasalgebraic structure with two binary operations. "Logic" and "Booleanalgebra" covers elementary logic and propositional calculus. "Booleanalgebra" is a special type of lattice, and related to construction ofswitching circuits.   1. Basic (3 lectures)     - Set Theory and Logic     - Functions     - Relations   2. Counting and Combinatorics (2-3 lectures)     - Modulo calculation     - Recursion and Induction     - Combinatorics     Mid-term exam (optional)   3. Graph theory (4-5 lectures)     - Basics of Graphs     - Directed graphs (DAG)     - Planar graphs     - Tree   4. Order, Logic, Boolean algebra (3-4 lectures)     - Order     - Lattice     - Logic     - Boolean algebra [K.Asai's class]Handouts delivered.[N.Asai's class]S.Lipschutz, Theory and Problems of Discrete Mathematics, Ohmsha.[Mori's class]Necessary materials to be distributed.[Lubashevsky's class] Doing or not doing mid-term exam and grading methods are differentprofessor by professor. If you have any questions, please contact toyour class professor.The followings are current grading methods of each class.[K.Asai's class]By Final Exam. and Exercise. (More than 80% of homeworkassignments should be submitted.) Full score of Final Exam. isapprox. 150 points. The raw score "p" is converted to a scaled score"s" by the formula: s=75+(p-75)/3+e (p>75), s=p+e (p≦75) (inprinciple). Here, "e" is Exercise score, which is added up to s=80.[N.Asai's class]Exams (70%), [Mid-exam(30%)，Final-exam(40%)], Exercise (30%)[Mori's class]Exams (70%), [Mid-exam(30%)，Final-exam(40%)], Exercise (30%)[Lubashevsky's class]Exams (70%), [Mid-exam(30%)，Final-exam(40%)], Home work (30%) Doing or not doing mid-term exam and grading methods are differentprofessor by professor. [K.Asai's class]Directory for Asai's class: ~k-asai/classes/disc/Handouts and Exercises for Asai's class:http://web-ext.u-aizu.ac.jp/~k-asai/classes/class-texts.html[N.Asai's class]http://hare.u-aizu.ac.jp/DS/2020/index.php[Mori's class]Seymour Lipschutz, Hiroshi Narushima, "Discrete Mathematics",Ohmsha. translated version (Revised Third Edition)Seymour Lipschutz, Marc Lipson, "Discrete Mathematics", Series ofSchaum's Outline Series, Fundamental Mathematics in ComputerScience, McGraw Hill.[Lubashevsky's class]The course instructors have working  experiences:[N.Asai]1997-2000 Researcher, WaveFront Co. Ltd.2002-2003 Visiting researcher, National Institute of Environmental Study2001-2010 Collaborative Research with Asahi Glass CompanyHe has practical work experience at Wave Front Co. Ltd fornumerical simulations, modelings and high performancecomputings from 1997 to 2000. After joined to U. of Aizu, hehas continued with companies on the mentioned topics.  Theseexperiences of designing models, data structure and algorithmsare deeply related with this class topics, or each of thisclass topics is important basic element for practical design.[Mori]1988-1988 Shinko Electric Co.,Ltd.Implementataion of Computer Algebra System, REDUCE, on SELCOS, a computer system for Industrial Control.

開講学期／Semester 2021年度／Academic Year 　3学期 ／Third Quarter 2nd year 4.0 SAITO Hiroshi CHU Wanming, NISHIMURA Satoshi, SAITO Hiroshi, TOMIOKA Yoichi, OKUYAMA Yuichi, KOHIRA Yukihide － － －
更新日／Last updated on 2021/01/18 Logic circuit design is a design process in digital VLSIs such as processors. The main objective of logic circuit design is to design functional requirements implemented on digital VLSIs using logic variables which take 0 or 1 and logic operations (AND, OR, NOT). Not only circuits are designed from a specification correctly but also it is necessary to design optimum circuits to satisfy design requirements such as cost and performance. In lectures, students study the basic knowledge, design method, and optimization method for logic circuit design. In exercises, students design logic circuits from specificationsuch as truth table using a schematic editor. In addition, students verify whether thedesigned circuits are correct or not by using a logic simulator.The goals of this course are as follows:1. Students can design the minterm cannonical disjunctive form from truth tables2. Students can minimize two-level logic functions using Karnaugh map3. Students can design sequential circuits using finite state machine 1. Introduction2. Representation of numbers3. Boolean algebra4. Two-level logic minimization using Karnaugh map5. Various representations of logic functions6. Delay and performance of logic circuits.7. Mid-term examination8. Combinational circuits 19. Combinational circuits 210. Memory logics11. Design of sequential circuits12. Design of sequential circuits using finite state machine13. Summary14. Others Not assigned Mid-term/final examination 60%Reports 40%No re-examination In each class, lectures and exercises are provided by both on-line and on-site styles. To join on-line, students need to run Cadence tools from a remote machine. Follow the instruction from each instructor to run Cadence tools in a remote manner.

開講学期／Semester 2021年度／Academic Year 　1学期 ／First Quarter 3rd year 4.0 BEN ABDALLAH Abderazek CHU Wanming, NISHIMURA Satoshi, NAKASATO Naohito, BEN ABDALLAH Abderazek, KITAMICHI Junji, SUZUKI Daisuke － － －
更新日／Last updated on 2021/01/13 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. Lecture schedule / contents1. Introduction (Chapter 1)2. Performance evaluation (Chapter 1)3. Instruction set & assembly language (Chapter 2)4. Instruction set & assembly language 2 (Chapter 2)5. Arithmetic for computer: addition, subtraction, ALU, etc (Chapter 3)6. Arithmetic for computer2: multiplication, division, floating point (Chapter 3)7. Datapath (Chapter 4)8. Controller (Chapter 4)9. Pipeline (Chapter4)10. Pipeline 2: hazards (Chapter 4)11. Memory hierarchy: cache (Chapter 5)12. Memory hierarchy: virtual memory (Chapter 5)13. Storage & other I/Os:, RAID, etc (Chapter 5 +α)14. Parallel processor: SIMD/MIMD, Vector processors, etc (Chapter 6)Exercise schedule / contents1. Introduction 2. Assembly Programming Language (Basic instructions only) 3. Assembly Programming Language (Develop a multiply routine using immediate instructions）4. Assembly Programming Language (JAL and sub-routine call)5. Understand mechanisms of RF and ALU（Confirm using a simulator）6. Develop a simple CPU and confirm its behavior using basic instructions 7. Develop a simple CPU and confirm its behavior using the multiply routine developed in Ex. 38. Develop a simple CPU and confirm its behavior using the program calling sub-routines, which is developed in Ex. 49. Reserve day for catching up delay of Ex 5-7, and review10. Pipeline (Solve ex. problems in the textbook) 11. Cache (Solve ex. problems in the textbook) 12. Virtual memory (Solve ex. problems in the textbook)13. Integrated final exercise 1 (or Ex for multicore, or review of previous exercises. Depending on the progress of the class)14. Integrated final exercise 2 (or Ex for multicore, or review of previous exercises. Depending on the progress of the class) Computer Organization and Design - The Hardware/Software Interface. David. A. Patterson and John L. Hennessy, 5th edition, Morgan Kaufmann Publishers, ISBN 0124077269 Final examination (50%), Exercise report (50%). (No makeup examination) (Ben class) The lecture will be offered in EnglishRelated courses which include important concepts relevant to the courseCourses should be taken before taking this course:-Introduction to Computer Systems-Logic circuit designRelated courses-Operating Systems-Parallel Computer Architecture-Embedded Systems Course website:Will be announced in the first classRelated literature“HDLによるVLSI設計―VerilogHDLとVHDLによるCPU設計　第2版” 深山正幸　他著 (in Japanese)

開講学期／Semester 2021年度／Academic Year 　4学期 ／Fourth Quarter 2nd year 4.0 VAZHENIN Alexander P. VAZHENIN Alexander P., LIU Yong, OI Hitoshi, MARKOV Konstantin, NISHIDATE Yohei, LI Peng, MATSUMOTO Kazuya － － －

開講学期／Semester 2021年度／Academic Year 　4学期 ／Fourth Quarter 2nd year 3.0 SUZUKI Taro SUZUKI Taro, HAMADA Mohamed, MORI Kazuyoshi － － The course instructors use the language as follows.Kazuyoshi Mori: JapaneseMohamed Hamada: EnglishTaro Suzuki: Japanese
更新日／Last updated on 2021/01/22 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. At the end of the course the student should be able to:1. know the necessity to describe infinite (countable)    sets(= languages) correctly2. know methods to describe languages, automata as recognizers   and grammars as generators of them3. design automata and grammars for languages4. understand the restriction on the automata and grammars and   the hierarchy of describing powers of languages caused by    such restriction5. understand the relation between automata and grammars Although class schedule depends on professors, each professor deals with the following topics (the order depends on professors).1. IntroductionImportant 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. AutomataAutomata and languages accepted by them are extensively studied. We deal with finite automata(FA) and pushdown automata(PDA). Three classes of finite automata (deterministic finite automata(DFA), nondeterministic finite automata(NFA), nondeterministic finite automata with empty moves(ﾎｻ-NFA, also known as ﾎｵ-NFA)) and their relationship is explained. We also deal with minimization of DFAs.3. GrammarsGrammars and languages generated by them are explained in detail. Following four types of grammars and languages are explained: regular grammars(RG) and regular languages(RL), context-free grammars(CFG) and context-free languages(CFL). We deal with regular expressions(RE) as an expression of regular languages. Normal forms of context-free grammar (Chomsky normal form(CNF) and Griebach Normal form(GNF) are also explained.4. Relationship between Automata and GrammarsWe learn relationship between automata and grammars as the devices to describe languages. Correspondences between finite automata and regular grammars, pushdown automata and context-free grammars are explained, 5. The Hierarchy of Language ClassesWe establish a hierarchy among language classes and show some property which every language in one class satisfies, and then using it, we show the existence of a language which does not belong to the class. That is, we explain followings: Properties of Regular Languages and the Existence of Languages which are not Regular, Properties of Context-Free Languages and the Existence of Languages which are not Context-Free.6. The computability and computational complexityWe briefly explain the existence of non-computable problems even if they are formally defined. As an example of such problems, we introduce the Halting Problem. We also briefly explain the introduction of computational complexity and show some topics such as P and NP classes of computational complexity, NP complete class and some examples of NP complete problems.Class schedule for each professor is as follows.Kazuyoshi Mori1,2.Mathematical Introduction. Itroduction to Formal Languageswith Operations of Words and Formal Languages.3,4,5.Finite Automata (FA) (Deterministic (DFA), Nondeterministic (NFA), andNondeterministic with ε-moves (ε-NFA)). Regular Languages(RL).Relationship between DFA, NFA, and ε-NFA.  Non-Regular Languages(Pumping Lemma). Minimization of Deterministic Finite Automata.6,7.Pushdown Automata (PDA)(Deterministic (DPDA) and Nondeterministic(NPDA)).  Context-Free Languages (CFL). Non-Context-Free Languages(Pumping Lemma for CFL).8.Midterm Examination.9,10.Formal Languages.  Regular Grammars (RG).Linear Grammers (LG). Regular Expressions (RE).Relationship between FA, RG, RE, and RL.11,12,13.Context-Free Grammars (CFG).  Derivation tree.  Relationship betweenNPDA, CFG, and CFL.  Chomsky Normal Forms (CNF). Griebach NormalForms(GNF).14.Other Computing Models, Grammars, and Languages.Hierarchy of Language Classes.Computability and Computational Complexity.Mohamed Hamada1. Mathematical background I: Sets, Relations, Functions.2. Mathematical background II: Graphs, Trees, Proof techniques.3. Finite Automata: Deterministic finite automata (DFA) with examples4. Regular expressions, Nondeterministic finite automata (NFA) and NFA toDFA conversion5. Nondeterministic finite automata with empty move (λ-NFA) and conversionto NFA6. Deterministic finite automata to regular expression conversion7. Finite automata minimization8. Midterm exam9. Grammar: Regular grammar (RG) and Context-free grammar (CFG)10. CFG Parsing, and grammar ambiguity11. Normal forms: Chomsky Normal form (CNF), CFG to CNF conversion,    Griebach Normal form (GNF)12. Regular languages, Non-regular languages and Pumping lemma13. Context-free languages and Push down automata (PDA)14. Introduction to Turing machines and computability theoryTaro Suzuki1. Introduction to automata, grammars and language theory.    Mathematical introduction2-4. finite automata: Deterministic finite automata (dfa),       Nondeterministic finite automata (nfa), Nondeterministic       finite automata with empty moves (λ-nfa)5. Equivalence of dfa, nfa and λ-nfa6. Minimization of finite automata7. Pushdown automata (pda)8. Introduction to Grammar9. The Classification of grammars, Mid-term exam10. Regular grammars(rg) and Regular languages(rl),      Context-free grammars(cfg) and context-free languages(cfl),      Normal forms of Context-free grammars (Chomsky Normal form(CNF),      Griebach Normal forms (GNF))11. Transformation of cfgs to CNFs, Correspondences between automata      and grammars12. Correspondences between automata and grammars(continued),      Various presentation of regular languages (right-linear grammars      (rgl), left-linear grammars (lgl), regular expressions)13. Various presentation of regular languages(continued),      Hierarchy of language classes (the existence of non-regular      languages and non-context-free languages, the pumping lemma      for regular languages and for context-free languages)14. Hierarchy of language classes(continued),      Computability and Computational ComplexityThe correspondence between classes and topics described above may be changed according to the progress of the course. No textbook is used. Materials will be distributed from each professor. The weights of the final exam is 40%. The other grading methods and criteria depend on professors.Kazuyoshi Mori.Midterm exam: 30%  Exercise: 30%Mohamed Hamadathe class activities: 14% (1% per class)  Midterm exam: 20%  Exercise: 26%Taro SuzukiMidterm exam: 30%  Exercise: 30% 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. 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 ofComputation, Morgan Kaufmann Pubs.Inc., 1998A. Meduna: Automata and Languages, Theory and Applications,Springer, 1999.J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory,Languages, and Computation(3rd ed.), Addison-Wesley, 2006.P. Linz: An Introduction to Formal Languages andAutomata(5 ed.), Jones and Bartlett, 2012.The course instructors have work experiences:Prof. Suzuki was engaged in the development of language processing systems on Prolog inference machines from 1987 to 1990 at MTC Co.,Ltd. Based on his experience, he can teach the basics of language theory and its relationship with language processing systems.Prof. Mori was engaged in the implementation of REDUCE, a computer algebra system, on SELCOS, a computer system for industrial control at Shinko Electric Co.,Ltd in 1988, where REDUCE runs on RLISP.  Based on his experience he can teach the basics of a theoretical aspect as well as mechanical aspect of computing.

開講学期／Semester 2021年度／Academic Year 　2学期 ／Second Quarter 3rd year 3.0 ASAI Nobuyoshi ASAI Nobuyoshi, YAGUCHI Yuichi, MARKOV Konstantin, SUZUKI Taro, LIU Yong, YEN Neil Yuwen － － －
更新日／Last updated on 2021/02/02 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 which are not covered in Algorithms and Data Structures 1. 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.This course is offered online. This course will cover (but not limited to) the following contents: algorithms and their complexity, graph algorithms, heaps, B-trees, matrix multiplication, algebraic path problem, special mathematical algorithms, divide-and-conquer, dynamic programming, recursion, greedy, and algorithm design techniques. Lecture 01 - Algorithms and their Complexity;Lecture 02 - Priority Queue and Heap;Lecture 03 - Graphs and Representations;Lecture 04 - Weighted Graphs;Lecture 05 - Shortest Path Problem;Lecture 06 - Transitive Closure;            07 - Midterm Exam.Lecture 08 - Algorithm Design Techniques: Greedy Algorithms;Lecture 09 - Algorithm Design Techniques: Divide-and-Conquer;Lecture 10 - Algorithm Design Techniques: Dynamic Programming;Lecture 11 - Algorithm Design Techniques: Backtracking;Lecture 12 - Random Number Generators;Lecture 13 - Randomized Algorithms;Lecture 14 - Models of Computations. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms 3rd Ed. (MIT Press, ISBN-10: 0262033844, ISBN-13: 978-0262033848, soft cover: ISBN-10: 0262533057, ISBN-13: 978-0262533058) or its Japanese translation:T. H. Carmen, C. E. Leiserson, R. L. Rivest, C. Stein, 浅野 哲夫 (訳),‎ 岩野 和生 (訳),‎ 梅尾 博司 (訳),‎ 山下 雅史 (訳),‎ 和田 幸一 (訳)アルゴリズムイントロダクション 第3版(世界標準MIT教科書)近代科学社,  第1巻: 基礎・ソート・データ構造・数学(ISBN-10: 4764904063, ISBN-13: 978-4764904064), 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム（ISBN-10: 4764904071, ISBN-13: 978-4764904071）, または総合版 (ISBN-10: 476490408X, ISBN-13: 978-4764904088) Lab. Exercises: 40%;Mid-Term Exam: 30%;Final Exam: 30%; The knowledge and skill of the following classes are required:Linear Algebras 1, 2,Discrete Systems,Programming C,and Algorithms and Data Structures 1 1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms (Addison Wesley Professional, 1974, ISBN:0-201-00029-6);2. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman(著), 野崎昭弘, 野下浩平(訳)『アルゴリズムの設計と解析I』 (サイエンス社, 1977, ISBN:4-7819-0279-0);3. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman(著), 野崎昭弘, 野下浩平(訳)『アルゴリズムの設計と解析II』 (サイエンス社, 1977, ISBN:4-7819-0280-4);4. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC　第１巻　基礎・整列』 (近代科学社, ISBN:4-7649-0255-9);5. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC　第２巻　探索・文字列・計算幾何』 (近代科学社, ISBN:4-7649-0256-7);6. Robert Sedgewick(著), 野下浩平, 星守, 佐藤創, 田口東(訳)『アルゴリズムC　第３巻　グラフ・数理・トピックス』 (近代科学社, ISBN:4-7649-0257-5);Reference (coursewebsite, literature, etc.)Course Website: http://hare.u-aizu.ac.jp/classaa/2020  (N. Asai class)  (Moodle):http://hi-srv2.u-aizu.ac.jp/ (K. Markov class)Prof. Asai has practical experience at Wave Front Co. Ltd for numerical simulations, modelings and high performance computings from 1997 to 2000. After joined to U. of Aizu, he has continued with companies on the mentioned topics. These experience is deeply related to this class topics of cost of computation, data structure, and algorithms.Prof. Suzuki was engaged in the development of C and Lisp languageprocessing systems implemented on inference machines based on Prolog,developed in the Fifth Generation Computer Systems national projectfrom 1987 to 1990 at Mitsubishi Electric Eastern Computer System Co.Ltd. After joined to U. of Aizu, he has been engaged in the preparationfor the PC Koshien Programming  Division, a programming contest forhigh-school students, since 2012. Prof. Markov has a practical experience at the Advanced Telecommunications Research (ATR) Institute where he worked from 1999 to 2009. This experience includes complex algorithms for search, dynamic programming and optimization which are directly related to the topics of this class.

更新日／Last updated on 2021/01/19 Languages processing is a fundamental and vital subject in computer science. It is a subject which has been studied intensively since the early 1950’s and continues to be an important research field today. Languages processing is an important part of the undergraduate curriculum for many reasons:1. It provides students with a better understanding of and appreciation for       programming languages.2. The techniques used in languages processing can be used in other applications with command languages.3. It provides motivation for the study of theoretic topics. Students understand the role of languages processing systems such as compilers and translators, the processing methods of languages, the importance of compilers, and the relation between theory and practice (that is, formal language theory and languages processing systems). 1. Introduction to compiler and interpreter 2. Anatomy of the compiler and compiler structure 3. Lexical Analysis, regular expression, finite automata and LEX tools4. Syntax analysis and introduction to parsing5. Top-down parsing techniques: predictive parser6. Bottom-up parsing techniques: shifet-reduce parser7. Automatic compiler generator tools: LEX and YACC8. Midterm exam9. Semantics analysis: Abstract syntax tree and scope10. Construction of symbol table11. Type checker and type system12. Intermediate representations and intermediate code generation13. Abstract machine and code generation14. Final review Several book recommendations and other reading materials will be described in lectures Class activities: 14 %Exercise: 26 %Midterm exam: 20 %Final Exam: 40 % Automata theory Will be given in lecture

開講学期／Semester 2021年度／Academic Year 　4学期 ／Fourth Quarter 3rd year 3.0 NISHIDATE Yohei NISHIDATE Yohei, KITAZATO Kohei, LIU Yong － － －
更新日／Last updated on 2021/02/01 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. 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. 1: Introduction. Computer Precision - Introduction to numerical analysis - Floating-point representation - Determination of computer parameters2: Errors of Floating-point Computations - Loss of significance - Error propagation - Function evaluation3: Zero of a Function - Bisection method - Newton's method - Newton's method for nonlinear system of equations4: Linear Algebraic Equations - Vectors and matrices - Gauss elimination - LU decomposition5: Matrix Inversion. Matrix Eigenvalues - Determinant of a matrix - Matrix inverse - Eigenvalues of a matrix. Jacobi diagonalization6: Interpolation and Curve Fitting - Lagrange polynomials - Newton polynomials - Least-squares curve fitting7: Spline Interpolations - Piecewise cubic spline - B-spline8:  Mid-term Examination9: Numerical Differentiation and Integration - Forward difference and central difference - Numerical integration. Trapezoidal rule - Simpson’s rules - Gauss quadrature10: Ordinary Differential Equations - Euler’s method - Predictor-corrector method - Runge-Kutta methods - First-order systems11: Partial Differential Equations - Finite difference method - Laplace equation - Poisson equation - Derivative boundary conditions12: Methods for Sparse Matrices - Matrix storage - Direct solution methods - Iterative methods13: Random Number Generation and Monte Carlo Method - Linear Congruential Generators - Integration by Monte Carlo Method14: Review Lecture notes Prerequisites: C Programming, Algorithms and Data Structures.Related courses: Calculus, Linear Algebra, Java Programming. Exercises 50%.In class testing 20%Final examination 30%. 数値で学ぶ計算と解析,金谷健一,共立出版.

開講学期／Semester 2021年度／Academic Year 　1学期 ／First Quarter 3rd year 3.0 YOSHIOKA Rentaro YOSHIOKA Rentaro, VAZHENIN Alexander P., PAIK Incheon, PEI Yan, VILLEGAS OROZCO Julian Alberto, CHU Wanming － － －
更新日／Last updated on 2021/01/28 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. 1. Be able to explain the knowledge and technologies involved in Software Engineering2. 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 Day 1Lecture : Introduction to Software EngineeringExercise : Orientation and Requirements Definition 1Day 2Lecture: Processes & Requirements DefinitionExercise : Requirements Definition 2Day 3Lecture : Requirements Definition 2Exercise : Requirements Phase - Feedback & Self-checkDay 4Lecture : Requirements Definition 3Exercise : Analysis 1Day 5Lecture : Analysis – Architectural DesignExercise : Analysis 2Day 6Lecture : Analysis – Architectural Design 2Exercise : Analysis 3Day 7Lecture : Analysis – Architectural Design 3Exercise : Analysis – Feedback & Self-checkDay 8Lecture : Design – Module DesignExercise : Detailed Design 1Day 9Lecture : Design – Modules Design 2Exercise : Detailed Design 2Day 10Lecture : Design – Module Design 3Exercise : Detailed Design 3Day 11Lecture : ProgrammingExercise : Detailed Design Phase – Feedback & Self-checkDay 12Lecture : TestExercise : Development & TestDay 13Lecture : Unit Test, Integration Test, and System TestExercise : Development & TestDay 14Lecture : Summary & Future PerspectiveExercise : Development & Test Phase – Feedback & Self-check Software Engineering Theory and Practice, Shari Lawrence Pfleeger and Joane M.Atlee, Prentice HallHandouts for each lecture and exercises will be downloadable from the UoA Moodle site.Related reading material will be instructed during lectures. 1. Quiz 15%2. Final Examination 50%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 23:59 of the day before the next lecture.*Final exam will include problems to check understanding of the exercise topics as well.*Attendance will be checked by submission of quizzes. ・All exercises should be performed individually (Is not team work).・Discussions with fellow students is recommended but copying of work of others is strictly prohibited and will be penalized.・Students are requested, if necessary, to self-study necessary knowledge and skills (including, details of UML, Java, Astah) outside of course hours. Course material, exercise submissions, quiz, and QA are provided through UoA Moodle page.The course instructor has working experiences: A company employee working on development projects will create exercises for each week and provide review and advices to student work throughout the course.A currently active software engineer (with more than 30 years’ experience) and faculty with previous software development experience (including practical software development in industry) will jointly provide lectures and exercises.

開講学期／Semester 2021年度／Academic Year 　2学期 ／Second Quarter 2nd year 3.0 PYSHKIN Evgeny PYSHKIN Evgeny, MOZGOVOY Maxim, VILLEGAS OROZCO Julian Alberto, CHU Wanming, YEN Neil Yuwen, OFUJI Kenta － － －