yuhuanstudio/wikipedia-omni-zh huggingface dataset:
仓颉

仓颉（约公元前2667年约公元前2596年），是中国神话人物，相传为黄帝的右史官、以及汉字的创造者，俗称仓颉先师、仓颉圣人、制字先师、制字先圣或右史仓圣人。传说生有“双瞳四目”。

## 造字传说

<image>

传说仓颉是黄帝的右史，是发明文字的始祖，有传说“仓颉造字”。战国时期的人不知道在此之前的汉字是殷商时期的甲骨文，因此传说中仓颉在黄帝时期造的字是战国时期流行的篆书。其助手左史沮诵记录下来时，鬼怪夜间哭泣，认为人类即将开启智慧纪载历史及教诲。传说他仰观天象，俯察万物，首创了“鸟迹书”震惊尘寰，堪称人文始祖。黄帝感他功绩过人，乃赐以“仓”姓，意为君上一人，人下一君。

“仓颉造字”的传说在战国时期已经广泛流传。《荀子·解蔽》称：“好书者众矣，而仓颉独传者壹也”。《韩非子·五蠹》：“昔者仓颉之作书也，自环者谓之私，背私谓之公。”《吕氏春秋·君守篇》亦记载有：“奚仲作车，仓颉作书，后稷作稼，皋陶作刑，昆吾作陶，夏鲧作城，此六人者，所作当矣。”《淮南子·本经》中记载：“昔者仓颉作书，而天雨粟，鬼夜哭。”《说文解字序》中记载：“仓颉之初作书，盖依类象形，故谓之文；其后形声相益，即谓之字。文者，物象之本；字者，言孳乳而寖多也。著于竹帛谓之书。书者，如也。以迄五帝三王之世，改易殊体，封于泰山者七十有二代，靡有同焉。”唐代西明寺道世法师（？－683年）在其名作《法苑珠林》中就有这样的记载：“昔造书之主，凡有三人。长名曰梵，其书右行；次曰佉卢，其书左行；少者苍颉，其书下行。”《大正藏》第53册，351页中、下

## 遗迹与纪念

山西新绛、山东寿光和东阿、河南开封、河南南乐、虞城、陕西长安和白水、河南阳武（今原阳县）、河南洛宁等地都有仓颉墓等遗迹。

为了纪念仓颉造字之功，后人把河南新郑县城南仓颉造字的地方称作“凤凰衔书台”，宋朝时还在这里建了一座庙，取名“凤台寺”。

在旧中国许多学校都奉有“文字圣人仓颉先师”的神位，并常与文昌帝君一同奉祀。其诞辰为农历三月二十八日，也有一说为农历九月一十八日。

台湾多将仓颉作为寺庙同祀神或奉祀于敬字亭。

联合国因为纪念仓颉的贡献，将4月20日（谷雨）定为联合国中文日。

现今在香港常用的中文输入法仓颉输入法，也是用仓颉命名。

### 奉祀寺庙

#### 台湾

- 台北市士林区芝山岩惠济宫－有神像，祀于后殿二楼文昌阁主神龛前方
- 新北市平溪区十分成安宫－有神像
- 宜兰县头城镇庆元宫－有神像及神位
- 宜兰县宜兰市文昌庙－有神位，祀于文昌宫正龛内
- 宜兰县罗东镇孔子庙－有神位
- 桃园市芦竹区南天坛－有神像，位于玉皇宝阁主龛内
- 新竹市东区关帝庙－有神位，位于后殿正龛内
- 新竹市香山区香山财神庙－有神像，位于母圣殿内
- 新竹县北埔乡五指山灶君堂－有神像，位于正殿正龛内
- 苗栗县苗栗市苗栗文昌祠－神位有二，分别位于正殿正龛及龙边
- 苗栗县头份市斗焕坪大化宫－有神像，位于正殿下层龙边神龛
- 苗栗县头屋乡鸣凤山云洞宫－有神像，位于二楼虎边神龛
- 彰化县员林镇兴贤书院－有神位，位于后殿龙边厢房
- 彰化县鹿港镇文武庙－有神像，位于文祠正龛内
- 云林县麦寮乡拱范宫－有神位，位于文昌殿内
- 嘉义市东区镇南圣神宫－有神位，位于后殿
- 台南市归仁区敦源圣庙－有神位
- 台南市麻豆区麻豆文衡殿－有神位
- 高雄市苓雅区高雄关帝庙－有神像，位于正殿二镇殿关帝前方
- 高雄市凤山区凤邑诚心社明善堂－有神位，位于赤山文衡殿二楼诚心社明善堂
- 高雄市旗山区天后宫－有神位，位于文昌殿内
- 屏东县屏东市玉皇宫－有神像，位于大成宝殿上层龙边神龛
- 屏东县东港镇东隆宫－有神像，位于先师殿内
- 屏东县车城乡福安宫－有神像，位于文昌殿内

## 参见

- 仓颉中文输入法（第一批电脑键盘繁体中文输入法之一，以“仓颉”命名，以表示其重大意义）
- 仓颉书

## 外部链接

- “造字圣人光耀南乐”之一：仓颉陵原是古遗址
- 系列之二：四目灵光的仓颉
- 系列之三：不废江河万古流
- 《图书的起源》：仓颉造字传说及遗迹。
玻色子

<image>

在量子力学里，粒子可以分为玻色子（boson）与费米子。玻色子由保罗·狄拉克命名，是为了纪念印度物理学者萨特延德拉·玻色的贡献。他与阿尔伯特·爱因斯坦合作发展出的玻色-爱因斯坦统计可以描述玻色子的性质。在所有基本粒子中，标准模型的几个传递作用力的规范子，如光子、胶子、W玻色子、Z玻色子都是玻色子，同时赋予基本粒子质量的希格斯子业已证实是玻色子；而在量子引力理论里传递引力的引力子也是玻色子，只是尚未被证实存在。在复合粒子里，介子是玻色子，质量数为偶数的稳定原子核，像重氢2H（原子核由一颗质子和一颗中子组成，质量数为2）、氦-4、铅-208等也是玻色子，准粒子像库柏对、等离体子、声子等都是玻色子。

多个玻色子可以同时占有同样量子态。这是一个很重要的性质。当氦-4因冷却变为超流体时，会显示出这种性质。与之相比，两个费米子不能同时占有同样的量子态。组成物质的基本粒子是费米子，例如，轻子、夸克。玻色子传递作用力使得费米子能够连结在一起。由于玻色子的作用，物质能够黏结在一起。

## 定义与性质

<image>

玻色子定义为遵守玻色-爱因斯坦统计的粒子；根据玻色-爱因斯坦统计，对于N个全同玻色子，假设将其中任意两个玻色子交换，则由于描述这量子系统的波函数具有对称性，波函数不会改变。费米子遵守费米狄拉克统计；根据费米狄拉克统计，对于N个全同费米子，假设将其中任意两个费米子交换，则由于描述这量子系统的波函数具有反对称性，波函数的正负号会改变。由于这种特性，费米子遵守包利不相容原理：两个全同费米子不能占有同样的量子态。因此，物质具有有限体积与硬度。费米子被称为物质的组成成分。

