实现已有算法
A. 人工智能专业主要学什么 就业方向有哪些
人工智能技术关系到人工智能产品是否可以顺利应用到我们的生活场景中。在人工智能领域,它普遍包含了机器学习、知识图谱、自然语言处理、人机交互、计算机视觉、生物特征识别、AR/VR七个关键技术。
一、机器学习
机器学习(MachineLearning)是一门涉及统计学、系统辨识、逼近理论、神经网络、优化理论、计算机科学、脑科学等诸多领域的交叉学科,研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能,是人工智能技术的核心。基于数据的机器学习是现代智能技术中的重要方法之一,研究从观测数据(样本)出发寻找规律,利用这些规律对未来数据或无法观测的数据进行预测。根据学习模式、学习方法以及算法的不同,机器学习存在不同的分类方法。
根据学习模式将机器学习分类为监督学习、无监督学习和强化学习等。
根据学习方法可以将机器学习分为传统机器学习和深度学习。
二、知识图谱
知识图谱本质上是结构化的语义知识库,是一种由节点和边组成的图数据结构,以符号形式描述物理世界中的概念及其相互关系,其基本组成单位是“实体—关系—实体”三元组,以及实体及其相关“属性—值”对。不同实体之间通过关系相互联结,构成网状的知识结构。在知识图谱中,每个节点表示现实世界的“实体”,每条边为实体与实体之间的“关系”。通俗地讲,知识图谱就是把所有不同种类的信息连接在一起而得到的一个关系网络,提供了从“关系”的角度去分析问题的能力。
知识图谱可用于反欺诈、不一致性验证、组团欺诈等公共安全保障领域,需要用到异常分析、静态分析、动态分析等数据挖掘方法。特别地,知识图谱在搜索引擎、可视化展示和精准营销方面有很大的优势,已成为业界的热门工具。但是,知识图谱的发展还有很大的挑战,如数据的噪声问题,即数据本身有错误或者数据存在冗余。随着知识图谱应用的不断深入,还有一系列关键技术需要突破。
三、自然语言处理
自然语言处理是计算机科学领域与人工智能领域中的一个重要方向,研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法,涉及的领域较多,主要包括机器翻译、机器阅读理解和问答系统等。
机器翻译
机器翻译技术是指利用计算机技术实现从一种自然语言到另外一种自然语言的翻译过程。基于统计的机器翻译方法突破了之前基于规则和实例翻译方法的局限性,翻译性能取得巨大提升。基于深度神经网络的机器翻译在日常口语等一些场景的成功应用已经显现出了巨大的潜力。随着上下文的语境表征和知识逻辑推理能力的发展,自然语言知识图谱不断扩充,机器翻译将会在多轮对话翻译及篇章翻译等领域取得更大进展。
语义理解
语义理解技术是指利用计算机技术实现对文本篇章的理解,并且回答与篇章相关问题的过程。语义理解更注重于对上下文的理解以及对答案精准程度的把控。随着MCTest数据集的发布,语义理解受到更多关注,取得了快速发展,相关数据集和对应的神经网络模型层出不穷。语义理解技术将在智能客服、产品自动问答等相关领域发挥重要作用,进一步提高问答与对话系统的精度。
问答系统
问答系统分为开放领域的对话系统和特定领域的问答系统。问答系统技术是指让计算机像人类一样用自然语言与人交流的技术。人们可以向问答系统提交用自然语言表达的问题,系统会返回关联性较高的答案。尽管问答系统目前已经有了不少应用产品出现,但大多是在实际信息服务系统和智能手机助手等领域中的应用,在问答系统鲁棒性方面仍然存在着问题和挑战。
自然语言处理面临四大挑战:
一是在词法、句法、语义、语用和语音等不同层面存在不确定性;
二是新的词汇、术语、语义和语法导致未知语言现象的不可预测性;
三是数据资源的不充分使其难以覆盖复杂的语言现象;
四是语义知识的模糊性和错综复杂的关联性难以用简单的数学模型描述,语义计算需要参数庞大的非线性计算
四、人机交互
人机交互主要研究人和计算机之间的信息交换,主要包括人到计算机和计算机到人的两部分信息交换,是人工智能领域的重要的外围技术。人机交互是与认知心理学、人机工程学、多媒体技术、虚拟现实技术等密切相关的综合学科。传统的人与计算机之间的信息交换主要依靠交互设备进行,主要包括键盘、鼠标、操纵杆、数据服装、眼动跟踪器、位置跟踪器、数据手套、压力笔等输入设备,以及打印机、绘图仪、显示器、头盔式显示器、音箱等输出设备。人机交互技术除了传统的基本交互和图形交互外,还包括语音交互、情感交互、体感交互及脑机交互等技术。
五、计算机视觉
计算机视觉是使用计算机模仿人类视觉系统的科学,让计算机拥有类似人类提取、处理、理解和分析图像以及图像序列的能力。自动驾驶、机器人、智能医疗等领域均需要通过计算机视觉技术从视觉信号中提取并处理信息。近来随着深度学习的发展,预处理、特征提取与算法处理渐渐融合,形成端到端的人工智能算法技术。根据解决的问题,计算机视觉可分为计算成像学、图像理解、三维视觉、动态视觉和视频编解码五大类。
目前,计算机视觉技术发展迅速,已具备初步的产业规模。未来计算机视觉技术的发展主要面临以下挑战:
一是如何在不同的应用领域和其他技术更好的结合,计算机视觉在解决某些问题时可以广泛利用大数据,已经逐渐成熟并且可以超过人类,而在某些问题上却无法达到很高的精度;
二是如何降低计算机视觉算法的开发时间和人力成本,目前计算机视觉算法需要大量的数据与人工标注,需要较长的研发周期以达到应用领域所要求的精度与耗时;
三是如何加快新型算法的设计开发,随着新的成像硬件与人工智能芯片的出现,针对不同芯片与数据采集设备的计算机视觉算法的设计与开发也是挑战之一。
六、生物特征识别
生物特征识别技术是指通过个体生理特征或行为特征对个体身份进行识别认证的技术。从应用流程看,生物特征识别通常分为注册和识别两个阶段。注册阶段通过传感器对人体的生物表征信息进行采集,如利用图像传感器对指纹和人脸等光学信息、麦克风对说话声等声学信息进行采集,利用数据预处理以及特征提取技术对采集的数据进行处理,得到相应的特征进行存储。
识别过程采用与注册过程一致的信息采集方式对待识别人进行信息采集、数据预处理和特征提取,然后将提取的特征与存储的特征进行比对分析,完成识别。从应用任务看,生物特征识别一般分为辨认与确认两种任务,辨认是指从存储库中确定待识别人身份的过程,是一对多的问题;确认是指将待识别人信息与存储库中特定单人信息进行比对,确定身份的过程,是一对一的问题。
生物特征识别技术涉及的内容十分广泛,包括指纹、掌纹、人脸、虹膜、指静脉、声纹、步态等多种生物特征,其识别过程涉及到图像处理、计算机视觉、语音识别、机器学习等多项技术。目前生物特征识别作为重要的智能化身份认证技术,在金融、公共安全、教育、交通等领域得到广泛的应用。
七、VR/AR
虚拟现实(VR)/增强现实(AR)是以计算机为核心的新型视听技术。结合相关科学技术,在一定范围内生成与真实环境在视觉、听觉、触感等方面高度近似的数字化环境。用户借助必要的装备与数字化环境中的对象进行交互,相互影响,获得近似真实环境的感受和体验,通过显示设备、跟踪定位设备、触力觉交互设备、数据获取设备、专用芯片等实现。
虚拟现实/增强现实从技术特征角度,按照不同处理阶段,可以分为获取与建模技术、分析与利用技术、交换与分发技术、展示与交互技术以及技术标准与评价体系五个方面。获取与建模技术研究如何把物理世界或者人类的创意进行数字化和模型化,难点是三维物理世界的数字化和模型化技术;分析与利用技术重点研究对数字内容进行分析、理解、搜索和知识化方法,其难点是在于内容的语义表示和分析;交换与分发技术主要强调各种网络环境下大规模的数字化内容流通、转换、集成和面向不同终端用户的个性化服务等,其核心是开放的内容交换和版权管理技术;展示与交换技术重点研究符合人类习惯数字内容的各种显示技术及交互方法,以期提高人对复杂信息的认知能力,其难点在于建立自然和谐的人机交互环境;标准与评价体系重点研究虚拟现实/增强现实基础资源、内容编目、信源编码等的规范标准以及相应的评估技术。
目前虚拟现实/增强现实面临的挑战主要体现在智能获取、普适设备、自由交互和感知融合四个方面。在硬件平台与装置、核心芯片与器件、软件平台与工具、相关标准与规范等方面存在一系列科学技术问题。总体来说虚拟现实/增强现实呈现虚拟现实系统智能化、虚实环境对象无缝融合、自然交互全方位与舒适化的发展趋势
B. (六) 概率算法
前面所讨论算法的每一计算步骤都是确定的,而本次所讨论的概率算法允许算法在执行过程中随机地选择下一个计算步骤。在许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。
概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下, 可将概率算法大致分为四类:数值概率算法、蒙特卡罗(MonteCarlo) 算法、拉斯羡孝陵维加斯(Las Vegas) 算法和舍伍德(Sherwood) 算法。
随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数,因此在随机化算法中使用的随机数都是一定程度上随机的,即伪随机数。
线性同余法 是产生伪随机数的最常用的方法。由线性同余法产生的随机序列 满足
其中 。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容,已超出本书讨论的范围。从直观上看,m应取得充分大,因此可取m为机器大数,另外应取 ,因此可取b为一素数。
为了在设计概率算法时便于产生所需的随机数,建立一个随机数类RandomNumber:该类包含一个需由用户初始化的种子randSeed。给定初始种子后,即可产生与之相应的随机序列。种子randSeed是一个无符号长整型数, 可由用户选定也可用系统时间自动产生。函数Random的输入参数 是一个无符号长整型数,它返回 范围内的一个随机整数。函数fRandom返回[0,1) 内的一个随机实数。
数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。且近似解的精度随计算时间的增加而不断提高。在许多情况下,要计算出问题的精确解是不可能的或没有必要的,因此用数值概率算法可得到相当满意的解。
当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时
舍伍德算法就是一种利用随机算法改造确定性算法,消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为,而是设法消除这种最坏情形行为与特定实例之间的关联性。
思想:利用随机算法改造已有算法,使得算法的性能尽量与输入数据无关,即平滑算法的性能。它总能求得问兄戚题的一个解,且求得的解总是正确的。
算法的性能 =平均性能 + 一个很小的随机值。 舍伍德算法是为了得到好的平均性能。
一个算法,对于不同的输入数据,其算法的性能是不一样的。比如快排算法,每次选择第一个元素作为基准,慎带对序列从小到大排序:
拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。
与蒙特卡罗算法类似,拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例,用同一拉斯维加斯算法反复对该实例求解足够多次,可使求解失效的概率任意小。
蒙特卡罗算法用于求问题的准确解。对于许多问题来说,近似解毫无意义。例如,一个判定问题其解为“是”或“否”,二者必居其一,不存在任何近似解答。又如,我们要求一个整数的因子时所给出的解答必须是准确的,一个整数的近似因子没有任何意义。
用蒙特卡罗算法能求得问题的一个解,但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多,得到正确解的概率就越高。蒙特卡罗算法的主要缺点也在于此。一般情况下,无法有效地判定所得到的解是否肯定正确。
在实际应用中常会遇到一些问题,不论采用确定性算法或随机化算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解,但是通常无法判定一个具体解是否正确。
有些蒙特卡罗算法除了具有描述问题实例的输入参数外,还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。
参考链接: http://www.ruanyifeng.com/blog/2015/07/monte-carlo-method.html
数值概率算法的应用
舍伍德算法的应用
拉斯维加斯算法的应用
蒙特卡罗算法的应用
C. RSA算法的C++实现
RSA算法介绍及java实现,其实java和c++差不多,参考一下吧
<一>基础
RSA算法非常简单,概述如下:
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素(就是最大公因数为1)
取d*e%t==1
这样最终得到三个数: n d e
设消息为数M (M <n)
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M,从而完成对c的解密。
注:**表示次方,上面两式中的d和e可以互换。
在对称加密中:
n d两个数构成公钥,可以告诉别人;
n e两个数构成私钥,e自己保留,不让任何人知道。
给别人发送的信息使用e加密,只要别人能用d解开就证明信息是由你发送的,构成了签名机制。
别人给你发送信息时使用d加密,这样只有拥有e的你能够对其解密。
rsa的安全性在于对于一个大数n,没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e;同样在已知n e的情况下无法
求得d。
<二>实践
接下来我们来一个实践,看看实际的操作:
找两个素数:
p=47
q=59
这样
n=p*q=2773
t=(p-1)*(q-1)=2668
取e=63,满足e<t并且e和t互素
用perl简单穷举可以获得满主 e*d%t ==1的数d:
C:\Temp>perl -e "foreach $i (1..9999){ print($i),last if $i*63%2668==1 }"
847
即d=847
最终我们获得关键的
n=2773
d=847
e=63
取消息M=244我们看看
加密:
c=M**d%n = 244**847%2773
用perl的大数计算来算一下:
C:\Temp>perl -Mbigint -e "print 244**847%2773"
465
即用d对M加密后获得加密信息c=465
解密:
我们可以用e来对加密后的c进行解密,还原M:
m=c**e%n=465**63%2773 :
C:\Temp>perl -Mbigint -e "print 465**63%2773"
244
即用e对c解密后获得m=244 , 该值和原始信息M相等。
<三>字符串加密
把上面的过程集成一下我们就能实现一个对字符串加密解密的示例了。
每次取字符串中的一个字符的ascii值作为M进行计算,其输出为加密后16进制
的数的字符串形式,按3字节表示,如01F
代码如下:
#!/usr/bin/perl -w
#RSA 计算过程学习程序编写的测试程序
#watercloud 2003-8-12
#
use strict;
use Math::BigInt;
my %RSA_CORE = (n=>2773,e=>63,d=>847); #p=47,q=59
my $N=new Math::BigInt($RSA_CORE{n});
my $E=new Math::BigInt($RSA_CORE{e});
my $D=new Math::BigInt($RSA_CORE{d});
print "N=$N D=$D E=$E\n";
sub RSA_ENCRYPT
{
my $r_mess = shift @_;
my ($c,$i,$M,$C,$cmess);
for($i=0;$i < length($$r_mess);$i++)
{
$c=ord(substr($$r_mess,$i,1));
$M=Math::BigInt->new($c);
$C=$M->(); $C->bmodpow($D,$N);
$c=sprintf "%03X",$C;
$cmess.=$c;
}
return \$cmess;
}
sub RSA_DECRYPT
{
my $r_mess = shift @_;
my ($c,$i,$M,$C,$dmess);
for($i=0;$i < length($$r_mess);$i+=3)
{
$c=substr($$r_mess,$i,3);
$c=hex($c);
$M=Math::BigInt->new($c);
$C=$M->(); $C->bmodpow($E,$N);
$c=chr($C);
$dmess.=$c;
}
return \$dmess;
}
my $mess="RSA 娃哈哈哈~~~";
$mess=$ARGV[0] if @ARGV >= 1;
print "原始串:",$mess,"\n";
my $r_cmess = RSA_ENCRYPT(\$mess);
print "加密串:",$$r_cmess,"\n";
my $r_dmess = RSA_DECRYPT($r_cmess);
print "解密串:",$$r_dmess,"\n";
#EOF
测试一下:
C:\Temp>perl rsa-test.pl
N=2773 D=847 E=63
原始串:RSA 娃哈哈哈~~~
加密串:
解密串:RSA 娃哈哈哈~~~
C:\Temp>perl rsa-test.pl 安全焦点(xfocus)
N=2773 D=847 E=63
原始串:安全焦点(xfocus)
加密串:
解密串:安全焦点(xfocus)
<四>提高
前面已经提到,rsa的安全来源于n足够大,我们测试中使用的n是非常小的,根本不能保障安全性,
我们可以通过RSAKit、RSATool之类的工具获得足够大的N 及D E。
通过工具,我们获得1024位的N及D E来测试一下:
n=EC3A85F5005D
4C2013433B383B
A50E114705D7E2
BC511951
d=0x10001
e=DD28C523C2995
47B77324E66AFF2
789BD782A592D2B
1965
设原始信息
M=
完成这么大数字的计算依赖于大数运算库,用perl来运算非常简单:
A) 用d对M进行加密如下:
c=M**d%n :
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x11111111111122222222222233
333333333, 0x10001,
D55EDBC4F0
6E37108DD6
);print $x->as_hex"
b73d2576bd
47715caa6b
d59ea89b91
f1834580c3f6d90898
即用d对M加密后信息为:
c=b73d2576bd
47715caa6b
d59ea89b91
f1834580c3f6d90898
B) 用e对c进行解密如下:
m=c**e%n :
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x17b287be418c69ecd7c39227ab
5aa1d99ef3
0cb4764414
, 0xE760A
3C29954C5D
7324E66AFF
2789BD782A
592D2B1965, CD15F90
4F017F9CCF
DD60438941
);print $x->as_hex"
(我的P4 1.6G的机器上计算了约5秒钟)
得到用e解密后的m= == M
C) RSA通常的实现
RSA简洁幽雅,但计算速度比较慢,通常加密中并不是直接使用RSA 来对所有的信息进行加密,
最常见的情况是随机产生一个对称加密的密钥,然后使用对称加密算法对信息加密,之后用
RSA对刚才的加密密钥进行加密。
最后需要说明的是,当前小于1024位的N已经被证明是不安全的
自己使用中不要使用小于1024位的RSA,最好使用2048位的。
----------------------------------------------------------
一个简单的RSA算法实现JAVA源代码:
filename:RSA.java
/*
* Created on Mar 3, 2005
*
* TODO To change the template for this generated file go to
* Window - Preferences - Java - Code Style - Code Templates
*/
import java.math.BigInteger;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.FileWriter;
import java.io.FileReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;
/**
* @author Steve
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public class RSA {
/**
* BigInteger.ZERO
*/
private static final BigInteger ZERO = BigInteger.ZERO;
/**
* BigInteger.ONE
*/
private static final BigInteger ONE = BigInteger.ONE;
/**
* Pseudo BigInteger.TWO
*/
private static final BigInteger TWO = new BigInteger("2");
private BigInteger myKey;
private BigInteger myMod;
private int blockSize;
public RSA (BigInteger key, BigInteger n, int b) {
myKey = key;
myMod = n;
blockSize = b;
}
public void encodeFile (String filename) {
byte[] bytes = new byte[blockSize / 8 + 1];
byte[] temp;
int tempLen;
InputStream is = null;
FileWriter writer = null;
try {
is = new FileInputStream(filename);
writer = new FileWriter(filename + ".enc");
}
catch (FileNotFoundException e1){
System.out.println("File not found: " + filename);
}
catch (IOException e1){
System.out.println("File not found: " + filename + ".enc");
}
/**
* Write encoded message to 'filename'.enc
*/
try {
while ((tempLen = is.read(bytes, 1, blockSize / 8)) > 0) {
for (int i = tempLen + 1; i < bytes.length; ++i) {
bytes[i] = 0;
}
writer.write(encodeDecode(new BigInteger(bytes)) + " ");
}
}
catch (IOException e1) {
System.out