大数据机器学习算法与计算机视觉应用04:多项式

The Algorithm Magic of Polynomial

  • Polynomials
  • The Root of Polynomial
  • A Delete Channel
  • Polynomials for Finding Maximum Matchings

Polynomials 多项式

一个 d d d 次多项式可以用一个 d + 1 d+1 d+1 元组 c i {c_i} ci 表达。在这种情况下,两个多项式相加的时间复杂度是 O ( d ) O(d) O(d) ,而两个多项式相乘的实践复杂度是 O ( d log ⁡ d ) O(d \log d) O(dlogd)

快速地估计一个多项式的值的方法:对应给定值b,循环执行将当前式子乘b,加下一项。这个方法叫做霍纳规则。流程如下:
c d c d × b + c d − 1 ( c d × b + c d − 1 ) × b + c d − 2 c_d c_d \times b + c_{d-1} (c_d \times b + c_{d-1}) \times b +c_{d-2} cdcd×b+cd1(cd×b+cd1)×b+cd2
该算法的时间复杂度是 O ( d ) O(d) O(d)

多项式的根

对于一个多项式 P ( x ) P(x) P(x),令 P ( x ) = 0 P(x)=0 P(x)=0 的值 x ′ x' x 被称作多项式的根。

根据代数基本定理,一个d次多项式一定有d个根。

Unique Reconstruction Theorem 唯一重构定理

唯一重构定理告诉我们,给定d个点 ( x 1 , y 1 ) , ( x 2 , y 2 ) ⋱ , ( x d , y d ) (x_1,y_1),(x_2,y_2) \ddots, (x_d,y_d) (x1,y1),(x2,y2),(xd,yd), 总有一个多项式 P ( x ) P(x) P(x) 使得这些点都在多项式上。

事实上,唯一重构定理告诉我们如何构造这样一个多项式满足条件。
首先我们构造这样一组多项式 R i ( x ) R_i(x) Ri(x) 满足:
R i ( x i ) = 1 R i ( x j ) = 0 , j ≠ i R_i(x_i) = 1 R_i(x_j) = 0, j \neq i Ri(xi)=1Ri(xj)=0,j=i
结果如下:
Π j ≠ i ( x − x j ) Π j ≠ i ( x i − x j ) \quad{\Pi _{j\neq i}(x-x_j)}\over{\Pi _{j\neq i}(x_i-x_j)} Πj=i(xixj)Πj=i(xxj)
那么
P ( x ) = y 0 R 0 ( x ) + y 1 R 1 ( x ) + ⋯ + y d R d ( x ) P(x) = y_0 R_0(x) + y_1 R_1(x) + \cdots +y_d R_d(x) P(x)=y0R0(x)+y1R1(x)++ydRd(x)

举个例子:有三个点 ( 5 , 1 ) , ( 6 , 2 ) , ( 7 , 9 ) (5,1),(6,2),(7,9) (5,1),(6,2),(7,9),现在找出经过这三个点的多项式。
R 1 ( x ) = ( x − 6 ) ( x − 7 ) ( 5 − 6 ) ( 5 − 7 ) = 1 2 ( x 2 − 13 x + 42 ) R 2 ( x ) = ( x − 5 ) ( x − 7 ) ( 6 − 5 ) ( 6 − 7 ) = − 1 2 ( x 2 − 12 x + 35 ) R 3 ( x ) = ( x − 5 ) ( x − 6 ) ( 7 − 6 ) ( 7 − 5 ) = 1 2 ( x 2 − 11 x + 30 ) P ( x ) = R 1 ( x ) + 2 R 2 ( X ) + 9 R 3 ( x ) = 4 x 2 − 50 x + R_1(x) = \frac{(x-6)(x-7)}{(5-6)(5-7)} = \frac{1}{2} (x^2 -13x +42) R_2(x) = \frac{(x-5)(x-7)}{(6-5)(6-7)} = -\frac{1}{2} (x^2 -12x +35) R_3(x) = \frac{(x-5)(x-6)}{(7-6)(7-5)} = \frac{1}{2} (x^2 -11x +30) P(x) = R_1(x) + 2R_2(X) + 9R_3(x) = 4x^2-50x + R1(x)=(56)(57)(x6)(x7)=21(x213x+42)R2(x)=(65)(67)(x5)(x7)=21(x212x+35)R3(x)=(76)(75)(x5)(x6)=21(x211x+30)P(x)=R1(x)+2R2(X)+9R3(x)=4x250x+