所有已知基本或复合粒子，依照自旋而定，自旋为整数的粒子是玻色子，自旋为半整数的粒子是费米子。在非相对论性量子力学里，这纯为经验观察；但在相对论性量子场论里，自旋统计定理表明，半整数的粒子不能成为玻色子，整数的粒子不能成为费米子。

激光、激微波、超流体、玻色-爱因斯坦凝聚的基础物理机制为玻色子所遵守的玻色-爱因斯坦统计。另外一个结果是处于热力学平衡的光子气体，其光谱是普朗克谱，例如，黑体辐射、现今称为微波背景辐射的不透明早期宇宙的热辐射。虚玻色子与真实粒子之间的交互作用造成了所有已知的作用力，除了引力之外。

在大型系统里，只当在粒子密度很大时，也就是说，当它们的波函数重叠时，玻色子统计与费米子统计才会显示出来；在密度很小时，两种统计都可以用经典力学的麦克斯韦-玻尔兹曼统计作良好近似。

## 基本玻色子

所有观测到的基本粒子，不是费米子，就是玻色子。所有观测到的基本玻色子都是规范玻色子：光子、W玻色子、Z玻色子、胶子、希格斯玻色子。

- 胶子 - 强相互作用的媒介粒子，自旋为1，共8种。
- 光子 - 电磁相互作用的媒介粒子，自旋为1，共1种。
- W及Z玻色子 - 弱相互作用的媒介粒子，自旋为1，共3种。
- 希格斯玻色子 - 通过希格斯机制将质量给予其它粒子，自旋为0，目前只发现1种。
- 引力子 - 引力相互作用的媒介粒子，自旋为2，只有1种，目前未曾观测到。

## 复合玻色子

复合粒子是由几个粒子组成，例如，强子、原子核、原子等等。依照组成粒子的自旋，复合粒子可以是玻色子或费米子。更精确地说，由于自旋与统计之间的关系，由偶数个费米子组成的粒子是玻色子，因为它的自旋为整数。

- 介子是玻色子，它是由一个夸克与一个对应的反夸克组成的强子。
- 由偶数个核子组成的原子核是玻色子。质子和中子都是费米子，含偶数个核子的原子核具有整数自旋，例如，碳-12有六个质子、六个中子。
- 氦-4有两个质子、两个中子、两个电子，是复合玻色子。

## 玻色子的量子态

玻色-爱因斯坦统计鼓励全同玻色子挤入同一个量子态，但并不是任意量子态都必需很方便地被挤入。除了统计机制以外，玻色子可以彼此相互作用，例如，几个非常邻近的氦-4原子会彼此感受到分子间力，假设它们的凝聚处于某种空间定域的量子态，由于从统计获得的助益 不能克服太过高昂的位势，它们喜好处于一种空间离域的量子态（较低的ψ(x)）：假若凝聚的数目密度与普通液体或固体大致相同，则拿量子统计所描述的凝聚与普通统计所描述的液体或晶体晶格作比较，凝聚的相斥位势不能高于后者的相斥位势。所以，玻色-爱因斯坦统计不能够绕过对于物质的密度所施加的物理限制。因此，超流体液氦的密度与普通液体物质相当。根据不确定性原理，空间离域的量子态具有较低的动量，因此动能也较低，这就是为什么通常在低温才能观察到超流体性质与超导性质。

光子彼此之间不会相互作用，因此不会经历到这种挤入量子态的不同。

## 参阅

- 任意子
- 玻色气体
- 全同粒子
- W-玻色子
- 仲统计法（parastatistics）
汾阳市

汾阳市是中华人民共和国山西省的一个县级市，由吕梁市代管。位于山西中部，太原盆地西南缘。市人民政府驻永和西大街9号。

## 历史

<image>

秦朝置兹氏县，西晋改名隰城县，唐朝上元元年（760年）再改为西河县；明朝洪武元年（1368年）并入汾州，万历二十三年（1595年）升为汾州府并置汾阳县；民国初年废府存县；1996年撤县设市。

## 地理

汾阳地处吕梁山的东麓，境内兼具丘陵与平原地形；汾河的支流文裕河流贯。全市年平均气温9℃，降水量470毫米。

## 交通

- 铁路：太中银铁路（汾阳站）
- 公路：G20、和汾高速公路（S66）、307、222、223、243、340

收费站：汾阳收费站 汾阳西收费站 汾孝收费站 汾孝东收费站 杏花村收费站

## 人口

第七次全国人口普查（以2020年11月1日零时为标准时点）数据显示：汾阳市常住人口为407647人。

2010年第六次全国人口普查汾阳市常住人口416212人。

## 经济

农业以种植小麦、高粱、稻谷、棉花为主，特产核桃。工业有食品、煤炭采掘等。

白酒是当地的主导产业，2022年汾阳市白酒产值201.5亿元、产量17.7万千升，产量为山西省的五分之四、全国清香型白酒的五分之一，其中龙头企业为汾酒集团，其产量又占全市的70%、产值占96%。

## 物产

- 汾阳的矿产有煤、石膏、铝矾土、铁、石灰岩、石英石、钾长石等。
- 野生动物有麝、豹、狐狸、狍、野猪、山鸡、石鸡、褐马鸡等。
- 野生植物有猪苓、党参、甘草、黄芩、柴胡等。
- 土特产主要有汾酒、竹叶青酒、汾州核桃、长山药。

## 风景名胜

- 全国重点文物保护单位共9处：太符观、汾阳五岳庙、汾阳文峰塔、杏花村汾酒作坊、东龙观墓群、柏草坡龙天土地庙、峪口圣母庙、汾阳关帝庙、汾阳后土圣母庙。
- 山西省文物保护单位共23处：杏花村遗址、峪道河遗址、北垣底遗址、狄青墓、虞城五岳庙、汾阳法云寺、堡城寺龙王庙、齐圣广佑王庙、汾阳报恩寺、禅定寺、汾阳铭义中学、巩村古城址、演武寿圣寺、石家庄龙天庙、蔚光年宅院、后沟玲珑塔、坂峪东岳庙、刘家堡关帝庙、汾阳南薰楼、药师七佛多宝塔、东石龙天庙、南赵郡佛殿、汾阳教会医院旧址。
- 吕梁市文物保护单位：汾阳北门北关宋金墓群
- 汾阳市文物保护单位多处
- 中国历史文化名镇：杏花村镇

## 名人

- 郭子仪
- 王文素，明朝数学家
- 贾樟柯
- 恒安石
- 冀朝铸
- 冀朝鼎
- 郭德纲

## 电影

以汾阳为背景的电影有：

- 《小武》
- 《山河故人》

## 教育

学校名称：山西省汾阳中学校

学校地址：汾阳市英雄中路19号

学校简介：

山西省汾阳中学的办学历史最早可追溯至清康熙二十四年（1685年）创建的棠荫书院。雍正七年（1729），更名西河书院。光绪二十七年（1901），按照清廷命令改设为西河学堂。到1906年，伴随着新思想的传播又改为汾州府中学堂，1913年称河汾中学，其时校训为：“勤诚朴毅”。

