- De www.coursera.org
高级数据结构与算法
Curso
zh
Mandarim
Este conteúdo é classificado como 0 de 5
- Individualizado
- Acesso livre
- Certificado pago
- 9 sequências
- Introductive Level
Detalhes do curso
Programa de Estudos
- Week 1 - 欢迎来到高级数据结构与算法
学习了基本的数据结构后，我们已经可以用程序来解决现实中的一些问题了。但是，怎样提升程序在运行效率呢？ 如何快速地把图书按序号从小到大整理好？如何通过一个ID编号在数据库中高效地查找相对应的信息？如何迅速找到所有内容中含有“数据结构”的文档？《高级数据结构与算法》将通过使用高级的数据结构和高效的算法，让你学会如何解决这些对运行时间要求比较严格的问题。 高级数据结构和算法能够根据实际情况，满足一些复杂问题对数据规模、运行时间的要求，帮助我们更有效地解决问题。当我们面对实际问题的时候，高级数据结构和算法让我们有更广泛的空... - Week 2 - 内排序（上）
生活中，排序操作无处不在，列队出操的时候，需要让同学们从矮到高依次站好，举行运动会的时候，会把每位运动员的成绩从高到低排序。在计算机的存储结构中，分为内存和外存，前者相对后者来说速度快、容量小，因此，当整个排序过程中所有的记录都可以直接放入内存中时，我们称之为内排序。可以按照什么策略来进行排序？每种排序算法的时间代价是多少？这一模块中，你将会学到三种类型的排序算法：插入排序、选择排序和交换排序，并了解到各个算法的稳定性和时间代价。重点：排序问题的基本概念，时间和空间复杂度分析（比较次数和移动次数，一个swap操作是... - Week 3 - 内排序（下）
有些算法时间代价太大？有的时候可以根据数据本身的特性，或是排序的特殊要求，调整排序的策略。例如，现在要将一叠试卷按得分从高到低排序，假设老师只给了“合格”、“不合格”两种分数，相信你立马就能整理好。原因就在于你并不需要再去整理所有“合格”试卷的相对次序了。本模块中，你将会学习到归并排序、分配排序和索引排序，并了解它们各自的基本思想、适用范围和时间代价。重点：归并排序及其优化、桶式排序、静态/链式基数排序的实现、地址索引排序的结果整理。难点：归并排序的实现、排序问题的下限的决策树分析方法（了解即可）。 - Week 4 - 外排序
当待处理的数据对象非常多，以至于内存容纳不下所有数据时，如果我们仍旧按照内排序的算法进行排序，大量的I/O会使得时间代价非常大，那应该怎么办呢？一般我们需要将数据文件分成若干段，每次将一段放入内存中进行排序，得到一系列的顺串，最后通过逐趟归并顺串，形成对整个数据文件的排序文件。在这一模块中，你将学到如何让初始文件形成尽可能长的初始顺串、如何通过增加每次参与归并的顺串个数，来减少对数据扫描的趟数，从而减少访问外存次数提高排序效率。重点：置换选择算法、二路归并算法、赢者树算法的基本思想和实现。难点：败者树的类定义... - Week 5 - 检索
检索是一种常见的、也是必不可少的运算。在数据量很小的时候，顺序检索就可以快速找到目标，但当数据量很大的时候，顺序检索的效率就很差了。那如何在这种情况下进行检索呢？生活中，比如我们要查一个英文单词在字典的哪一页，我们可以根据拼写，判断这个单词是在当前页之前还是之后；又比如我们也可以问一个“天才”，他能直接告诉我们那个词在第几页。那如何找到、创造这样的“天才”呢？通过本模块的学习，除了检索的基本知识、基于线性表的检索方法、对集合的检索外，你还会学习到一种可以根据关键码值直接找到记录存储地址的方法——基于散列表的检索。... - Week 6 - 索引
索引相当于图书馆的卡片目录，有了卡片目录之后，就不需要在整个书库中搜索某一本书，而可以在卡片目录中检索到该书的位置。有了索引技术之后，我们可以高效地进行检索、插入、删除等操作。如何来实现索引？如何动态地调整索引？如何提高在索引中的检索效率？通过这一模块的学习，你会了解静态索引、倒排索引的相关知识，B树B+树是如何维护的，红黑树又是通过怎样的调整，提高增删和检索效率的。重点：要充分理解索引的意义。也就是（key, pointer）。基于属性的倒排、对正文文件的倒排、B/B+树的概念及相关操作、红黑树的定义和数学性质... - Week 7 - 高级线性结构
生活中，很多事物是有层次结构关系的，如果只是用线性表之类的简单数据结构来描述，就会丢失一些重要的信息。另一方面，为了支持动态数据结构，操作系统需要对内存进行动态地分配和回收，但也因此会产生如“碎片问题”、“内存泄露”等问题。如何利用高级数据结构来描述实际问题？如何实现相应的高级数据结构？如何管理内存分配，使内存利用率更高？通过本模块的学习，你将会了解多维数组、广义表这两个高级数据结构的实现，以及多种内存动态分配和回收的技术。重点：特殊矩阵和稀疏矩阵的计算，了解索引下标的规律（例如，特殊矩阵多维到一维下标的相互映射... - Week 8 - 高级树形结构
你是不是发现，二叉搜索树的运行效率并没有想象中那么好？这是因为二叉搜索树是一种基于对象空间分解的数据结构，即关键码范围的分解是由树中的对象决定的，并受到关键码输入的影响，因此就有可能变得非常不平衡，例如退化为线性结构。那如何来改进二叉搜索树呢？在这一模块中，你将学到Trie树、AVL树、伸展树的基本思想以及他们在具体进行插入删除操作时，是如何调整树的结构以保持平衡的。重点：Trie树的概念及其改进、AVL树的概念及插入删除操作、伸展树的概念及其旋转操作。 - Week 9 - 期末考试，向毕业项目出发！
祝贺大家完成了《高级数据结构与算法》这门课的所有教学模块，只要顺利通过期末考试，你就向成为优秀的程序设计人员的梦想又迈进了一步哦！如果你同时也完成了《程序设计与算法》专项课程的其他部分，那么恭喜你，你已经由轻叩计算机世界大门的初学者，成长到了一名优秀的准程序员啦！快来通过期末考试，向我们的毕业项目出发，用实际的企业开发案例证明你的实力吧！
Pré-requisito
Nenhum.
Instrutores
Prof. Ming Zhang 张铭
教授
School of Electronics Engineering and Computer Science北京大学计算机系
Editor
A Universidade de Pequim está determinada a tornar a sua educação abertamente acessível aos estudantes na China e em todo o mundo. Com mais de 3000 membros do corpo docente, a Universidade de Pequim oferece excelência no ensino e na aprendizagem. Fundada em 1898, a Universidade de Pequim (PKU) foi a primeira universidade nacional abrangente da China.
Nos últimos 115 anos, com as suas centenas de milhares de antigos alunos excepcionais, a Universidade de Pequim tem dado contributos proeminentes nas áreas das humanidades e das ciências para promover a prosperidade e o progresso da China.
Plataforma
A Coursera é uma empresa digital que oferece um curso on-line massivo e aberto, fundado pelos professores de computação Andrew Ng e Daphne Koller Stanford University, localizado em Mountain View, Califórnia.
O Coursera trabalha com as melhores universidades e organizações para disponibilizar alguns dos seus cursos on-line e oferece cursos em várias disciplinas, incluindo: física, engenharia, humanidades, medicina, biologia, ciências sociais, matemática, negócios, ciência da computação, marketing digital, ciência de dados. e outros assuntos.Cours
Este conteúdo é classificado como 4.5 de 5
(nenhuma revisão)Este conteúdo é classificado como 4.5 de 5
(nenhuma revisão)Conclua este recurso para fazer uma avaliação