|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/io-efficient-algorithms
课程评论：没有评论
课程名称：I/O高效算法 课程概述： 当数据项位于内存层次的较高处时，操作数据的成本会显著增加。在CPU寄存器中的操作速度约为在外部存储器中寻址的数据项操作的百万倍。因此，将I/O操作考虑在算法设计中至关重要。本课程旨在帮助学员熟悉处理这些问题所需的重要算法概念和技术。尽管我们将采用简化的内存层次结构，但这些概念自然可以扩展到更现实的模型。 先修知识： 为了成功完成本课程，学员需具备基本的算法和数学知识。以下是您应了解的一些内容： - O符号、Ω符号、Θ符号；算法分析方法 - 基本微积分：求和运算、递推关系的求解、对数运算等 - 基础概率论：事件、概率分布、随机变量、期望值等 - 基本数据结构：链表、栈、队列、堆 - （平衡）二叉搜索树 - 基础排序算法，如归并排序、插入排序、快速排序 - 图的术语、图的表示（邻接表和邻接矩阵）、基本图算法（广度优先搜索、深度优先搜索、拓扑排序、最短路径） 课程材料基于资源标签下的课程笔记。虽然课程不会涵盖课程笔记中的所有内容，但这些笔记对未能完全理解讲座或希望深入研究主题的学员都非常有帮助。 视频讲座中存在少量微小错误，具体错误列表可在资源中找到。如发现错误，请通过在出现错误的讲座或测验下方点击方形旗帜报告问题。 课程大纲： 1. **引言**：介绍I/O高效算法课程，讨论I/O模型的基本概念，包括有限大小的内部内存和无限大小的外部内存，以及两者之间以给定大小的块进行数据传输。举例说明算法在外部内存中运行时，其I/O行为对实际运行时间的影响，并讨论I/O模型中算法分析的基础知识。 2. **设计缓存感知和无缓存算法**：讨论两种设计I/O高效算法的技术，以矩阵转置问题为例。第一种技术是“基于块”的方法，形成缓存感知算法；第二种技术使用递归方法，形成无缓存算法。 3. **替换策略**：当我们需要从外部内存读取数据而内部内存已满时，需要通过逐出内部内存中的一个数据块来腾出空间。该逐出数据块的选择由替换策略决定。本模块介绍LRU及其他一些知名替换策略，并探讨LRU与最佳替换策略在I/O效率上的对比。 4. **I/O高效排序**：分析归并排序的I/O效率，并讨论如何调整其结构以提高I/O效率。 5. **I/O高效数据结构**：介绍一些I/O高效的数据结构，包括B树、缓冲树，以及基于缓冲树的I/O高效优先队列。 6. **时间前向处理**：讨论时间前向处理技术，该技术可用于评估有向无环图上的局部函数。
Name:Introduction
Description:In this module we give an introduction to the course I/O-efficient algorithms. We discuss the so-called I/O-model, which consists of an internal memory of limited size, an external memory of unlimited size and where data transfer between these two happens in blocks of a given size. We give a simple example showing that the actual running time of an algorithm working on data in external memory is greatly influenced by its I/O-behavior. Finally, we discuss the basics of analyzing algorithms in the I/O-model.
Name:Designing cache-aware and cache-oblivious algorithms
Description:In this module we discuss two techniques to design I/O-efficient algorithms, using the matrix-transposition problem as a running example. The first technique is a "tile-based" approach and leads to a cache-aware algorithm. The second technique uses a recursive approach and leads to a cache-oblivious algorithm.
Name:Replacement Policies
Description:When we want to read something from external memory while the internal memory is full we need to make room by evicting a block from internal memory. The block which should be evicted is decided by the replacement policy. In this module we introduce LRU and some other some well-known replacement policies, and investigate the I/O-efficiency of LRU compared to an optimal replacement policy.
Name:I/O-efficient sorting
Description:In this module we analyze the I/O-efficiency of MergeSort and discuss how to adapt it to make it more I/O-efficient.
Name:I/O-efficient data structures
Description:In this module we introduce some I/O-efficient data structures: B-trees and buffer trees, and an I/O-efficient priority queue based on buffer trees.
Name:Time-Forward Processing
Description:In this module we discuss time-forward processing, a technique that can be used to evaluate so-called local functions on a directed acyclic graph.
Operations on data become more expensive when the data item is located higher in the memory hierarchy. An operation on data in CPU registers is roughly a million times faster than an operation on a data item that is located in external memory that needs to be fetched first. These data fetches are also called I/O operations and need to be taken into account during the design of an algorithm. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. We will work with a simplified memory hierarchy, but the notions extend naturally to more realistic models. Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, stacks, queues, heaps - (Balanced) binary search trees - Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort - Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths) The material for this course is based on the course notes that can be found under the resources tab. We will not cover everything from the course notes. The course notes are there both for students who did not fully understand the lectures as well as for students who would like to dive deeper into the topics. The video lectures contain a few very minor mistakes. A list of these mistakes can be found under resources. If you think you found an error, report a problem by clicking the square flag at the bottom of the lecture or quiz where you found the error.