1899年，基督教公理会派传教士文阿德在汾阳办起学校。1911年，学校始定出年级和学制：初级小学四年制，高级小学三年制。民国三年（1914），创立了铭义中学，作为一所教会背景的私立中学，其校训为：“苦读、苦炼、苦作”。

1949年，人民政府将河汾中学、铭义中学及周边各县的学校整合，组建了山西省立汾阳中学。

学校坐落于汾州古城中心，校园占地69368平米，建筑面积40659平米，绿化面积达31423平米。

## 基本资料

- – 拼音：Fényáng Shì
- 隶属：山西省吕梁市
- 类型：县级市
- 行政区划代码：141182
- 成立：1996年8月
- 行政中心：太和桥街道
- 分区：14
- 地址：9
- 分区：3
- 分区：2
- 坐标：37.265°N 111.788°E
- 面积：1176
- 人口：2020
- 人口：43.46万
- 密度：353.92
- GDP：264.70亿元
- 人均：20368元
- 邮政编码：032200
- 网站：www.fenyang.gov.cn
- 网站：中国汾阳政府门户网站
- GDP_as_of：2022
费米子

<image>

在粒子物理学里，费米子（fermion）是遵守费米-狄拉克统计的粒子。费米子包括所有夸克与轻子，任何由奇数个夸克或轻子组成的复合粒子，所有重子与很多种原子与原子核都是费米子。术语费米子是由保罗·狄拉克给出，纪念恩里科·费米在这领域所作的杰出贡献。

费米子可以是基本粒子，例如电子，或者是复合粒子，例如质子、中子。根据相对论性量子场论的自旋统计定理，自旋为整数的粒子是玻色子，自旋为半整数的粒子是费米子。除了这自旋性质以外，费米子的重子数与轻子数守恒。因此，时常被引述的“自旋统计关系”实际是一种“自旋统计量子数关系”。

<image>

根据费米-狄拉克统计，对于N个全同费米子，假设将其中任意两个费米子交换，则由于描述这量子系统的波函数具有反对称性，波函数的正负号会改变。由于这特性，费米子遵守包利不相容原理：两个全同费米子不能占有同样的量子态。因此，物质具有有限体积与硬度。费米子被称为物质的组成成分。质子、中子、电子是制成日常物质的关键元素。

## 基本费米子

标准模型确认两种基本费米子：夸克与轻子。而这2类基本费米子，又分为合共24种味（flavor）：

- 12种夸克：包括上夸克 （u）、下夸克 （d）、奇夸克 （s）、魅夸克 （c）、底夸克 （b）、顶夸克 （t），及它们对应的6种反粒子。
- 12种轻子：包括电子（e-）、μ子 （μ-）、陶子 （τ-）、电微中子（νe）、缈微中子（νμ）、陶微中子（ντ），及对应的6种反粒子。

理论而言，费米子有三种：不带质量的外尔费米子（Weyl fermion）、带质量的狄拉克费米子（Dirac fermions）、粒子与反粒子相同的马约拉纳费米子。物理学者认为，大多数标准模型费米子是狄拉克费米子，虽然物理学者们尚不清楚中微子是狄拉克中微子还是马约拉纳中微子。狄拉克费米子可以视为左手的外尔费米子与右手的外尔费米子的组合。

## 复合费米子

依它们组成的成分而定，复合粒子可以是玻色子或费米子。更精准而言，由于自旋与统计之间的关系，奇数数量的费米子可以组成一个费米子，它的自旋为半整数。例如。

- 像中子、质子这些强子，都是由三个夸克组成的费米子。
- 碳-13的原子核含有六个质子、七个中子，因此，它是费米子。
- 氦-3 （3He）原子含有两个质子、一个中子、两个电子，因此，它是费米子。

在复合粒子内部的玻色子数量不会改变这复合粒子是玻色子还是费米子。

复合粒子到底是玻色子还是费米子，这判别是在远距离（与粒子尺寸做比较）进行。在复合粒子邻近，空间结构开始显得重要，其物理行为与组成的成分有关。

当费米子松散地结合成对时，可能会展示出玻色子行为。这物理机制造成了氦-3的超导性质与超流体性质的。在超导物质里，通过交换声子，电子形成库柏对；在氦-3里，库柏对是通过自旋涨落形成库柏对。

在分数量子霍尔效应（fractional quantum Hall effect）里出现的准粒子知名为复合费米子，它是负载偶数个量子涡旋的电子。

## 参阅

- 任意子
- 手征性
- 费米凝聚
- 费米场（Fermionic field）
- 全同粒子
壶口瀑布

<image>

<image>

36.14883 110.44394 壶口瀑布是黄河中游流经晋陕大峡谷时形成的一个天然瀑布。东为吕梁山脉南端的火焰山，临山西省临汾市吉县；西为黄龙山，临陕西省延安市宜川县壶口乡，距吉县县城西南约25公里。瀑布宽达30米，深约50米，最大瀑面为3万平方米。与属于珠江水系位于中越边界的德天瀑布、贵州省黄果树瀑布等同为中国著名瀑布。

滚滚黄河奔流至此，500余米宽的洪流骤然被两岸所束缚，上宽下窄，在50米的落差中翻腾倾涌，声势如同在巨大无比的壶中倾出，河口收束狭如壶口，故名“壶口瀑布”。中国古籍尚书《禹贡》曰“盖河漩涡，如一壶然”。两大著名奇景“旱地行船”和“水里冒烟”，更是罕见。亚洲飞人柯受良和吉县飞人朱朝晖先后驾驶汽车和摩托车成功飞越黄河壶口瀑布景区。2006年9月5日，壶口瀑布国家地质公园正式揭碑开园。

<image>

黄河壶口瀑布位于山西省临汾市吉县西部南村坡下，地理位置为北纬36°8′10″，东经110°26′40″，海拔448.1米。以壶口瀑布为中心，北至马粪滩，南至小船窝，西至峡谷地域，东至人祖山，总面积100平方千米。

壶口瀑布所处地区平均海拔高度958.6米，气候属高原大陆性中温带-暖温带季风气候，北部属半干旱地区，南部属半湿润地区，南北差异显著。壶口瀑布年平均气温9.9℃，四季分明，冬季寒冷、时间最长，从10月17日入冬，4月4日才会入春，长达170天，最冷的1月，平均最高气温只有2.2℃，平均最低气温达到-11℃，历史上曾出现过最寒冷的一天气温低至-25.4℃。冬春雨雪少，易旱且有风沙、寒潮侵袭，气象灾害频繁，12月到2月各月平均降水总量只有3～5毫米。夏秋温凉多雨，常年6月26日入夏，8月14日入秋，6～9月一年中降水最多时段，7、8月最多，降水总量达到100多毫米，也多暴雨、冰雹出现。一年中最热时期，平均最高气温在28.9℃，曾经出现的极端最高气温为39.7℃，年高温日数最多有18天，连续高温最长天数是8天。日照充足，年变化量不大，各月的每天日照时数都能达到6～8个小时。平均早霜始于十月中旬，晚霜终于四月上旬，无霜期152天。
高等数学

