敬畏自然绿水青山

Category: ICT-Information and Communication Technology

  • 回溯算法示例2-n皇后问题

    上次分享过回溯问题的示例数独问题求解，今天向大家介绍一个类似的问题，n皇后问题，问题的来源是国际象棋中的皇后的摆法，两个皇后不能直面水平，垂直，对角线，否则不满足皇后摆放的要求。 这里也采用回溯的思路，假设为8皇后问题，从第一行开始摆放，用变量记录当前摆放行的candidate位置（记为valid_pos_），并且记录从第一行到当前行摆放的位置记录（path，path[i]即为第i行摆放的皇后的位置值）。我们的第一个函数即为根据已经摆放的path（前面已经摆放的行）去获取当前行的candidates，实现逻辑即为针对每一个前面的行的位置，计算其在当前行不可行的位置（竖直，对角线的位置），具体的代码如下。 其中正式的递归回溯过程的示例代码如下： 最后完整串起来的代码为： 完整的代码请参考链接： data-structures-algorithms/backtracking/n-queens.cpp at main · kindlytree/data-structures-algorithms (github.com)

  • Hadoop-HDFS简介

    Apache hadoop项目开发了一个开源的可信赖，可伸缩的分布式计算软件，Hadoop是一个软件框架，采用简单的编程模型来在计算机集群上分布式的处理大量的数据，它被设计成可以从一台服务器伸缩到几千台机器，该开发框架可以在应用层检测和处理错误，从而在集群上能够提供高可用的服务。大数据的应用场景也有很多，大数据处理技术的集群环境可以用云计算平台搭建，大数据平台也可以作为云计算中的PaaS层提供给有大数据分析场景需求的用户使用。因此大数据技术一般也作为云计算技术专业的专业核心课程之一。后面有机会再和云平台结合具体详细介绍其搭建和使用。这里先做一下简要介绍。 Hadoop的核心组件包括：1、Hadoop Common，支持Hadoop其他模块的通用的一些工具库；2、HDFS（Hadoop Distributed File System）为应用程序提供高吞吐量的分布式文件系统；3、Hadoop YARN，为Hadoop系统中资源管理和任务调度（job scheduling）的框架；4、Hadoop MapReduce：是一个基于YARN系统的大数据集并行处理编程模型；5、Hadoop Ozone。本篇文章主要介绍一下其分布式文件系统的大体思想。 Hadoop HDFS(分布式文件系统），主节点进程(Namenode，存储元数据，文件的目录结构，不同节点之间的负载容量的计算)，子节点(Datanode，多个，客户数据存储的地方)，如图所示为一个客户端在上传文件时（下方的橙色的Client），将两个文件块上传到两个节点中去，然后文件块再创建对应的副本。HDFS和Ceph都属于大容量分布式存储，但是其实现思想方法和优缺点各有不同，怎么选择和结合使用要到后面有机会再详细介绍。 Hadoop中块副本（Block Replication）机制的如下图所示。为文件名，副本数量以及对应的块id号等信息。一般情况下默认副本数为3。 References

  • 线性方程组求解方法简介

    线性方程组的求解可以有不同的方法，下面理解几种以备后续查阅。 1、拉默法则（Cramer’s Rule）是线性代数中一个关于求解线性方程组的定理，其证明过程见参考文献1。 2、高斯消除法求解线性方程组，将方程组转换为增广矩阵，经过一系列的初等行变换得到了行阶梯矩阵（即上三角矩阵）然后自下至上依次求解即可得到原方程的解。正是由于顺序消去法会因为值过小而引入计算误差，为了减少计算过程中舍入误差对方程组求解的影响，因此是否可以选择绝对值尽可能大的主元作为除数。基于这种思想就有了高斯消去法的改进型：部分主元消去法（Gaussian Elimination with Partial Pivoting）。 3、LU分解在实际应用中，LU分解可以通过Doolittle算法来实现，该算法从下至上对矩阵进行初等行变换，将对角线左下方的元素变成零。这些行变换的效果等同于左乘一系列单位下三角矩阵，这些单位下三角矩阵的乘积就是 ( L ) 矩阵。通过这种方式，可以将原始矩阵 ( A ) 表示为 ( L ) 和 ( U ) 的乘积，从而简化求解过程。 4、更多的方法有jacobi迭代法等，具体可以参考引文4，后续有需要再去做更详细的解释说明。 References

  • 树结构相关算法实例-递归方法遍历路径

    在数据结构这门课程中，树结构是最重要的数据结构之一，有比较多的相关算法，比较有名的有：1、树的递归和非递归遍历；2、二叉搜索树的搜索过程；3、AVL树的构建过程；4、树的深度遍历（DFS）和宽度遍历（BFS）算法；5、其他更多的基于树结构的算法。树结构是图结构的基础，在实际应用中也有很多的问题基于树数据结构去建模。更多树结构的相关算法可以参考本文最后的链接，后面有机会也会进一步补充更多的相关算法。 今天要介绍的是一个树结构的一个中等难度左右的算法，即check一颗二叉树从根节点出发到叶子节点的路径上所有节点的和是否等于一个预先设定的值。 在这里介绍两种思路：1、通过递归遍历树结构找到所有的从根节点到叶子节点的路径，这些路径作为候选，一条一条路径check是否满足条件，如果满足可以将路径打印出来；2、通过递归程序直接判断是否存在这样的路径，这种条件下只返回true或false，不能打印出满足条件的路径。 下面主要介绍第一种算法思路（第二种代码思路请参考本文最后的链接），其主要代码如下所示，这里需要特殊说明的是c++中参数的传递技巧，如下面的代码中，path是普通变量，而all_paths是引用变量。普通变量在每一函数调用时会通过拷贝重新生成一个对象，而引用变量在所有递归调用过程中指向同一个数据变量。 两个算法完整的代码请参考链接： data-structures-algorithms/trees/path-sum.cpp at main · kindlytree/data-structures-algorithms (github.com)

  • 关于ML/DL的一些基本问题的汇总及其解答-part2

    机器学习/深度学习（ML/DL）是当前人工智能的核心基础课程和知识点，只有在充分理解了这些核心基础的内容后才能做好更多相关的研究和工程研发，这里收集汇总了之前回答一些基础的相关问题，以备后续查阅。 准备从1、通用的基本问题，2、回归和分类的基本问题，3、Cost Function（objective fuction，loss，error surface），4、Quality metric，5、Neural Network，6、CNN，7、RNN，8、Transformer，9、Reinforcement Learning等等方面进行汇总，后面欠缺的部分后面将要去进一步更新。 这是第二部分的内容。 References 六、CNN 七、RNN 八、Transformer 九、Reinforcement Learning 十、Feature Engineering(Data augumentation) 十一、Clustering Algorithm 十二、Trees 十三、Optimization Algorithms

  • 关于ML/DL的一些基本问题的汇总及其解答-part1

    机器学习/深度学习（ML/DL）是当前人工智能的核心基础课程和知识点，只有在充分理解了这些核心基础的内容后才能做好更多相关的研究和工程研发，这里收集汇总了之前回答一些基础的相关问题，以备后续查阅。 准备从1、通用的基本问题，2、回归和分类的基本问题，3、Cost Function（objective fuction，loss，error surface），4、Quality metric，5、Neural Network，6、CNN，7，RNN，8，Transformer，9，Reinforcement Learning等等方面进行汇总，后面欠缺的部分后面将要去进一步更新。 这是第一部分的内容。 References 一、通用的基本问题 二、回归和分类的基本问题 三、Cost Function（objective fuction，loss，error surface） 四、Quality metric 五、Neural Network

  • 人机交互与人人交互简介

    交互（interaction，dialog）是两个系统之间信息交流的方式，人机交互（human computer interaction）指的是人和计算机之间信息交流沟通的过程和方式，人和计算机都有信息接收，信息加工处理和信息发送的能力，不过两个系统的工作原理不同（经典计算机是人类发明，其工作原理是比较清晰的，但人类的智能加工还有很多神秘待挖掘）。人人交互（human human interaction）指的是人们之间的交互方式，如日常的口语对话（natural dialog），书信，肢体语言等。由于其过程自然流畅，一般也称为自然交互。随着计算机软硬件技术的不断进步，人机交互也越来越向着更加自然高效的交互方式去发展。当然人人交互的复杂和高效特性是那么的独特，比如在一个会议或一群人的交流互动过程中，群体的交互过程的建模和分析就比较复杂（如社交网络也可以理解为一种非即时的群体人人交互，其通过信息技术得以实现物理距离不受限的群体人人交互）。而现阶段一般的人机交互主要还是研究的一对一的人和机器之间的高效交互。人机交互基本上是没有太大二义性的，而人人交互二义性就比较多，人的认知目标也不尽相同，甚至相互的理解程度也是在一定范围和程度内（人人交互也可以说是一种信息的模糊交互过程）。 自计算机发明以来，从早期的纸带输入数据和计算指令，到键盘鼠标以及麦克风等等，新的外围设备的发明不断促进了人和机器之间信息交互的便捷性。人机交互也早已经是计算机应用里边的一个大的研究方向。其研究范畴也挺大，有硬件的外围设备，如鼠标，键盘，智能笔等的发明，促进了计算机使用的便捷性并大大普及了计算机在更广的人群里的使用。计算机可视化技术的发展，使得计算机从早期的DOS系统（Command Line Interface， CLI）过渡到（Graphical User Interface，GUI），通过鼠标和窗口进行交互更加快捷高效，这些交互技术的进步不断促进着计算机的进一步普及。随着人工智能技术的引进，交互也会引入模糊性，如智能技术的结果的精确性就会带来机器理解的模糊性。这类技术通常也称为Intelligent User Interface（IUI，智能用户界面）。 新的智能时代，智能设备的多样性也给交互带来了更多的应用场景和想象的空间，智能眼镜，智能投影仪摄像头等等，一方面提供了更加便捷普适场景的交互，另一方面也延申了人类的感知和认知和想象的能力。如基于虚拟现实技术的交互可视化，可以通过手势等方便和系统进行交互，并及时反馈交互的结果，如可视化技术随着交互手势的输入来动态响应其用户的交互意图，从而展示想要看到的不同视角，不同尺度比例的可视化内容。智能机器人的出现（如具身机器人），人和机器的交互可以逐渐模拟人和人之间的交互过程，如自然的对话，肢体表达等等。随着更多的技术进步，如脑机接口，多模态大模型等技术的发展，人机交互的应用范围和场景也会进一步扩大，nothing is impossible， nothing is beyond imagination。

  • UE学习笔记1-安装及基本使用

    UE是虚拟现实相关技术的很有影响力的引擎，这里将边学习边做一下记录备忘，以备后续查阅复习。 1、UE的下载安装，下载链接请参考引文1，下载安装文件后，执行epic games launcher启动程序，注册一个账号后就可以进入启动epic games的程序进入主窗口界面了。登录后，移动至“虚幻引擎”选项卡，并点击“安装”按钮，下载最新版本。下面将介绍一下UE使用的基础内容，主要是窗口中的一些重要的子窗口元素介绍。 2、关卡编辑器界面：首先新建一个项目，选择第三人称模板(Third Person Template)，项目设置选择蓝图，质量预设选择最大，以及填写项目名称后会进入关卡编辑器界面。 3、放置actor面板：在下图的红色区域点击弹出drop list对话框并选择“放置Actor面板”菜单项，会在程序窗口的左边弹出放置Actor面板，然后在弹出的面板中选择形状，拖入一个“立方体”放入视口中，并通过配置来设置立方体的大小。如下图所示。 4、内容浏览器子窗口面板：用来管理各类资源，如果在创建项目时勾选了初学者内容包，那么在内容浏览器中可以看到“StarterContent”在我们的项目文件中被创建。如下图所示。 5、大纲子窗口面板：放入到视口中的元素，都会一一列到大纲中，如下图中的右边所示。 6、细节子窗口面板：当选中任一物体后，其相关细节设置就会展示在细节面板中。我们可以在细节面板中对选中的物体设置坐标、材质、碰撞等属性。 上述对UE的各个关键子窗口做了介绍，下面以具体的一个简单的设计实操示例来进行性说明。 在内容浏览器子窗口面板的的“Content”（“内容”）目录下，右击鼠标，在弹出的对话框中选择“创建文件夹”，将创建的文件夹命名为“Level”，双击“Level”，然后在内容浏览器空白处右键，选择“新建关卡”。并进行重命名为“Level_Demo”，双击“Level_Demo” ，此时在视口中一片漆黑，什么都看不到。我们需要在关卡内放入Actor来构建世界，我们可以在菜单栏 – 窗口中找到环境光照混合器，点击里面的5个按钮，可以将其快速添加到场景中。 References

  • 量子计算简要介绍

    量子计算是当前前言的科技创新研发领域，相关的计算概念和理论和传统的计算机差异较大，理解起来也挺有难度。今天有机会了解了一下量子计算的最基础的基础部分，加以记录，后面有机会学习更深入的部分的时候也可以回过头来看一些基础的内容，也是作为知识储备能更快的学习后面的内容。技术发展日新月异，终身学习既是时代的需求，也是自我不断成长和进步的要求。 一、布洛赫球 (Bloch sphere)。和经典计算机的比特位不同，量子计算机的信息表示方式为量子位（quantum bit，qubit），其是0和1的叠加态（具体的表示方式可以参考引文），用公式来理解为其是0和1两个状态的线性组合，需要注意的是，这里的线性因子是复数（两个复数因子有归一化约束，即其模的平方和为1）。 经过欧拉方程和global phase等公式和概念的引入和推导，最后得出如下的公式 用布洛赫球 (Bloch sphere)表示为如下的示意结果。 二、单量子比特上的量子操作，量子操作 (Quantum operations)将量子系统的状态转换成一个新的状态，我们通常也称它们为量子门 (Qubit gates)，可以用泡利矩阵的形式来表达，双量子态和多量子态的内容后面有机会再详细介绍，具体也可以参考引文1中的相关内容。上面的两点内容只从数学上进行了阐述，其实际的计算和量子力学等关键的物理背景知识是息息相关的，这方面希望后续有机会要多多了解一下。量子比特的叠加态（Superposition State）是量子计算中一个重要的概念，它允许量子比特同时处于多个状态的线性组合。这使得量子计算在某些情况下能够处理并行计算，与经典计算有着显著的区别。（和传统计算机基于经典比特和晶体管数字逻辑电路属于不同的计算范式） 三、量子计算机的物理实现也有多种，有基于超导量子的实现，也有基于光电子的量子计算机的实现，具体实现方式根据技术差异可能比较大。 四、量子算法有对应的软件模拟，如Qiskit是基于python的面向量子计算的开源软件开发框架，由IBM量子计算团队开发和维护，可以构建、 模拟、执行量子电路。 五、量子力学和信息科技的融合发展出现了量子计算，量子通信和量子精密测量等先进技术，也是当前发展的前沿技术，后面由机会也可以多了解一下。 今天是交通大学128周年校庆，我和交大有挺深的渊源，在这里祝贺交大128岁生日快乐，祝愿交大在未来的科教兴国的征程上硕果累累，创造更大的辉煌！ References

  • 回溯算法示例数独问题求解

    回溯（backtracking）是遍历整个求解空间的一种常见的方式，一些有名的小游戏如数独的解法，八皇后游戏等都可以通过回溯的方法去求解。回溯的思想基本是通过递归进行的实现。这里以一个数独的场景为例向大家介绍一下实现的思路。 首先对数独的尚未填上数字的格子依次从左到右，从上到下的顺序进行填数字尝试，每填写当前的格子，可以按照条件首先筛选出可能的数字，并尝试将这些数字依次进行尝试填到格子里，当可以填写一个候选时，就跳到下一个还未填写数字的格子。如果后来发现下一个未填写的格子没有解（填写数字不能满足数独条件），则尝试下一个候选，如果所有候选都尝试后整个过程还是无解，则返回上一个格子的下一个候选再进行类似的尝试过程。 回溯过程也可以将看成时一个树的搜索过程，比如在数独场景，第一层节点可以看成是第一个格子的所有候选数字节点，回溯的过程是一个动态扩展这棵树的深度优先遍历的过程。如下示例代码显示了其过程，通过递归进行的实现，如果当前填写满足条件则继续下一个格子的填写，如果不满足则当前格子不填（撤回填写的数字）并考虑下一个候选，如果所有的候选都不满足，则退回到上一层搜索的状态继续搜索树的动态构建。 完整示例代码可以参考如下链接。data-structures-algorithms/backtracking at main · kindlytree/data-structures-algorithms (github.com)