山梨大学電子シラバス>検索結果一覧>授業データ



授業科目名
担当教員
コンピュータ理工学特別講義V
クップル　ドミニク
時間割番号
単位数
コース
履修年次
期別
曜日
時限
GTK613 2 (未登録) 1 前期 木 II
［概要と目標］
このコースは、修士課程の学生を対象とした完結データ構造に焦点を当てたものであり、
巨大なデータセットを管理するための効率的なデータ構造を設計および実装するための高度な技術とアルゴリズムを紹介する。

学生は基本的なデータ構造の理解を深め、基本的な解決策のスペースおよび時間の効率を向上させる専門技術を学ぶ。
コースでは、ウェーブレットツリー、ブロックツリー、テキストインデックスデータ構造など、さまざまなコンパクトで圧縮されたデータ構造に焦点を当てる。

学生は、高度なデータ構造を効果的に分析、設計、実装するスキルを学習する。
さらに、これらのデータ構造のパフォーマンスを評価し、特定のアプリケーションシナリオに適した構造を選択するスキルも獲得する。
コースは、アルゴリズム解析、理論的および実践的な側面の両方を紹介する。

紹介する知識は、
データ圧縮、情報検索、バイオインフォマティクス、データベースなど、大規模なデータの処理が関連する、多くの分野で活用することができる。
このコースに参加することで、学生は大量のデータを管理し、効率的な解決策を開発するための多様な問題に取り組むことができます。

このコースは、プログラミング競技に参加、あるいは、トップ企業（GAFAM）での採用面接でアルゴリズムのスキルを披露することが求められる学生にとって魅力的であるはずです。

なお、本授業はコンピュータ理工学コースのディプロマポリシーで定めた専門知識・技術(E1)及び(E2)に対応する。

The course on compact data structures is designed for graduate students and focuses on compact and compressed data structures.
This lecture will introduce advanced techniques and algorithms to design and implement efficient data structures for managing massive data sets.

Students will have the opportunity to deepen their understanding of fundamental data structures and learn specialized techniques that improve space and time efficiency of basic solutions.
The course will concentrate on various compact and compressed data structures, for instance wavelet trees, block trees, text indexing data structures, and many more.

Students will be equipped to effectively analyze, design, and implement advanced data structures. Additionally, they will gain the skills to evaluate the performance of such data structures and select appropriate structures for specific application scenarios. The course will try to cover both theoretical and practical aspects, including algorithm analysis, complexity theory, and implementation details.

This course provides students with a solid foundation to succeed in areas such as data compression, information retrieval, bioinformatics, databases, and many other fields where processing huge amount of data is relevant. By participating in this course, students will be able to tackle demanding challenges in managing large volumes of data and develop efficient solutions.

The course should be attractive for students competing in programming competitions, striving to improve their algorithmic know-how for application at top companies (GAFAM), where job interviews usually require showing algorithmic skills.

Note that this course corresponds to the specialized knowledge and skills (E1) and (E2) specified in the Diploma Policy of the Computer Science and Engineering Course.
[到達目標]
1. アルゴリズム・データ構造の効果率を解析するため、領域・時間の計算量を深く理解できる / Understand the space and time complexity of algorithms and data structures to judge their efficiency
2. 多面の問題に対して、適切な抽象データ型を選択できる / Select and combine appropriate abstract data types, data structures, and algorithms to solve complex problems
3. 大規模のデータを対応できる方法の知識 / Know methods to tackle big data problems
4. 関する問題に学んだ方法を応用できる / Able to adapt solutions to related problems
5. 問題に最適に取り組むことができる / Solve problems with optimal methods
6. 圧縮指標に関する計算量でアルゴリズム・データ構造を提案できる / Express complexities of algorithms and data structures in compressed terminology such as repetitiveness measures.
［必要知識・準備］
このコースには、
「TCS207 アルゴリズムとデータ構造I」および「TCS209 アルゴリズムとデータ構造II」での成功した参加を通じて得られる知識が必要である。

The course requires knowledge that can be acquired through successful participation in the courses
TCS207 アルゴリズムとデータ構造I and TCS209 アルゴリズムとデータ構造II.
［評価基準］
No評価項目割合評価の観点
1試験：期末期 25  %議論・発表の前に、個別ゼミで発表について議論 / Argumentation during an individual appointment before the presentation 
2試験：中間期 25  %査読・他人のレポートを評論的に評価 / Peer review of another report 
3小テスト／レポート 25  %レポート・内容を深く理解 / Final report, understanding the presented material in depth 
4発表／表現等 25  %発表・教訓的に内容を説明 / Presentation, didactical break-down 
［教科書］
  1. 定兼邦彦著, 簡潔データ構造, 共立出版, ISBN:9784320121744,
    (2018年出版 アルゴリズム・サイエンスシリーズ / 杉原厚吉 [ほか] 編, 8 ; 数理技法編)

  2. ゴンザロ・ナバロ著 ; 定兼邦彦訳, コンパクトデータ構造 : 実践的アプローチ, 講談社, ISBN:9784065124765,
    (2023年出版)

  3. Enno Ohlebusch, Bioinformatics algorithms : sequence analysis, genome rearrangements, and phylogenetic reconstruction : hbk, [s.n.], ISBN:9783000413162,
    (2013年出版)

  4. Felipe A. Louza, Simon Gog, Guilherme P. Telles, Construction of fundamental data structures for strings : pbk, Springer, ISBN:9783030551070,
    (2020年出版 SpringerBriefs in computer science)
［参考書］
  1. Gonzalo Navarro, Compact Data Structures: A Practical Approach, Cambridge University Press, ISBN:978-1316588284
  2. Paolo Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, ISBN:978-1009128933
  3. Veli Makinen, Djamal Belazzougui, Fabio Cunial, Alexandru I. Tomescu, Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing, Cambridge University Press, ISBN:978-1009341257
［講義項目］
第１回　Bit Vectors
第２回　Rank/Select Data Structures I
第３回　Rank/Select Data Structures II
第４回　Entropy Compression I
第５回　Entropy Compression II
第６回　Lempel-Ziv-compressed Data Structures I
第７回　Lempel-Ziv-compressed Data Structures II
第８回　Compact Data Structures I
第９回　Compact Data Structures II
第10回　Text Indexing Data Structures I
第11回　Text Indexing Data Structures II
第12回　Compressed Data Structures I
第13回　Compressed Data Structures II
第14回　Compressed Data Structures III
第15回　Compressed Data Structures IV
※評価はレポートと発表により行う．
［前年度授業に対する改善要望等への対応］
アンケート結果確認中