高等数学（Further Mathematics）是比初等数学更高深的数学，一般是指高中的数学组学生，以及大学非数学专业的本科生所修习的数学。

## 历史

微积分是17世纪末由英国科学家牛顿（I. Newton，1643—1727）和德国科学家莱布尼茨（G. W. Leibniz，1646—1716）独立发明。数学界把微积分发明之前的数学称为初等数学，而把微积分及其后的发展例如微分方程称为高等数学。

现代高等数学教材的主要内容包括：极限理论、一元微积分学、多元微积分学、空间解析几何与向量代数、级数理论、常微分方程初步，各类课本略有差异。

中学里较深入的代数、几何以及集合论初步、逻辑初步统称为中等数学的，将其作为小学、初中的初等数学与本科阶段的高等数学之间的过渡。

## 数学专业

数学专业的本科生，须学习数学各主要方向的理论，学习许多抽象数学概念的定义，以及与这些概念有关的定理的陈述与证明，要求的范围和深度比其他专业的“高等数学”要高得多：分析方面，除了一元和多元微积分，还有数学分析、实分析、复分析、泛函分析等；代数方面有在任意域上的线性代数、抽象代数等；概率方面以测度论为基础，与实分析关系密切；应用数学方面有常微分方程、偏微分方程、数值分析等；并且有“高等数学”不会触及到的很多方向，如几何和拓扑方面，有曲线与曲面的微分几何、点集拓扑等；其他方面还有初等数论、图论、组合数学、数理逻辑等。研究生程度则有更多20世纪以后所发展出的分支方向，一些较大的方向有代数几何、黎曼几何、代数拓扑、几何拓扑、表示论、解析数论、代数数论、动力系统理论、随机过程等。

## 经典文献

- 《微积分学教程》格里高利·米哈伊洛维奇·菲赫金哥尔茨著
- 《数学分析习题集》鲍里斯·吉米多维奇著
- 《微积分和数学分析引论》Richard Courant（柯朗）著
- 《高等数学教程》斯米尔诺夫著 1-5卷 高等教育出版社
- 《古今数学思想》M.克莱因着 1-4册 上海科学技术出版社
- 《高等数学例题与习题集.一,一元微积分》И.И.利亚什科等编著
- 《高等数学例题与习题集.二,多元微积分》И.И.利亚什科等编著
- 《高等数学引论》(共四卷) 华罗庚著 科学出版社
- 《微积分五讲》龚昇著
- 《重温微积分》齐民友著

## 各地情况

### 中国大陆

理工科非数学专业的各类专业的学生，学的深一些，课本常称“高等数学”，多数院校使用课本为同济大学数学系所编的《高等数学》；文史科各类专业的学生，学得浅一些，课本常称“微积分”。理工科的不同专业，文史科的不同专业，深浅程度又各不相同。研究变量的是高等数学，可高等数学并不只研究变量。至于与“高等数学”相伴的课程通常有：线性代数，概率论与数理统计。

### 香港

在以往的五年制中学中，报考香港中学会考理学组的学生会在中四及中五级学习到附加数学科，预科中六及中七级数学组学习纯粹数学科，涵盖较深的三角学、极限、数列、级数、微积分、复数、矩阵、三维空间向量、圆锥曲线、数学归纳法、不等式、基础的逻辑和集合论等，并需学习书写证明。部分学生在中六及中七级还会学习应用数学科，包括利用向量、微积分和微分方程设立联立方程，处理复杂的受力分析问题，以及概率与统计、数值方法、微分方程；中六及中七级的非数学组学生，也有部分会学习数学与统计学科，学习基础微积分、概率与统计。

在三三四高中教育改革后，中学高等数学内容被大量删减，只保留代数、微积分、概率与统计，成为香港中学文凭考试数学科延伸部分。

大学理科、工科、商科和社会科学所要学习的数学和统计知识，多数由各院系自行设计和教授。
维尔纳·海森堡

维尔纳·卡尔·海森堡（Werner Karl Heisenberg；1901年12月5日－1976年2月1日），德国物理学家，量子力学创始人之一，“哥本哈根学派”代表性人物。1933年，海森堡因为“创立量子力学以及由此导致的氢的同素异形体的发现”而获得1932年度的诺贝尔物理学奖。他对物理学的主要贡献是给出了量子力学的矩阵形式（矩阵力学），提出了“不确定性原理”（又称“海森堡不确定性原理”）和S矩阵理论等。他的《量子论的物理学原理》是量子力学领域的一部经典著作。

## 生平

维尔纳·海森堡1901年12月5日出生于德国维尔茨堡，1920年从慕尼黑的一所中学毕业后，在慕尼黑大学学习物理学，师从阿诺·索末菲、威廉·维恩等，1922年冬天转去哥廷根大学，师从马克斯·玻恩（1954年诺贝尔物理学奖）、詹姆斯·弗兰克（1925年诺贝尔物理学奖）和大卫·希尔伯特。1923年他在慕尼黑大学获得博士学位，并去哥廷根大学担任玻恩的助手，1924年获得大学任教资格。

从1924年至1927年，海森堡在哥廷根担任讲师。1924年9月17日至1925年5月1日，由于一项国际教育委员会洛克菲勒基金会奖学金的支持，海森堡与哥本哈根大学物理主任玻尔进行研究。之后他回到哥廷根和马克斯·玻恩共事并共同发表了矩阵力学。1926年又前往哥本哈根大学教授理论物理学。1927年，发展了海森堡不确定性原理，为后来知名的哥本哈根诠释奠定了基础，于同年，年仅26岁的海森堡被任命为莱比锡大学的教授，他的第一篇论文发表于莱比锡。1929年，他又前往美国、日本和印度巡回讲学。1941年成为柏林洪堡大学的物理学教授和物理研究所主任。

第二次世界大战结束后，他和其他德国物理学家作为囚犯，被美国军队送往英国Farm Hall。1946年重返德国后，他和他的同事们重建了哥廷根物理研究所，该研究所在1948年改名为马克斯-普朗克物理学研究所。1948年他在英国剑桥讲学数月，1950年和1954年又应邀前往美国讲学，1955年冬天他在苏格兰的圣安德鲁斯大学教书，这些课程后来出版成书。1955年作为马克斯-普朗克物理学研究所的主任，与研究所一起迁往慕尼黑，1958年成为慕尼黑大学的物理学教授，他的研究所被改名为“马克斯-普朗克物理学和天体物理学研究所”（现为马克斯-普朗克天体物理学研究所）。

海森堡于1937年与伊丽莎白·舒马赫（Elisabeth Schumacher）结婚，育有7个孩子，居住在慕尼黑。1976年2月1日，他因癌症于家中逝世。

## 研究

海森堡的名字一直都和他的量子力学理论联系在一起，这一理论发表时他年仅23岁，他也因为提出这一理论及其应用（尤其是氢的自旋异构体发现），获得了1932年度的诺贝尔物理学奖（1933年颁发）。