A Deletion Channel 丢失频道

下面是另一个问题,假设在上面构造多项式的情景中,Alice要向Bob传d+1个数,但是在传输的过程中总会有k个数丢失,那么怎么才能保证Bob一定收的到这d+1个数呢?

一种很笨的方法是,将每个数据发送k+1次就可以了。但是这需要发送 d × ( k + 1 ) d\times (k+1) d×(k+1) 个数据,有没有更好的方法呢?

一种好方法是构造一个多项式 P ( x ) = Σ c i x i P(x) =\Sigma c_i x_i P(x)=Σcixi,然后发送 P ( 0 ) , P ( 1 ) , ⋱ , P ( d + k ) P(0),P(1),\ddots,P(d+k) P(0),P(1),,P(d+k),这样Bob至少可以收到d+1个多项式的值,根据唯一重构定理,Bob可以计算出这个多项式从而得出所有的c。
这种做法的时间复杂度是 O ( d + k + 1 ) O(d+k+1) O(d+k+1),比上面的做法少传输很多数据。(注意,不用担心乱序的问题,因为是一个一个传的,而如果出错会传乱码而不是什么也不做)。

General Error Correction 误码纠错

假设现在不是传输丢失,而是传输一个错误的数字,那么在同样的背景下,需要进行怎样的传输呢?

很明显,答案是需要传输 d + 2 k + 1 d+2k+1 d+2k+1个数字,其中 d + k + 1 d+k+1 d+k+1是正确的多项式的值。因为 k + 1 > k k+1>k k+1>k,所以我们从理论上确认了Bob可以通过这种方式找到正确的多项式。

那么实际上应该怎么找到那个正确的多项式呢?

假设Bob收到的数据是 r 0 , r 1 , ⋱ , r d + 2 k r_0,r_1,\ddots,r_{d+2k} r0,r1,,rd+2k,Z是其中错误信息的集合,那么我们声明一个错误项多项式
E ( x ) = Π i ∈ Z ( x − i ) E(x) = \Pi_{i\in Z}(x-i) E(x)=ΠiZ(xi)
那么对于Bob收到的所有项都满足以下等式,因为要么 E ( x ) = 0 E(x)=0 E(x)=0,要么 P ( x ) = r x P(x) = r_x P(x)=rx
P ( x ) ⋅ E ( x ) = r x ⋅ E ( x ) P(x)\cdot E(x) = r_x \cdot E(x) P(x)E(x)=rxE(x)

Berlekamp-Welch Algorithm BW算法

BW算法是一种用于误码纠错的算法,其运行规律基于上文所述,我们假设
E ( x ) = x k + e k − 1 x k − 1 + ⋯ + e 0 ( i f d e g r e e ( E ( x ) ) i s k ) P ( x ) ⋅ E ( x ) = f d + k x d + k + f d + k − 1 x d + k − 1 + ⋯ + f 0 E(x) = x^k +e_{k-1}x^{k-1} + \cdots + e_0 (if degree(E(x)) is k) P(x) \cdot E(x) = f_{d+k}x^{d+k} + f_{d+k-1}x^{d+k-1} + \cdots + f_0 E(x)=xk+ek1xk1++e0(ifdegree(E(x))isk)P(x)E(x)=fd+kxd+k+fd+k1xd+k1++f0
这种情况下,我们分别将 x = 0 , 1 , ⋯ , d + 2 k x = 0,1,\cdots, d+2k x=0,1,,d+2k带入方程
P ( x ) ⋅ E ( x ) = r x ⋅ E ( x ) P(x) \cdot E(x) = r_x \cdot E(x) P(x)E(x)=rxE(x)
左边是一堆参数f相加,右边是一堆e相加,f和e未知数的总和是d+2k+1个,而带入d+2k+1个x的值对应d+2k+1个方程,而且方程必定有解,因此就可以解出所有的e和f。

已知 P ( x ) ⋅ E ( x ) P(x) \cdot E(x) P(x)E(x) E ( x ) E(x) E(x) ,相除就可以求出 P ( x ) P(x) P(x)

Polynomials for Finding Maximum Matching 多项式在最大匹配中的应用

Schwarz-Zippel Lemma Schwarz-Zippel 引理

