解数独

数独英文为sudoku,是一种在9*9 大小方格内,填充1-9 的游戏,要求每行每列,和9 个3*3 的方格内不允许有重复的数字。前几天写了一个解数独的程序:http://blog.foool.net/sudoku/ ‘set value’将方格中数字顺序填入方格内(0 代表该空格未填数字),‘compute’进行计算,规定时间内完成计算则会返回结果。右边有一个计算范例,测试过独数之道中大师级PK 题,可解。

image         image

继续阅读

安装libcloud 遇到的一些问题

libcloud 是apache 的顶级项目之一,用于在多个云直接提供统一的接口,既可以用于云计算,也可以用于云存储,使用python 编写。下载手动安装libcloud 后没有问题,试着跑一个测试文件提示:

  File "/usr/local/lib/python2.7/ssl.py", line 60, in 
    import _ssl             # if we can't import it, let the error propagate
ImportError: No module named _ssl

判断为SSL module 没有安装, 试着

python -c "import ssl"

出现和之前一样的提示。接着参考这Compiling Python with SSL Support (Fedora 10) 重新下了python 编译下还是出现同样问题。

查看了下,openssl 安装了。转头想用官网上使用的pip 安装,但是得先用easy_install 安装,easy_install 是由PEAK(Python Enterprise Application Kit)开发的setuptools包里带的一个命令,所以使用easy_install实际上是在调用setuptools来完成安装模块的工作。但是在使用easy_install 命令时,提示错误:

Traceback (most recent call last):
  File "/usr/bin/easy_install", line 5, in 
    from pkg_resources import load_entry_point
ImportError: No module named pkg_resources

初步怀疑原因是setuptools 是使用命令:

sudo apt-get install python-setuptools

安装到/usr/bin 目录下,和python 的版本不一致导致的,网上有使用ez_setup.py 安装的方法(据说64 位只有这样安装才行),但还是有问题:

Downloading http://pypi.python.org/packages/2.7/s/setuptools/setuptools-0.6c11-py2.7.egg
Traceback (most recent call last):
  File "ez_setup.py", line 278, in 
    main(sys.argv[1:])
  File "ez_setup.py", line 212, in main
    from setuptools.command.easy_install import main
zipimport.ZipImportError: can't decompress data; zlib not available

按照官网中安装下载python2.7 对应的版本setuptools-0.6c11-py2.7.egg 安装setuptools 出现同样问题:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
zipimport.ZipImportError: can't decompress data; zlib not available
You have new mail in /var/mail/qing

参考stackoverflow 上的方法安装了一些包后可以

sh setuptools-0.6c11-py2.7.egg

安装对应版本的setuptools 了。只是安装在了/usr/local/lib/python2.7/site-packages/ 目录下,每次运行需要加上sudo 才有对应权限:

sudo easy_install pip

安装好pip 后更新了libcloud:

pip install --upgrade apache-libcloud

再使用SSL

python -c "from socket import ssl"

也没有提示之前问题了。

由IPhone 密码锁想到的零知识证明

事情源于国庆、中秋双节回家,看到Lina 总是背着我输入IPhone 密码想到的(上次因为输入密码次数过多导致重新刷机,所以她不让我碰她的IPhone),我猜想这:如果我能够瞄她输入密码的数字和顺序,那么我就可以知道并记住密码,并在“偷”到IPhone 后以同样的密码进入。为了避免密码输入被人偷窥到而导致密码泄露,自然而然会有些想法:一、有没有什么方式让每次输入的密码都不同;二、更进一步,有没有哪种方式让她当着我的面输入密码,我也不知道密码是什么呢?

继续阅读

信息论基础

信息论是应用数学,电子信息工程和计算机科学相关信息量的一个分支。信息论最早是由香农同学发展起来的,他提出了信号处理操作如数据压缩和可靠地存储、传输数据的基本限制。现已推广并发展到多个领域:自然语言处理(NLP)、加密、包含通信网络更大范围的网络,如神经网,还有量子计算、其他形式的数据分析等等。

衡量信息的一个重要工具是熵(或者称为信息量,为统一起见,下文将全部用熵代替),它用来表示在信息中存储或通信一个符号需要的平均比特长度。熵量化了预测一个随机变量的值的不确定性。比如,说出一次投币过程的结果(两个等概率可能出现的结果)比说出一次掷骰子的结果(六个等概率可能出现的结果)的信息量要少。

应用到信息论基础涉及但不局限于以下方面:无损压缩、有损压缩和信号编码等。

继续阅读

Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage

原文地址

从文章字面意思来看讲的是最优再生码的显示结构。文章主要贡献是给出了d = n-1 情况下的精确修复(Exact repair)MBR 一个通用的结构。

在分布式存储系统中,通过传输信息修复失效节点中的数据可以分为两类:精确修复(Exact repair,即修复得到的新数据和原来因节点失效的数据相同)、功能性修复(Functional repair,即修复得到的数据可能和原失效数据不同,但修复保持着数据的冗余度)。精确修复又有一类只对系统码中的原始数据部分进行精确修复,对校验部分进行功能性修复。三者包含范围关系如下:

                                  image

继续阅读