海森堡提出的新理论，是完全基于对原子辐射的观察，他认为，在某一个给定的时间点，一个电子所处的位置是无法确定的，也无法跟踪它的轨迹，所以玻尔假定的电子轨道不存在；诸如位置、速度等力学量，无法用通常的数字来描述，但可以用抽象的数学结构即矩阵来表达，海森堡用矩阵形式给出了他的新理论（矩阵力学）。

此后，海森堡又提出了著名的“不确定性原理”（又称“海森堡测不准原理”），在一个量子力学系统中，一个运动粒子的位置和它的动量不可被同时确定，位置的不确定性Δx和动量的不确定性Δp是不可避免的，它们的乘积不小于h/4π（h为普朗克常数），这些误差对于人类来说虽然是微小的，但是在原子研究中并不能被忽略。

在莱比锡期间，海森堡为原子核物理学做出了重要贡献，为基本粒子理论引入了内部对称量子数（1932年，1933年），发展了一种铁磁性理论（1928年），和沃尔夫冈·泡利对量子场论进行了开创性研究工作。海森堡和约翰·惠勒同为S矩阵（1942年，1944年）之父，他很早就研究了量子场论的基本长度模型（1938年）。1940年代，他还研究了宇宙射线及其产生的离子碎片，导致不久后在英国发现了第一个介子。

1957年起，海森堡的研究兴趣转向了等离子体物理和高热原子核反应问题，并与日内瓦国际原子物理研究所紧密合作，他担任该研究所的科学政策委员会主席，并一直是该委员会的成员。在他于1953年成为德国洪堡基金会主席后，为基金会做了很多促进工作，他邀请各国科学家来德国，并协助他们在德国开展研究工作。

1953年起，他的理论工作偏向基本粒子的统一场论，这对于他来说，是理解基本粒子物理学的关键。

## 荣誉

除了获得马克斯·普朗克奖章、德意志联邦共和国功绩勋章等奖章，诺贝尔物理学奖等奖项外，海森堡还被布鲁塞尔自由大学、卡尔斯鲁厄大学和罗兰大学授予荣誉博士头衔。他是伦敦皇家学会的会员、以及哥廷根、巴伐利亚、萨克森、普鲁士、瑞典、罗马尼亚、挪威、西班牙、荷兰、罗马、美国等众多科学学会的成员，德国科学院和意大利科学院的院士。1953年成为洪堡基金会的主席。

## 纳粹德国的核武器计划

海森堡曾经是德国核武器开发计划研制的参与者，不过纳粹德国自始至终都没有能力将核武器从理论变为现实。海森堡本人提供的一种说法称，他其实不信任希特勒政权，因此在尽力拖延纳粹德国的研究计划。但古德施密特等一些人对这种说法嗤之以鼻，这也被称之为“海森堡之谜”。

## 参阅

- 莫特问题

## 延伸阅读

- Nobel Lectures, Physics 1922-1941, Elsevier Publishing Company, Amsterdam, 1965.
- Werner Heisenberg - Biography. The Nobel Foundation. （诺贝尔官方网站关于维尔纳·海森堡简介）
- Ivan Todorov: Werner Heisenberg . Institut für Theoretische Physik, Universität Göttingen. Göttingen, Germany.

## 基本资料

- 原文名：Werner Heisenberg
- 出生日期：1901年12月5日
- 出生地：德意志帝国巴伐利亚王国维尔茨堡
- 逝世日期：1976年2月1日
- 逝世地：西德巴伐利亚州慕尼黑
- 居住地：西德
- 国籍：德意志帝国、魏玛共和国、纳粹德国、西德
- 研究领域：物理
- 机构：哥廷根大学、哥本哈根大学、莱比锡大学、柏林洪堡大学、圣安德鲁斯大学、慕尼黑大学
- 母校：慕尼黑大学、哥廷根大学
- 博士导师：阿诺·索末菲
- 博士生：费利克斯·布洛赫

<image>

、爱德华·特勒、王福山
- 知名于：测不准原理、量子力学
- 获奖：

<image>

诺贝尔物理学奖（1932年）
Encarta

Encarta 是微软过往曾推出的数码多媒体百科全书，部分内容整合自ABC百科全书中的科里尔百科全书。Encarta也有线上版，但是线上版只包含有限内容，完整版本是必须购买才能获得的。现在Encarta与Microsoft Student系列软件一同售出。2008年，完整的英文版Encarta Premium有超过62,000篇条目。

《Microsoft Student with Encarta Premium 2009》包括了适应从小学（7岁）至大学的学生学习内容与工具、电子百科、多语种字典以及一套儿童教育软件（《Encarta kids》）。与其他电子百科相比，Encarta的优势在于大量的多媒体资料。缺点是其中部分内容不甚客观，有以美国为中心的倾向，而且内容更新的速度也比较慢，Encarta 2009中很多数据已经改为2007－2008年的资料。

2009年3月，微软宣布停止Encarta光盘和在线版本。除日本外的所有国家/地区的MSN Encarta站点于2009年10月31日关闭。日本的Encarta站点于2009年12月31日关闭。但dictionary.msn.com上的Encarta在线词典将继续由Microsoft运营。

## 历史

大英百科全书1989年出版的康普顿多媒体百科全书是第一部多媒体CD-ROM百科全书。

Grolier1985年出版的CD-ROM上的美国学术百科全书是纯文本的。1990年，当它被称为新格罗利尔电子百科全书（1988-1991）时，增加了静态图片。格罗利尔多媒体百科全书CD-ROM于1992年作为新格罗利尔多媒体百科全书首次出现。

微软通过购买Funk & Wagnalls百科全书的非专有权利来发起Encarta，并于1993年将其合并到其第一版中。（Funk & Wagnalls 继续独立于Encarta 出版修订版数年，但在1990年代后期停止印刷。) 微软最初在1980年代接触了大英百科全书，这是一个多世纪以来百科全书的黄金标准，但它拒绝了，认为它的印刷媒体销售会受到损害。然而，本顿基金会在1996年被迫以低于账面价值的价格出售大英百科全书公司，当时印刷品销售不再能够与Encarta专注于将副本与新计算机系统捆绑在一起的Microsoft分销渠道竞争。

1990年代后期，微软从Macmillan手中收购了Collier的百科全书和New Merit Scholar 的百科全书，并将它们并入Encarta。因此，当前的Microsoft Encarta可以被认为是Funk和Wagnalls、Collier和New Merit Scholar百科全书的继任者。这些以前成功的百科全书在并入Encarta后，都没有长期出版。

微软即后又推出了几个翻译成英语以外语言的区域版本的Encarta。例如，巴西葡萄牙语版本于1999年推出，并于2002年暂停使用。西班牙语版本比英语版本略小，有42,000篇条目。

2006年7月，总部位于伦敦的Websters International Publishers在华盛顿贝尔维尤的子公司Websters Multimedia从Microsoft手中接管了Encarta的维护工作。最后一个版本是Encarta Premium 2009，于2008年8月发布。

