Lavenshtein Distance

https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm

Advertisements

Pure to Applied Math: Self-driving Cars & “Sum of 2 Squares” Polynomial

Key Points:

  • 1900 Hilbert’s 17th Conjecture: Non-negative Polynomial <=> sum of 2 squares (Proved by Emile Artin in 1927)
  • Computing Math : approximate by optimisation with “Linear Programs” which are faster to compute.
  • Princeton Mathematicians applied it to self-driving cars.

https://www.wired.com/story/a-classical-math-problem-gets-pulled-into-self-driving-cars/amp

Explain:

Sum of 2 Squares <=> always non-negative ( 0)

13 = 4 + 9 = 2^{2} + 3^{2}

P (x) = 5x^2+16x+13 = (x+2)^{2} + (2x+3)^{2} \geq 0

Self-driving Car: Trajectory = P (x)

P(x) < 0 where the car’s position in the trajectory;

Obstacles are positions where P (x) 0.

This is one of the many cases of Pure Math turned to be Applied Math in last few decades. Other examples:

Is Applied Math => Pure Math ?
Yes!

“Simplix” – A simplest language

https://www.codeproject.com/Articles/1244412/How-to-Design-and-Build-the-Simplest-Possible-Prog?from=timeline

Summary: Simplix is an imperative language (not Object-Oriented, nor Functional), it has the “minimalist” features with extensibility from Java VM libraries by intraoperability (aka embedding) Java/C/C++ codes:

  • Only 1 data type: List. The rest (collection, map, structure, array…) are just made of trees of lists.
  • Functions
  • Services: group of functions.

Boolean Algebra

George Boole [2/11/ 1815 – 8/12/ 1864]: 《The Laws of Thought》: symbolic logic representation of thought.

Let x = class of sheep’s

y = white

=> white sheep = xy = yx = sheep white

then Commutativity Law:

\boxed {xy = yx}

Let x= rivers, y = estuaries河口, z= navigable 通航

then, Associativity Law:

\boxed {(xy)z= x(yz)}

A sheep is a sheep,

\boxed {xx = x^{2} = x}

Note: x = 0 or 1 fulfills the above equation.

If x = class of men

y = class of women

z = class of adults (either men or women)

\boxed {z = x + y}

w = European

then Distributive Law:

\boxed {w(x+y) = wx + wy}

If t = Chinese

then all non-Chinese men = {x – t}

If s = Singaporean,

then

\boxed {s(x - t ) = sx - st}

Blockchains and Application in Bitcoins

Encryption & Decryption: ECC (Elliptic Curve Cryptography):

Sending End: Encryption

1) SHA algorithm generates “Digital Signature” ;

2) Generate random “Private Key”.

第3-6步骤:

3) ECC encrypts the text with “Private Key”;

4) From the Private Key generates a “Public Key”;

5) Send out the “original message” and the “Public Key” with the “encrypted message” from 3);

Receiving End: Decryption

6) ECC with Public Key generates Digital Signature 1 (S1);

7) Use SHA algorithm on the original message generates Digital Signature 2 (S2);

8) If S1 = S2, then accept transaction, otherwise reject.

https://mp.weixin.qq.com/s/cLhycZBxkcl5oYNDsElUTg

芯片的基本原理是什么?

芯片 (Chips) 的种类:

  1. CPU 中央处理机
  2. Memory 记忆体储存

材料: 硅 (\gui) Silicon 取自 沙 (sand)

中兴 ZTE 禁令之芯片 为什么这么难做

步骤:

  1. Design 设计 (最难 !)
  2. Manufacture 制作
  3. Test & Packaging 测试&封装

2003 上海交大 微电子学院院长 陈进 的上亿骗局 “汉芯”一号 (其实是 Motorola Chip) 害中国退后十多年 !

Global Foundry: how a CPU is made ?