シラバス参照

講義概要/Course Information

2024/05/02 現在

科目基礎情報/General Information

授業科目名 /Course title (Japanese)	応用ネットワーキング論１
英文授業科目名 /Course title (English)	Ｎｅｔｗｏｒｋ　Ａｐｐｌｉｃａｔｉｏｎｓ　１
開講年度 /Academic year	2019年度	開講年次 /Year offered	全年次
開講学期 /Semester(s) offered	前学期	開講コース・課程 /Faculty offering the course	博士前期課程、博士後期課程
授業の方法 /Teaching method	講義	単位数 /Credits	2
科目区分 /Category	選択科目
開講類・専攻 /Cluster/Department	情報ネットワークシステム学専攻
担当教員名 /Lecturer(s)	森田　啓義
居室 /Office	東2-615
公開E-mail /e-mail	morita@uec.ac.jp
授業関連Webページ /Course website	http://www.appnet.is.uec.ac.jp/%7Emorita/ThemesJ.html
更新日 /Last update	2019/03/11 16:42:56	更新状況 /Update status	公開中 /now open to public

講義情報/Course Description

講義の狙い、目標	[講義の目標] インターネットや大規模な計算機システムを流れる膨大なディジタル情報データの性質，ならびに，生成された情報データを処理するさまざまなアルゴリズムの仕組みとその性能について主に情報理論ならびに計算機科学の立場から論じる．それにより，習得した情報データの捉え方や処理アルゴリズムの性能評価法が，個々の事例へ柔軟に適用でき，また新たな応用へと発展できる力を養う． The aims of this course are to: - overview new trends of application networking services. - acquire systematic knowledge on algorithms and systems to generate various   kinds of network data, including video stream. - learn the methodology and fundamentals of network information transfer. - develop an ability to create new applications of network. Topics to be discussed in the class will be picked up from a variety of fields such as multimedia streaming, traffic models, information data analysis, fundamentals of information transfer, optimization theory, image and signal processing, network coding, and tree structures on network. [講義内容] 今年度は，情報システムにおける最も基本的なデータ構造である文字列を取り上げる．文字列は有限アルファベットの要素を一列に並べたデータとして表現されるが，データ長が大きくなればなるほど，文字列処理の基本である検索，照合，保存といった処理をいかに効率良く行うかが重要な課題になる．これらの処理については古くから研究が進められているが，近年，計算量の観点から従来法を上回る優れた手法がつぎつぎに提案されている．この新たな展開に焦点をあててつつ，漸近的なアルゴリズムの解析法や自らのグループで開発したものも含め，代表的な文字列処理アルゴリズムを紹介する． In the 2018 summer semester, we will be concerned with a class of strings which is one of the most fundamental data structures in information systems.  A string  is defined as a series of elements in a finite set called alphabet.  The most important issues related on strings is how to efficiently deal with most fundamental manipulations; string searching, string matching, and string sorting.  There is a long history of these manipulations or algorithms of strings which have been developed by many researchers so far.  And recently, new algorithms which are superior to the conventional ones have been successively proposed.   With focusing these algorithms,  some string processing algorithms including ones developed by our group will be discussed.
内容	The plan of lectures is given as follows: [Contents] 01 Data Processing = Sorting, Searching, and Matching 02 Lempel-Ziv Algorithms as an Example of Searching Algorithm 03 Suffix Trees and Suffix Array 04 Burrows-Wheeler transform (BWT) as an Example of Sorting 05 LF mapping 06 Searching on Suffix Tray = Suffix Tree + Suffx Array 07 Fully Indexable Dictionary 08 FM-index 09 Wavelet Matrix 10 LCP Array 11 Construction of Suffix Array 12 Induced Sorting 13 Compressed Fully Text Search 14 MFW Array and Antidictionary 15 Contruction MFW Array Each lecture will be given with writing contents on the blackboard.  Some materials will be distributed in the class room.  The order of topics and their contents might be changed for the convenience of audience.
教科書、参考書	[教科書] とくになし．基本的に板書による．必要に応じて資料を配布する． No textbooks.  Some materials will be distributed in the class. [参考書] G. Navarro, Compact Data Structures, Cambridge Univ. Press, 2016. T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. John Wiley & Sons., 2006. [演習] 講義の都度，簡単な演習を課す． Homework for a few exercises will be given in every week.
予備知識	アルゴリズムとデータ構造の基礎知識があることが望ましいが，必須ではない． basic knowledges of algorithms and data structures would be preferable.
演習	毎回のレポート課題（プログラム演習含む）により，講義内容を復習し，理解を深めること． Homework for a few exercises with programming will be given in every week.
成績評価方法 および評価基準	毎回の演習レポートの成績（6割）と最終レポート（4割）で評価 Home works (60%) and final exam (40%).
その他 /Others	[その他] C または Pythonのプログラムが読めるがあることが望ましいが必須ではない． It would be preferable to read programs written in C or tyhon, but not necessary.
キーワード /Keywords	Suffix Trees, Suffix Array, Full Text Search, Data Compression,  Minimal Forbidden Words,