微软于2009年3月宣布，将在2009年6月之前，在全球停止销售Microsoft Student和所有版本的Encarta Premium软件产品，理由是人们寻求信息的方式以及传统百科全书和参考资料市场的变化是主要原因。Encarta 的更新一直提供到2009年10月。此外，MSN Encarta 网站已于2009年10月31日左右停止使用，2009年12月31日停止使用的Encarta Japan除外。现有的MSN Encarta Premium（MSN Premium 的一部分）订阅者将获得退款。Encarta 的关闭被广泛归因于来自在线百科全书领导者维基百科的竞争。

维基媒体基金会已与微软接洽，要求在免费许可下发布Encarta数据，但维基百科的联合创始人吉米·威尔士表示，“社区可能不会觉得它有用。但是，这些图像可能有用。”

## Encarta Dictionaries

<image>

Encarta Dictionaries是Encarta里的一部英文词典软件，这部词典里有词典（Dictionary）、类语辞典（Thesaurus）、5种语言词汇翻译（英语与西班牙语互译、英语与法语互译、英语与德语互译、英语与意大利语互译）、动词时态用法这4类功能。

在Encarta Dictionaries的词典功能中，绝大多数英语词汇都可点选真人词汇发音（美式发音），以便使用者知道词汇的正确读音。

## 基本资料

- 日语原文：Microsoft Encarta
- 开发者：微软公司
- 操作系统：Microsoft Windows
- 语言：英文、日文、法文、德文、西班牙文、荷兰文、意大利文、葡萄牙文（每种语言分开发售）
- 类型：多媒体百科全书
- 许可协议：专有软件
斐波那契堆

$$\Theta(1)$$ 斐波那契堆（Fibonacci heap）是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能，可用于实现合并优先队列。不涉及删除元素的操作有 $O(1)$ 的平摊时间。Extract-Min和Delete的数目和其它相比，较小时效率更佳。稠密图每次decrease key只要 $O(1)$ 的平摊时间，和二项堆的 $O(\log n)$ 相比是巨大的改进。

斐波纳契堆于1984年由迈克尔·弗雷德曼与罗伯特·塔扬提出，1987年公开发表。名字来源于运行时分析使用的斐波那契数。

## 结构

斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。

斐波那契堆中的树都是有根的但是无序。每个节点x包含指向父节点的指针px和指向任意一个子节点的childx。x的所有子节点都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的lefty和右兄弟的righty。如果节点y是x仅有的子节点，则lefty=righty=y。

斐波那契堆中所有树的根节点也用一个双向循环链表链接起来。

使用一个指针指向斐波那契堆中最小元素。

## 操作

### 建立一个新的费波那契堆

此处范例中使用的程式语言为C

每个节点x的域

- 父节点px
- 指向任一子女的指针childx——节点x的子女被链接成一个环形双链表，称为x的子女表
- 左兄弟leftx
- 右兄弟rightx——当leftx = rightx = x时，说明x是独子。
- 子女的个数degreex
- 布尔值域markx——标记是否失去了一个孩子

```
//斐波那契節點ADT
typedef struct FibonacciHeapNode {
    int key;       //節點
    int degree;    //度
    FibonacciHeapNode *left;  //左兄弟
    FibonacciHeapNode *right; //右兄弟
    FibonacciHeapNode *parent; //父節點
    FibonacciHeapNode *child;  //第一个孩子節點
    bool marked;           //是否被删除第1个孩子
} FibNode;
```

对于一个给定的斐波那契堆H，可以通过指向包含最小关键字的树根的指针minH来访问，这个节点被称为斐波那契堆中的最小节点。如果一个斐波那契堆H是空的，则minH = NIL. 在一个斐波那契堆中，所有树的根都通过left和right指针链接成一个环形的双向链表，称为堆的根表。于是，指针minH就指向根表中具有最小关键字的节点。

```
//斐波那契堆ADT
typedef struct FibonacciHeap {
    int keyNum;   //堆中節點个数
    FibonacciHeapNode *min;//最小堆，根節點
    int maxNumOfDegree;   //最大度
    FibonacciHeapNode **cons;//指向最大度的内存区域
} FibHeap;
```

创建一个空的费波那契堆，过程MAKE-FIB-HEAP 分配并返回一个费波那契堆对象H。

```
//初始化一個空的Fibonacci Heap
FibHeap *FibHeapMake() {
    return calloc(1, sizeof(FibHeap));
}

//初始化節點x
FibNode * FibHeapNodeMake() {
    FibNode *x = (FibNode *)calloc(1, sizeof(FibNode));
    x->left = x->right = x;
    return x;
}
```

### 插入一个节点

创建一个仅包含一个节点的新的斐波纳契堆，然后执行堆合并。

### 查找最小的节点

由于用一个指针指向了具有最小值的根节点，因此查找最小的节点是简单的操作。

### 合并两个斐波纳契堆

简单合并两个斐波纳契堆的根表。即把两个斐波纳契堆的所有树的根首尾衔接并置。

### 释放（删除）最小的节点

分为三步：

- 查找最小的根节点并删除它，其所有的子节点都加入堆的根表，即它的子树都成为堆所包含的树。
- 需要查找并维护堆的最小根节点，但这耗时较大。为此，同时完成堆的维护：对堆当前包含的树的度数从低到高，迭代执行具有相同度数的树的合并并实现最小树化调整，使得堆包含的树具有不同的度数。这一步使用一个数组，数组下标为根节点的度数，数组的值为指向该根节点指针。如果发现具有相同度数的其他根节点则合并两棵树并维护该数组的状态。
- 对当前堆的所有根节点查找最小的根节点。

### 降低一个节点的键值

对一个节点的键值降低后，自键值降低的节点开始自下而上的迭代执行下述操作，直至到根节点或一个未被标记（marked）节点为止：

如果当前节点键值小于其父节点的键值，则把该节点及其子树摘下来作为堆的新树的根节点；其原父节点如果是被标记（marked）节点，则也被摘下来作为堆的新树的根节点；如果其原父节点不是被标记（marked）节点且不是根节点，则其原父节点被加标记。

如果堆的新树的根节点被标记（marked），则去除该标记。

### 删除节点

把被删除节点的键值调整为负无穷小，然后执行“降低一个节点的键值”算法，然后再执行“删除最小节点”算法。

## 基本资料

- 类型：堆积
- 搜索：迈克尔·弗雷德曼、罗伯特·塔扬
- 算法：1984年
- insert_avg：$\Theta(1)$
- delete_min_avg：$O(\log n)$
- delete_min_worst：&nbsp
- find_min_avg：$\Theta(1)$
- find_min_worst：&nbsp
- decrease_key_avg：$\Theta(1)$
- decrease_key_worst：&nbsp
- merge_avg：$\Theta(1)$
- merge_worst：&nbsp
链接器

<image>

链接器（Linker），又译为链结器、连结器，是一个程序，将一个或多个由编译器或汇编器生成的目标文件外加库，链接为一个可执行文件。