这个引理的内容是:假设 P P P是一个非零 m m m d d d次多项式,假设 S S S是有限域 F F F的一个子集。如果从 S S S中随机抽取 m m m个数 x 1 , x 2 , ⋯ , x m {x_1,x_2,\cdots,x_m} x1,x2,,xm,那么
P r [ P ( x 1 , ⋯ , x m ) = 0 ] ≤ d ∣ S ∣ Pr[P(x_1,\cdots,x_m)=0] \leq \frac{d}{|S|} Pr[P(x1,,xm)=0]Sd
健全性检查:当 m = 1 m=1 m=1时,因为d次多项式最多有 d d d个根,因此概率很明显就是 d ∣ S ∣ \frac{d}{|S|} Sd

这个引理可以用来解决下文提到的图的匹配问题。

Tutte Matrix

每个顶点数 v v v的简单无向图都对应一个Tutte Matrix M ( G ) M(G) M(G),简单来说如图所示:
Tutte Matrix

Tutte Determinant Theorem Tutte行列式定理

一个图有完美匹配当且仅当 M ( G ) M(G) M(G)的行列式不是零多项式。
(注:匹配指的找到图中一组边集,其中任意两条边都没有公共点。如果这组边集包括了图中所有的顶点,那么就说该匹配是完美匹配。)

那么剩下的就是选取 F F F的大小了, F F F的基数越大,这张图有完美匹配的概率就越高。

Finding a Perfect Matching

上面我们知道了有完美匹配的概率,但是我们如何找到一个完美匹配呢?下面是一个方法:

对于每个边,将图中的该边删去,判断剩下的图中是否还存在完美匹配。如果没有完美匹配,那么将该边加回来;否则丢弃该边。
最后一定剩下 V 2 \frac{V}{2} 2V条边,这些边就是一个完美匹配。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/11443.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

万字长文解读深度学习——生成对抗网络GAN

🌺历史文章列表🌺 深度学习——优化算法、激活函数、归一化、正则化深度学习——权重初始化、评估指标、梯度消失和梯度爆炸深度学习——前向传播与反向传播、神经网络(前馈神经网络与反馈神经网络)、常见算法概要汇总万字长文解读…

万字长文解读深度学习——训练(DeepSpeed、Accelerate)、优化(蒸馏、剪枝、量化)、部署细节

🌺历史文章列表🌺 深度学习——优化算法、激活函数、归一化、正则化深度学习——权重初始化、评估指标、梯度消失和梯度爆炸深度学习——前向传播与反向传播、神经网络(前馈神经网络与反馈神经网络)、常见算法概要汇总万字长文解读…

简易入手《SOM神经网络》的本质与原理

原创文章,转载请说明来自《老饼讲解神经网络》:www.bbbdata.com 关于《老饼讲解神经网络》: 本网结构化讲解神经网络的知识,原理和代码。 重现matlab神经网络工具箱的算法,是学习神经网络的好助手。 目录 一、入门原理解说 01.…

Python爬虫快速获取JD商品详情:代码示例与技巧解析

在当今这个信息爆炸的时代,数据成为了一种宝贵的资源。对于电商行业来说,获取商品详情信息是进行市场分析、价格比较、库存管理等重要环节的基础。本文将通过一个Python爬虫示例,展示如何快速获取(JD)商品的详情信息。…

大数据-218 Prometheus 插件 exporter 与 pushgateway 配置使用 监控服务 使用场景

点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…

【数字图像处理+MATLAB】将图像转换为二值图像(Binary Image):使用 imbinarize 函数进行二值化运算(Binarize)

引言 二值图像是一种特殊类型的数字图像,其中每个像素只有两种可能的强度值或颜色值。这两种值通常表示为黑色和白色,或者0和1。 二值化是一个常见的图像处理步骤,它将灰度或彩色图像转换为二值图像。在二值化过程中,会设定一个…

智能电销机器人的操作流程

对于电销行业的人来说,有了智能电销机器人,简直是太省心了! 智能外呼机器人,是一款基于人工智能语音外呼系统, 它可以代替人工自动拨打电话,自动筛选客户,自动推送意向客户到你的微信上 &#x…

CSDN做样板,教我们如何为新网站引流

CSDN为我们做了个很好的例子,详细请看下图 亮点分析: 1. 未采用硬广在网站上进行引流。减少了给用户在直觉上的造成的反感; 2. 在GitHub的转跳页面中,植入额外的关联网站链接。虽然对用户解决问题没啥鸟用,但是人家能…

