计算思维脑图

山东专升本计算机第十一章计算思维的知识点有计算思维、问题求解、程序与算法、算法设计的基本方法、主题排序与查找、程序设计的一般过程。

第十一章-计算思维

• 11.1计算思维
  • 概念：计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动
  • 目的：问题求解、系统设计、以及人类行为理解
  • 使用方法：计算机科学的方法
  • 本质：抽象和自动化（基础和前提是抽象，包括设计算法和编写程序两部分）
  • 特征：
    • 计算思维是概念化，不是程序化
    • 计算思维是根本的，不是刻板的技能
    • 计算思维是人的，不是计算机的思维方式
    • 计算思维是数学和工程思维的互补和融合
    • 计算思维是思想，不是人造物
  • 应用：计算物理、计算化学、计算生物学、计算经济学
• 11.2问题求解
  • 分为两步
    • 问题抽象【包括形式化（问题求解的基础和前提）和数学建模】
    • 自动化（抽象以后是自动化，抽象是自动化的前提和基础，计算机通过程序实现自动化，而程序的核心是算法）
• 11.3程序与算法
  • 程序：数据结构（数据和结构）+算法（核心）
  • 算法：
    • 操作
      • 算术运算：加、减、乘、除等
      • 关系运算：大于、大于等于、小于、小于等于、等于、不等于等
      • 逻辑运算：与、或、非等
      • 数据传送：输入、输出、赋值等
    • 控制结构：顺序结构、选择结构、循环结构（刚型和直到型）
    • 特性：有穷性、确定性、可行性、输入、输出
    • 分类：
      • 数值计算算法：用于科学计算，少量输入、输出、复杂的运算
      • 非数值计算算法：目的是数据管理，大量的输入输出，简单的算术运算和大量的逻辑运算
    • 表示：自然语言、传统流程图、伪代码、计算机语言
    • 复杂度
      • 时间复杂度
        • 计算规则
          • 忽略公式中的常数项
          • 忽略公式中的低次幂项，保留公式中的最高次幂项
          • 忽略公式中的最高次幂项的常数系数
          • 如果公式都是常数项，则其时间复杂度为O(1)
      • 空间复杂度
        • 计算规则同时间复杂度相同
• 11.4算法设计的基本方法
  • 迭代法（递推法）
    • 典型案例：斐波那契数列、求最大公约数（欧几里得算法）
  • 穷举搜索法
  • 递归法
  • 回溯法
    • 典型案例：N皇后问题
  • 贪婪法或贪心法
    • 典型案例：硬币找零问题、背包问题
  • 分治法
    • 典型案例：二分搜索、快速排序、合并排序等
• 11.5主题排序与查找
  • 排序
    • 选择排序（递增或递减）
    • 冒泡排序（两两交换，逐个交换）
  • 查找
    • 顺序查找（最优查找次数：1、最坏查找次数：n、平均查找次数：（n+1）/2
    • 二分查找法（折半查找法）：必须按关键字大小排序
• 11.6程序设计的一般过程
  • 1.分析问题 2.确定数学模型 3.算法设计 4.程序编写、编辑、编译和连接 5.运行和测试
• 11.7程序设计方法
  • 结构化程序设计
    • 任何程序都基于顺序、选择、循环3种基本的控制结构
    • 提倡采用自顶而下、逐步细化的模块化程序设计原则
    • 每个模块具有唯一的出口和入口
    • 缺点：难以适应大型软件设计、程序可重用性差
  • 面向对象程序设计
    • 符合人们习惯的思维方法，便于分析复杂多变的问题，易于软件的维护和功能的增减，可重用性好