在IBM大型主机比如OS/360上，链接器是linkage editor；在Unix-like系统上常用的链接器是GNU ld。目标文件是包括机器码和链接器可用信息的程序模块。简单的讲，链接器的工作就是解析未定义的符号引用，将目标文件中的占位符替换为符号的地址。链接器还要完成程序中各目标文件的地址空间的组织，这可能涉及重定位工作。

大多数现代操作系统都提供动态链接和静态链接两种形式。

## 增量链接

增量链接（Incremental Linking），是针对大型软件的源代码的很小改动就需要花费很长时间全部重新链接问题。特别是程序开发时，不可避免地要不断修改、重新编译、链接、调试程序，链接的耗时大大影响了编程者工作效率。解决办法是：所有函数不再首尾紧挨着存放在内存地址空间，而是在函数之间加上padding区域作为间隔，为函数添加几句指令稍微变长留有余地。只要函数的代码改动不大，没有超过原padding所占的空间，链接器只需延长该函数自身，这大大提高了链接的速度。还可以在可执行文件的整个.text节末尾设置一个较大的padding区域，或者使用.textbss节，用来存放修改后变大很多的函数。为了解决由此带来的函数入口地址需要重定位，在.text节中增加ILT表（Incremental Linking Table），所有的函数调用都是通过间接跳转(jum)指令实现，因此函数地址改变仅需要修改ILT表。

Visual Studio在Debug模式下具有动态编译链接功能，也即“Edit and Continue”功能。一个函数在Visual Studio中设断点或单步调试，这时该函数在.text节中；修改源代码后继续执行该函数，Visual Studio会重新编译该函数并把它加载到.textbss节中的未利用地址空间（原为padding的部分），并修改对该函数调用时跳转所用的ILT表条目以及当前EIP寄存器值。
双端队列

双端队列（deque，全名double-ended queue）是一种具有队列和栈性质的抽象数据类型。双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。

## 操作

双端队列可以在队列任意一端入队和出队。此外，经常还会有一个查看（Peek）操作，返回该端的数据而不将其出队。

操作的名称依语言的不同而不同；主流实现包括：

操作｜常见名称｜Ada｜C++｜Java｜Perl｜PHP｜Python｜Ruby｜JavaScript

尾部插入｜inject, snoc｜`Append`｜`push_back`｜`offerLast`｜`push`｜`array_push`｜`append`｜`push`｜`push`

头部插入｜push, cons｜`Prepend`｜`push_front`｜`offerFirst`｜`unshift`｜`array_unshift`｜`appendleft`｜`unshift`｜`unshift`

尾部删除｜eject｜`Delete_Last`｜`pop_back`｜`pollLast`｜`pop`｜`array_pop`｜`pop`｜`pop`｜`pop`

头部删除｜pop｜`Delete_First`｜`pop_front`｜`pollFirst`｜`shift`｜`array_shift`｜`popleft`｜`shift`｜`shift`

查看尾部｜`Last_Element`｜`back`｜`peekLast`｜`$array[-1]`｜`end`｜`<obj>[-1]`｜`last`｜`<obj>[<obj>.length - 1]`

查看头部｜`First_Element`｜`front`｜`peekFirst`｜`$array[0]`｜`reset`｜`<obj>[0]`｜`first`｜`<obj>[0]`
邻接矩阵

在图论和计算机科学中，邻接矩阵（adjacency matrix）是一种方块矩阵，用来表示有限图。它的每个元素代表各点之间是否有边相连。

作为特例，简单图的邻接矩阵是(0,1)矩阵并且对角线元素都为0。无向图的邻接矩阵是对称矩阵。图和其邻接矩阵的特征值和特征向量之间的关系是谱图理论的研究对象。

图的关联矩阵需要和邻接矩阵区分。它是图的另一种矩阵表示方式，它的元素表示各个节点-边对是否相关。还有图的度数矩阵，含有每个结点的度数信息。

距离矩阵可算是邻接矩阵的扩充。

## 定义

阶为$n$的图$G$的邻接矩阵$A$是$n \times n$的。将$G$的顶点标签为$v_1,v_2,...,v_n$。若$(v_i,v_j) \in E(G)$，$A_{ij}=1$，否则$A_{ij}=0$。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。

无向图的邻接矩阵是对称矩阵。

## 例子

### 无向图

无向图的邻接矩阵计算方法是每条边为对应的单元加上1，而每个自环加上2。这样让某一节点的度数可以通过邻接矩阵的对应行或者列求和得到。

无向图｜邻接矩阵

<image>

｜$\begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$ 从左到右、从上到下分别代表1–6节点。

### 有向图

有向图的邻接矩阵可以是不对称的。我们可以定义有向图的邻接矩阵中的某个元素Aij代表：

- 从i指向j的边的数目
- 从j指向i的边的数目

第一种定义广泛用于图论和社会网络分析（如：社会学、政治学、经济学、心理学）。第二种更加常见于其他应用学科（如：动态系统、物理、网络学），这些学科有时用邻接矩阵A表示图上的线性动力。

在第一种定义下，有向图的某个节点的入度可以通过对应的列（column）求和而得，出度可以通过对应的行（row）求和而得。在第二种定义下，入度可以通过对应的行（row）求和而得，出度可以通过对应的列（column）求和而得。

有向图｜邻接矩阵

<image>

｜$\begin{pmatrix} 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ \end{pmatrix}$ 从左到右、从上到下分别代表1–4节点。采用有向图邻接矩阵的第一种定义

## 特性

设图$G$的邻接矩阵为$A$，边的取值为1。

- 如果顶点有自我连接产生的自环（loop），则在矩阵的主对角线上会有非零的值；如果没有自环，则主对角线上全部是0。
- $A^n$的元素$A^n_{ij}$可以表示由顶点$i$到顶点$j$长度为$n$的径的数目。
- $G$没有有向圈当且仅当$I-A$可逆。$(I-A)^{-1}$的元素$ij$表示由顶点$i$到顶点$j$的所有径的数目。因为：$(I-A)^{-1} = I + A + A^2 + A^3 + ...$

## 应用

### 传球问题

A、B、C、D四人传球6次，从A开始，最终回到A手里，有多少种传法？

非矩阵解法：

- m个人传n次球，$\sum_{i=1}^{[\frac{n}{2}]}(m-1)^i (m-2)^{n-2i} C_{n-1-i}^{i-1}$
- $(m-1)P_{n+1}=1-P_{n},P_n=\frac{1}{m}(1-(\frac{-1}{m-1})^{n-1})$，将Pn乘上总传法数$(m-1)^{n}$

矩阵解法：

$$A=\begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{bmatrix}, A^6=\begin{bmatrix} 183 & 182 & 182 & 182 \\ 182 & 183 & 182 & 182 \\ 182 & 182 & 183 & 182 \\ 182 & 182 & 182 & 183 \\ \end{bmatrix}$$

### 图论算法的计算机实践

邻接矩阵法是比较简单的图论问题建模方法，它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括：