电脑局域网内让其他电脑通过IP访问配置

依次点击桌面左下角“开始菜单”>“所有应用”>“Windows系统”>“控制面板”,如图所示 在控制面板界面,选择“查看方式”为“大图标”,然后点击打开window防火墙,如图所示 然后点击“高级设置”,如图所示 在…

网络安全——下载并在kali虚拟机上启动Cobalt Strike

目录 一、下载 二、上传文件到kali虚拟机 三、启动服务端 四、启动客户端 一、下载 CobaltStrike4.8汉化版带插件-CSDN博客 下载并解压后 二、上传文件到kali虚拟机 1、打开并运行kali虚拟机,查看kali的ip地址 2、打开xshell,新建连接,连…

[Win11]集成化综合漏洞扫描系统[更新]

前言 之前是为了方便外包仔在客户现场漏扫所以才集成的这个系统 优点:倒腾一下格式可以直接在客户的Vmware ESXI上面上面部署,同时个人版Vmware也可以拿来直接用。 由Linux版本改为了Windows版(有很多不会用) 因为前两个更新的很频繁,所以…

【SSL-RL】自监督强化学习:随机潜在演员评论家 (SLAC)算法

📢本篇文章是博主强化学习(RL)领域学习时,用于个人学习、研究或者欣赏使用,并基于博主对相关等领域的一些理解而记录的学习摘录和笔记,若有不当和侵权之处,指出后将会立即改正,还望谅…

详解MySQL安装

目录 Ubantu 1. 使⽤apt安装MySQL 2.查看MySQL状态 3. MySQL 安装安全设置 4.设置密码 卸载MySQL Centos 1. 确认当前的系统版本 2.下载MySQL源 3.安装MySQL 4.启动mysqld 5.查看MySQL状态 6.设置开机自启动 7.查看MySQL密码,并登录 8.修改密码 Ubant…

【MATLAB源码-第213期】基于matlab的16QAM调制解调系统软硬判决对比仿真,输出误码率曲线对比图。

操作环境: MATLAB 2022a 1、算法描述 一、16QAM调制原理 在16QAM(16 Quadrature Amplitude Modulation)调制中,一个符号表示4个比特的数据。这种调制方式结合了幅度调制和相位调制,能够在相同的频谱资源下传输更多的…

Renesas R7FA8D1BH (Cortex®-M85) Data Flash程序功能实现

目录 概述 1 Data Flash空间 2 FSP配置参数 3 源代码介绍 3.1 源代码 3.2 中断函数 3.3 源代码文件 4 测试 4.1 测试实现 4.2 测试 概述 本文主要介绍使用FSP提供的库函数操作Renesas R7FA8D1BH (Cortex-M85) Data Flash的方法,笔者使用FSP配置参数&#x…

计算机组成原理知识点汇总,零基础入门到精通,收藏这篇就够了

计算机发展历程 计算机硬件的发展 计算机的四代变化 1946年世界上第一台电子数字计算机(Electronic Numerical Integrator And Computer, ENIAC) 1)第一代计算机(1946-1957)电子管时代。特点:逻辑元件采…

动态规划——01背包问题

目录 零、背包问题 一、01背包 二、分割等和子集 三、目标和 四、最后一块石头的重量II 零、背包问题 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总…

30.2 不得不谈的lsm:分层结构和lsm数据结构

本节重点介绍 : LSM树核心特点LSM树的核心结构 MemTableImmutable MemTableSSTable LSM树的Compact策略 size-tiered 策略leveled策略 LSM树(Log-Structured-Merge-Tree) LSM树的名字往往会给初识者一个错误的印象,事实上,LSM树并不像B树、红黑树一样…

宏观经济学笔记

【拯救者】宏观经济学速成 国民生产总值GNP: GNP 衡量一国(地区)成员在一定时期内运用生产要素所生产的全部最终产品和服务的市场价值。凡是本国国民所 创造的收入,不管生产要素是否在国内,都计入本国GNP中。 GDP本国居民在本国创造的价值外国居民在本国…

模块二:central cache实现

一、central cache介绍 结构也是一个哈希桶,大小划分和 thread cache哈希桶一样,区别在于挂的不是自由链表而是 span 链表,里面连接了许多 span 二、span介绍 1、实现思路 span 就是 central cache 向 page cache 申请的大块内存&#xff…