- 各元素的取值与边的输入顺序无关。
- 利用输入数据建图之前，因为不一定每对点之间都有边相连，所以先要执行将所有边的权值设为无效值的初始化步骤。以此法建模有$n$个点和$m$条边的图，其初始化需要$O(n^2)$的时间复杂度，建图的时间则为$O(m)$。
- 以此法建模有$n$个点和$m$条边的图，其内存空间开销的规模是$O(n^2)$。

主要缺点包括：

- 遍历元素时，存在的边和不存在的边都不得不检查一遍，导致遍历效率低。
- 不能存储重复的边。
- 当顶点数量多时，内存空间开销会很大。
- 存储稀疏图时会得到稀疏矩阵，空间利用率不高。
- 存储无向图时，由于此时矩阵是对称的，而对称位置上的成对元素保存的信息是重复的，导致空间利用率不高。

### 随机过程

在随机过程理论中，表示单步状态变化的转移矩阵就是一种邻接矩阵。
函式库

函式库（library）是在计算机科学中用于开发软件的子程序集合。库和可执行文件的区别是：它不是独立的计算机程序，而是向其他程式提供服务的程式码。

## 链接

库链接（linking）是指把一个或多个库包括到程序中，有两种链接形式：静态链接和动态链接；相应的，前者链接的库叫做静态库，后者的叫做动态库。

### 静态库

静态链接是由链接器在链接时将库的内容加入到可执行程序中的做法。链接器是一个独立程序，将一个或多个库或目标文件（先前由编译器或汇编器生成）链接到一块，以生成可执行程序。

静态链接的最大缺点是生成的可执行文件较大，需要更多的系统资源，在载入到内存时也会消耗更多的时间。优点是代码执行效率高。

### 共享库

共享库或共享对象是旨在被执行档和其他共享对象文件共享的文件。程式使用的模组在装载时或运行时从各个共享对象加载到内存中，而不是在为程式建立单一整体可执行档时由连结器复制。

共享库可以在编译时静态连结，这意味着在创建可执行档时解析对库模组的引用，并为模组分配内存。但通常会推迟到共享库被装载时才进行连结。

### 动态链接库

动态链接是在可执行文件装载时或运行时，由操作系统的装载程序加载库。大多数操作系统将解析外部引用（比如库）作为加载过程的一部分。在这些系统上，可执行文件包含一个叫做汇入目录（import directory）的表，该表的每一项包含一个库的名字。根据表中记录的名字，装载程序在硬盘上搜索需要的库，然后将其加载到内存中预先不确定的位置，之后根据加载库后确定的库的地址更新可执行程序。可执行程序根据更新后的库信息调用库中的函数或引用库中的数据。这种类型的动态加载称为装载（load-time）时加载，被包括Windows和Linux的大多数系统采用。装载程序在加载应用软件时要完成的最复杂的工作之一就是加载时链接。

其他操作系统可能在运行时解析引用。在这些系统上，可执行程序调用操作系统API将库的名字、函数在库中的编号和函数参数一同传递。操作系统负责立即解析然后代表应用调用合适的函数。这种动态链接叫做运行时链接。因为每个调用都会有系统开销，运行时链接要慢得多，对应用的性能有负面影响。现代操作系统已经很少使用运行时链接。

可以动态链接的函式库，在Windows上是Dynamic Link Library（DLL），在UNIX或Linux上是Shared Library。库文件是预先编译链接好的可执行文件，存储在计算机的硬盘上。大多数情况下，同一时间多个应用可以使用一个库的同一份拷贝，操作系统不需要加载这个库的多个实例。

## 参考文献

- Code: Errata:
- Article Beginner's Guide to Linkers by David Drysdale
- Article Faster C++ program startups by improving runtime linking efficiency by Léon Bottou and John Ryland
- by Baris Simsek
- BFD - the Binary File Descriptor Library
- 1st Library-Centric Software Design Workshop LCSD'05 at OOPSLA'05
- 2nd Library-Centric Software Design Workshop LCSD'06 at OOPSLA'06
- How to create shared library by Ulrich Drepper (with much background info)
- Anatomy of Linux dynamic libraries at IBM.com
随机化算法

随机化算法（randomized algorithm）是在逻辑或执行过程中使用随机性的算法。这类算法通常使用均匀随机位元作为辅助输入，以引导算法的行为，并期望在所有可能的随机选择之平均情况下取得良好效能。因此，随机化算法的执行时间、输出结果，或两者都可能是随机变数。

随机化算法可依其对正确性与执行时间的保证分为不同类型。一类算法会使用随机输入，并总是以正确答案终止，其执行时间可能根据随机选择而改变，这类算法称为拉斯维加斯算法。另一类算法通常具有固定或有界的执行时间，但可能有一定几率产生错误结果或无法得到结果，这类算法称为蒙地卡罗算法。

在实际应用中，随机化算法通常会以伪随机数生成器取代理论上的真正随机位元来源。不过，这样的实作可能会偏离理论上预期的行为与数学保证，因为某些保证可能依赖理想的真正随机数生成器。

## 早期历史

### 排序

快速排序由东尼·霍尔于 1959 年发现，并于 1961 年正式发表。同年，霍尔也发表了快速选择算法；该算法可在期望线性时间内找出列表中的中位数元素。至于是否存在确定性的线性时间选择算法，直到 1973 年才获得解答。

### 资料结构

最早的随机化资料结构之一是杂凑表。杂凑表由 IBM 的汉斯·彼得·卢恩于 1953 年提出。卢恩的杂凑表使用链接法处理冲突，是链接串列的早期应用之一。

## 例子

### 快速排序

快速排序是常见且广泛使用的算法，也是随机性发挥作用的典型例子。许多确定性版本的快速排序，对于某些类型的退化输入，例如已排序的阵列，可能需要 $O(n^2)$ 时间才能完成对 $n$ 个数的排序；实际会导致此情况的输入类型，取决于算法选择基准值的方式。

然而，若算法每次都均匀随机选取基准值，则无论输入资料本身具有何种特性，快速排序被证明有很高的几率在 $O(n \log n)$ 时间内完成。
随机函数

由于所有的计算机算法均是确定性算法，因此在电脑上的随机函数生成的都是伪随机数，不过，伪随机数和伪随机数之间也有区别，且至少可以分为两个层次：统计学伪随机数、密码学安全伪随机数。大部分编程语言库中预备了的随机函数生成的都是前一种，而密码学安全伪随机数则由一类叫做CSPRNG的随机函数生成。对于实际问题中的大部分应用，这两个不同层次的伪随机数已经可以满足大部分随机数的需求。

## 实现

### VB和ASP

通常采用`Rnd`获取，但大多数时候配合`Randomize`使用。

`Rnd`函数得出的事实上是顺序读取一个随机数列表中的数，`Randomize`的功能是重新生成随机数列表，因此一般放置于`Rnd`函数前。也有说这个函数生成的是伪随机数。

### C语言

使用`rand();`可以产生一个0~32768之间的随机整数。若要产生带有范围的随机数，可以使用`mod`运算符，例如：`rand()%15`代表产生一个0~14之间的随机整数。

## 外部链接

- MSDN Rnd 函数(英文)
- The C Library Reference Guide rand 函数(英文)