lecture6-06
- 格式:pdf
- 大小:351.34 KB
- 文档页数:63
队列网络两种不同形式的网络已知量估计量开放式关闭式12•因特网流量•急诊室(Denardo )•美食广场•飞机场(抵达、检票、安检、护照、控制、通道、登机)•有一系列生产系统,但没有物料控制的工厂.例子开放式网络3人例子开放式网络美食广场入口人Sbarro 比萨TCBY 冷冻酸乳酪麦当劳餐桌出口人和盘子4•通过保持恒定数量的项目来进行物料控制的工厂(CONWIP )•有限个固定设备的工厂例子封闭式网络杰克逊网络队列网络经常被建模成杰克逊网络。
•易于计算性能(系统容量、系统中平均时间、平均队列长度)。
•易于理解•易于进行设计优化•对大规模的系统有效…5杰克逊网络•…但也有其不足之处。
要求存储区必须是足够大的(例如:大到从不出现堵塞)67开放式杰克逊网络ii K i i µα==提供单一服务的站点站点的服务率--指数分布站点的到达率--泊松分布01()1()r Ki ij r j P i j P P P i ===−=∑ij P 顾客离开站点到下一站点顾客在离开站点后退出系统:12,P 0i >i0注释、从概率角度讲,顾客被不能辨别、顾客的行程是无记忆的3、在每一个站点都遵守先到先服务(FCFS)的原则4、至少对于一个有例子89开放式杰克逊网络的解决方案i i λ=站点的有效到达率在孤立情况下站i 内平均等待时间流量方程(流入量=流出量)令稳态概率站点i 内处于稳态的顾客数量生产形式解决方案(行向量)是单一M/M/1队列中n 项的概率(1)nρρ−10注释1)杰克逊猜想并验证了站点的流出量=站点的流入量2)每一站点的输入看上去像服从泊松分布,但如果路径中有反馈,则这种输入就不服从泊松分布3)在没有顾客插队的情况下,系统中平均等待时间=在孤立状态下在各站点平均等待时间之和4)生产形式解决方案适于处理提供多种服务的站点(...)i k n n (...)i k n n,有:12封闭式杰克逊网络(续)生产形式解决方案这里,校正常数是1kijij i ii iλλρλλρµ===∑i 流量方程只能被解释成一个比例常数通过体现出相关性令13Buzen 算法第一步:定义一个辅助方程第二步:设计一个关于以及在j 上的代数和的递归关系条件k X j =11{0:...}(,)()*()Ki Ki i i X X XN n i i iC K N f X f X πρ=≥++===∑改变了符号目标:Buzen算法(续)第三步:初始化没有顾客时一个节点顾客第四步:填充k×N矩阵站从左上角开始,从上至下填写,15封闭式网络简单的FMS 模型另外转换站装载/卸载转换站Otherwise16生产率为:并且在这种情况下C(M , N )很容易计算封闭式网络简单的FMS 模型。
lecture的意思用法大全lecture的意思n. 演讲,训斥,教训vi. 作演讲vt. 给…作演讲,教训(通常是长篇大论的)变形:过去式: lectured; 现在分词:lecturing; 过去分词:lectured;lecture用法lecture可以用作名词lecture主要指教育性或学术性“演讲”,引申可指“冗长的训斥或谴责”。
lecture是可数名词,其后接介词on或about ,意为“关于…的演讲”“就…做演讲”“因…训斥或谴责某人”。
lecture作“讲演,讲课”解时,是不及物动词。
说“讲授某课程”时常与介词on连用,说“在某地讲演”时常与介词at〔in〕连用。
lecture用作名词的用法例句She ran over her notes before giving the lecture.她讲课前把讲稿匆匆看了一遍。
His lecture covered various aspects of language.他的讲课涉及到语言诸方面的问题。
They could not follow the lecture.他们听不懂这次演讲。
lecture可以用作动词lecture作“讲演,讲课”解时,是不及物动词。
说“讲授某课程”时常与介词on连用,说“在某地讲演”时常与介词at〔in〕连用。
lecture也可用作及物动词,意思是“向…讲演,给…讲课”,接名词或代词作宾语。
lecture还可作“责备”“教训”“训斥”解,用作及物动词,接名词或代词作宾语。
“因…而受到训斥”可说lecture sb for n./v -ing。
lecture用作动词的用法例句It was a shame for me to be lectured in front of the whole class.当着整个班级的面被训斥了一顿,真让我感到羞辱。
He lectured to his students on modern writers.他给学生们讲了关于现代作家的一课。
lecture的用法和短语例句lecture有讲课;演讲;训话等意思,那么你知道lecture的用法吗?下面店铺为大家带来有关lecture的用法和短语例句,供大家参考学习!lecture的用法:lecture的用法1:lecture主要指教育性或学术性“演讲”,引申可指“冗长的训斥或谴责”。
lecture的用法2:lecture是可数名词,其后接介词on或about ,意为“关于…的演讲”“就…做演讲”“因…训斥或谴责某人”。
lecture的用法3:lecture作“讲演,讲课”解时,是不及物动词。
说“讲授某课程”时常与介词on连用,说“在某地讲演”时常与介词at〔in〕连用。
lecture的用法4:lecture也可用作及物动词,意思是“向…讲演,给…讲课”,接名词或代词作宾语。
lecture的用法5:lecture还可作“责备”“教训”“训斥”解,用作及物动词,接名词或代词作宾语。
“因…而受到训斥”可说lecture sb for n./v -ing。
lecture的常用短语:用作动词 (v.)lecture about〔on〕 (v.+prep.)lecture at (v.+prep.)lecture for (v.+prep.)lecture的用法例句:1. Chuck would lecture me, telling me to get a haircut.查克就会数落我,让我去理一下发。
2. Within this lecture I cannot pretend to deal adequately with dreams.在这一次讲座中,我不敢自诩能对梦境作透彻的分析。
3. Our captain gave us a stern lecture on safety.船长就安全问题严厉地训斥了我们一顿。
4. We picked up our conference materials and filed into the lecture hall.我们领了会议材料后鱼贯进入讲演厅。
lecture6译文(1)WuxiWuxi is a small city in Jiangsu Province of the South, situated between Nanjing and Shanghai. As early as 6,000 years ago, there had been a primitive tribe settled here. Today' s Wuxi began to be built in the second century B.C. At that time tin ore was excavated from Xishan southwest of the city. After the discovery of tin, people started to call this place"Youxi". As time passed by, the tin mine ran out and "Youxi" was changed to "Wuxi". Wuxi is a small city in South China' s Jiangsu Province, located mid-way between Nanjing and Shanghai. Established as early as 6,000 years ago by a primitive clan tribe, the present city was first built in the second century B.C. when tin was mined from a hill in the southwest named Xishan. After tin was discovered there, the place began to be called Youxi, literally "has tin", and with the passage of time, the tin was mined out and the name was changed to Wuxi, meaning "no tin".Wuxi faces the Taihu Lake in the south and leans against the Huishan Mountain in the west, both of which are the major local scenic spots. Besides, the old Jing-Hang Grand Canal and the Jing-Hu Railway pass through here. Wuxi is bordered by Taihu Lake on the south, and Huishan Hill in the west. They are the major scenic spots there. In addition, the ancient Grand Canal from Beijing to Hangzhou was dug to run through the city, as was the Beijing-Shanghai Railway.As one of the five large freshwater lakes in China, the T aihu Lake has a water area of 36,000 square hectares, with about 100 small islands and 72 mountain peaks along its shore. Several thousand years ago, here used to be a shallow water bend. Lateron the Changjiang Delta gradually expanded and connected with the dikes and dams in the gulf, thus forming an interior lake and turning the original isles into mountain peaks. With its misty water, the Taihu Lake is surrounded by grotesque peaks. This nature-made scenery of lakes and mountains is so beautiful that one simply cannot take them all in. The Taihu Lake is one of the five largest freshwater lakes in China. Covering a water area of 36,000 hectares, it has scores of islets and 72 peaks along its banks. Thousands of years ago, the lake was a shallow bay. Later the gradually expanding Yangtse Delta linked with the dykes in the bay and turned it into an inland lake and the original islets into the peaks along the water. The mist-covered surface of the water and surrounding peaks make Taihu a splendid natural landscape of mountains and lakes.The part of the Grand Canal in Wuxi is 40 kilometres long, of which 14.6 kilometres is in the urban area. With a history of over 2,400 years, this green chain of water is still running merrily, with many places of historic interest and scenic beauty along its bank. The cutting of this canal dated back to the 5th century B.C. and its full length is 1,794 kilometres. Like the 10-thousand-li Great Wall, it is also the symbol of China's ancient civilization. The Wuxi section of the Grand Canal is 40 kilometres long, with 14.6 kilometres in the city area. With a history of more than 2,400 years, this green belt of water still flows pleasantly with many scenic spots and historical sites on both banks. The Grand Canal was first dug in the 5th century B.C. and is 1,794 kilometres. Like the Great Wall, this project is a symbol of ancient Chinese civilization.The Canal is both narrow and deep in Wuxi, and along the two banks there are rows of old-style dwelling houses with greentiles and white walls. The canal at Wuxi is narrow and deep, and row upon row of old residential buildings with white walls and black tiles stand along both sides.Every year there are many tourist activities in Wuxi and from 8th to 14th this October, there will be a "Wuxi Taihu International Fishing Competition, "which can be entered for by both individuals and groups, professionals and amateurs. Wuxi arranges many tourist programmes each year and during the coming October 8--14, there is a"Wuxi Taihu International Angling T ournament". Catering to both professionals and amateurs, the contest can either be entered in group or singles.译文二WuxiWuxi is a small city in South China' s Jiangsu Province, located mid-way between Nanjing and Shanghai. Established as early as 6,000 years ago by a primitive clan tribe, the present city was first built in the second century B.C. when tin was mined from a hill in the southwest named Xishan. After tin was discovered there, the place began to be called Youxi, literally "has tin", and with the passage of time, the tin was mined out and the name was changed to Wuxi, meaning"no tin".Wuxi is bordered by Taihu Lake on the south, and Huishan Hill in the west. They are the major scenic spots there. In addition, the ancient Grand Canal from Beijing to Hangzhou was dug to run through the city, as was the Beijing-Shanghai Railway.The Taihu Lake is one of the five largest freshwater lakes in China. Covering a water area of 36,000 hectares, it has scores of islets and 72 peaks along its banks. Thousands of years ago, the lake was a shallow bay. Later the gradually expanding Yangtse Delta linked with the dykes in the bay and turned it into an inlandlake and the original islets into the peaks along the water. The mist-covered surface of the water and surrounding peaks make Taihu a splendid natural landscape of mountains and lakes.The Wuxi section of the Grand Canal is 40 kilometres long, with 14.6 kilometres in the city area. With a history of more than 2,400 years, this green belt of water still flows pleasantly with many scenic spots and historical sites on both banks. The Grand Canal was first dug in the 5th century B.C. and is 1,794 kilometres. Like the Great Wall, this project is a symbol of ancient Chinese civilization.The canal at Wuxi is narrow and deep, and row upon row of old residential buildings with white walls and black tiles stand along both sides.Wuxi arranges many tourist programmes each year and during the coming October 8--14, there is a"Wuxi Taihu International Angling Tournament". Catering to both professionals and amateurs, the contest can either be entered in group or singles.第六讲主语的确定汉语:意合语言,重意念,轻形式英语:行合语言,重形式,讲逻辑如何确立主语?一、补充主语汉语句子中主语旺旺不突出,很多句子为无主句。
Lecture 6. Early Buddhist Art in ChinaContent1.Devotion belief of Maitreya2.Sinicization in early Chinese Buddhist Art2.1.Sinicization policy in the Northern Wei2.2.Yungang Grottoes2.3.Longmen Grottoes◎E-Resources :1. Timeline and Maps of China :/chinaciv/timeline.htm2. Timeline of Chinese History and Dynasties [Asia for Educators]/tps/1000bce.htm3. Database for Buddhist Cave Temples in Chinahttp://dsr.nii.ac.jp/china-caves/index.html.en4. Chinese Symbols and Art Motifs/chinese-symbols.html5. How to identify a Buddhist images :/002F/index.htm◎Readings :[Maitreya]Jaini, Padmanabh S. “Stages in the Bodhisattva Career of the Tathāgata Maitreya.” In Maitreya, the Future Buddha. Edited by Alan Sponberg and Helen Hardacre, 54–90. New York: Cambridge University Press, 1988.Kim, Inchang.The future Buddha Maitreya : an iconological study,New Delhi : D.K. Printworld, 1997, [294.342113 K49]Kitagawa, Joseph M. “The Many Faces of Maitreya: A Historian of Religions’ Reflections.” In Maitreya, the Future Buddha. Edited by Alan Sponberg and Helen Hardacre, 7–22. New York: Cambridge University Press, 1988.Lancaster, Lewis. “Maitreya.” In The Encyclopedia of Religion. 2d rev. edition. V ol.8. Edited by Lindsay Jones, Mircea Eliade, and Charles J. Adams. Detroit: Macmillan Reference USA, 2005.[Sinicization]ALEXANDER C. SOPER, IMPERIAL CA VE-CHAPELS OF THE NORTHERN DYNASTIES: DONORS, BENEFICIARIES, DATES , Artibus Asiae, V ol. 28, No.4 (1966), pp. 241-270ARPUTHARANI SENGUPTA, CULTURAL SYNTHESIS IN THE BUDDHIST ART OF CHINA, E-resources : http://ignca.nic.in/ks_41026.htmKatherine R. Tsiang, Changing Patterns of Divinity and Reform in the Late Northern Wei, The Art Bulletin, V ol. 84, No. 2, Jun., 2002 .Liu, Hongshi. "Early Chinese Buddhist stone carvings." Chinese Literature 4 (April 1982): 130-135.Rhie, Marylin M. "Late Sui Buddhist sculpture: a chronology and regional analysis." Archives of Asian Art 35 (1982): 27-54.Caswell, James O. Written and Unwritten: A New History of the Buddhist Caves at Yungang. Vancouver: University of British Columbia Press, 1988.Caswell, James D. "The 'Thousand-Buddha' pattern in caves XIX and XVI atYun-kang," Ars Orientalis 10 (1975):35-54.Chen, C.M. Buddha's statues in the Yunkang caves. Berkeley: [the author], 1977. Gabain, A. Annemarie von. "Types of arhats on a series of wall paintings from Turfan," Memoirs of the Research Department of the Toyo Bunko 33 (1975):161-9.Huntington, John C. "The iconography and iconology of the 'Tan Yao' caves at Yungang." Oriental Art 32:2 (Summer 1986): 142-160.Knauer, Elfriede Regina. The fifth century A.D. Buddhist cave temples at Yun-kang, North China: a look at their western connections." Expedition 25:4 (Summer 1983): 27-46.★James C. Y. Watt, Art and History in China from the Third to the Eighth Century, in China : Dawn of a Golden Age, 200-750 AD, New York : Metropolitan Museum of Art ; New Haven : Yale University Press, c2004. [LB 709.21 C5 W ]★Leidy, Denise Patry, The art of Buddhism : an introduction to its history and meaning, Boston : Shambhala, 2008. Chap.3, [704.948943 L52 a]Soper, Alexander C. Literary evidence for early Buddhist art in China. Ascona, Switzerland: Artibus Asiae Publishers, 1959.WU, HUNG, BUDDHIST ELEMENTS IN EARLY CHINESE ART (2nd and 3rd Centuries), Artibus Asiae, V ol. 47, No. 3/4 (1986), pp. 263-303+305-352"Stone Sculptures of the Northern Wei Dynasty." Arts of Asia 25:5 (1995):134.【E-resources】Video from web :Yungang Grottoes/program/newsupdate/20100930/104106.shtml※Glossary of Chinese Art/china/glossary.htmlGao gu you si miao高古游絲描Archaic floating gossamer threadsAo-tu painting technique凹凸畫法in the Western Regions‘ convex-concave technique 凹凸畫法is used, first creating an ink outline and then applying color shading to show a three dimension of pictureBao yi bo dai褒衣博帶: Confucian-style loose robe with a broad sashXiu gu qing xiang秀骨清像: graceful and elegant lookSome famous artists in the 3-6 century1.Dai Kui 戴逵, (326-396)2.Gu Kaizhi顧愷之, (344-405)3.Cao Zhongda曹仲達, (active in Northern Qi dynasty, ca.550-577)4.Zhang Sengyao張僧繇. (502-549)5.Lu Tanwei 陸探微(?-485)Basic Terms in Chinese PAINTINGS and CALLIGRAPHY Formats:hanging scrolls: vertically proportioned for hanging on wallshandscrolls: h orizontal scrolls viewed section by section (right to left) on a table fan: oval with a handle or folded and set in a frame; can be removed from holder and mounted in an albumalbum: paintings mounted on individual leaves in book-like form Materials:silk: smooth, fine fabric made from cocoons of silkworms in China since Neolithic timespaper: made in China since at least the Han dynasty of a variety of fibrous materials, such as mulberry bark and hempbrush: used in China since Neolithic times and made with a pointed tip and in many sizes of a variety of materials, such as rabbit, goat, and weasel hairink: made of pine soot or lampblack combined with glue and pressed into cakes or sticks in dried form, which must be ground with water for usecolor pigments: water-based and derived primarily from plants and minerals◎Key Images : (The images are collected from public domain and used only for education purpose only.)◎Iconography of Maitreya◎◎◎◎◎◎◎◎◎◎◎Sinicization in the Northern WeiYungang Grottoes (雲崗石窟)The Buddhist statues (cave 20) Yungang Grottoes in Datong, Shanxi Province. Yungang Grottoes (雲崗石窟)(cave 16, Yungang Grottoes) Bao yi bo dai褒衣博帶: Confucian-style loose robe with a broad sashYungang Caves, Datong, Shanxi Province Cave 9, AntechamberNorth Wall, Top of DoorNorthern Wei, Late 5th Century Sandstone, Photograph taken in 1982 Huntington Archive Image Scan # C7193Buddha, Yungang Cave 5,Longmen Cave 19, Fengxian Temple, at Longmen,Tang (early 670's CE, 672 CE - 675 CE) Material: grey limestone , Dimensions: H - ca. 55.00 ftCopyright Holder: Huntington, John C. and Susan L.Guyang Grotto 古陽洞Northern Wei Dynasty 493-534 AD; the oldest cave at Longmen(Binyang cave, Longmen grottoes, 龍門石窟賓陽中洞Luoyang, Henan province)Longmen Grottoes, Fengxian Tample, 奉先寺, Tang dynasty.Binyang Cave, Longmen 龍門賓陽洞Gong Xian County Grottoes 鞏縣石窟is in the Northern Wei Dynasty another great treasure house of Buddhist art besides the Longmen Grottoes. It is located in Luoyang northeast about 55 km(500-503AD).Northern Wei :Buddha's monk's robe covering both shoulders, with thin underrobe and knotted cross-tie (a loose gown with wide girdle褒衣博帶),flowing in patterned folds over his throne;。
贪心法(Greedy Approach)基本思想算法设计设计要素与动态规划法的比较正确性证明得不到最优解的处理办法应用实例1基本思想实例:最小生成树的Kruskal算法,活动选择问题适用问题:组合优化问题,满足优化原则设计方法:多步判断,解为判断序列选择依据:是否满足约束条件局部优化测度使用贪心法要解决的问题:是否可以得到最优解?不能得到最优解,解与最优解的误差估计2例1活动选择问题S={1, 2, …, n}为n项活动的集合s i, f i分别为活动i 的开始和结束时间≥f j或s j≥f i活动i 与j相容当且仅当si求最大的两两相容的活动集思路:按结束时间递增顺序将活动排列为1,2,…,n, ≤f2≤…≤f n使得f1按照标号从小到大选择3定理1 算法Select 执行到第k步, 选择k项活动i1= 1, i2, …, ik, 那么存在最优解A包含i 1=1,i2, …, ik正确性证明根据定理:算法至多到第n步得到最优解67•证明存在最优解包含活动1•假设按照算法前k 步选择都导致最优解,证明第k +1步选择也导致最优解1. 第k 步:选择活动i 1=1, i 2, …, i k2. 归纳假设:存在最优解A ={i 1=1, i 2, …, i k }∪BB 是剩下的待选活动集S ’的一个最优解3. 由归纳基础,存在S ’的最优解B’包含i k +14. 由|B’|=|B | 知A’={i 1=1, i 2, …, i k }∪B’最优5. A’={i 1=1, i 2, …, i k , i k +1}∪(B’-{i k +1})最优. 对步数进行归纳的证明思路贪心算法的设计适用:满足优化原则的组合优化问题问题求解表示成多步判断整个判断序列对应问题的最优解子序列对应子问题的最优解贪心选择:确定一个优化测度不考虑以前的选择,只与当前状态有关以优化测度的极大(或极小)作为依据10贪心算法的设计(续)确定是否满足贪心选择性质具有贪心选择性质得到最优解,否则为近似解证明:贪心选择会导致最优解一般采用归纳法加以证明对算法步数归纳对问题规模归纳自顶向下计算通过贪心选择,将原问题规约为子问题线性表记录选择的结果1112数学归纳法叙述一个可以归纳证明的命题:•对步数k 归纳对于任意k ,k 步贪心选择得到i 1,i 2,…,i k , 那么存在最优解包含i 1,i 2,…,i k •规模k 归纳:对于任意k ,贪心法得到关于规模为k 的问题的最优解归纳基础:k =1, 命题为真归纳步骤:假设对<k 的正整数命题为真,证明对k 命题也为真贪心选择性质的证明13ni x cxw x i i n i i n i i ,...,2,11,0max11==≤∑∑==贪心法:将集装箱按照从轻到重排序,轻者先装例2最优装载Loadingn 个集装箱1,2,…,n 装上轮船,集装箱i 的重量w i , 轮船装载重量限制为c ,无体积限制. 问如何装使得上船的集装箱最多?不妨设w i ≤c .贪心选择性质证明思路•设集装箱标号按照从轻到重记为1, 2, …, n •对问题规模n 进行归纳•n=1, 贪心选择得到最优解(只有一个箱子)•假设对于规模为n-1的输入得到最优解,证明对规模为n的输入也得到最优解14说明Loading算法复杂性T(n) = O(n log n)Loading问题是0-1背包问题的特例:= 1, i=1, 2, …, n.即vi该问题是O(n log n) 时间可解的0-1背包问题是NP难的。
16贪心法得不到最优解的处理办法讨论对于哪些输入贪心选择能够得到最优解输入应该满足的条件讨论贪心法的解最坏情况下与最优解的误差绝对误差与相对误差估计17确定得到最优解的输入所满足的条件例3找零钱问题设有n种零钱,重量分别为w1, w2, ... , wn,价值分别为v1=1, v2, ... , vn.付的总钱数是y如何付钱使得所付钱的总重最轻?1821n=2时得到最优解F 1(y ) =G 1(y ) F 2(y ) = G 2(y ))(])([])([])([)]())(([2212212222122222212222122221≤+−=+−=+−−++−−=+−−+++−w v w w v w x w x v y w w x w v x v y w x w x v y F x w x v y F δδδδδδδ22定理2 假定G k (y )=F k (y ),v k +1>v k 且v k +1=pv k -δ, 0≤δ<v k , p ∈Z +, 则以下命题等价.kk k k k k k k k k k pw G w pv F pv G y F y G y G y G ≤+==≤++++++)()4()()()3()()()2()()()1(111111δ用条件(4) 需O (k ) 时间验证G k +1(y )=F k +1(y )?对n 种零钱作出验证, 可在O (n 2) 时间内完成n >2时得到最优解的判定条件25例4装箱问题有n 个物体, 长度分别为a 1, a 2, ... , a n , a i ≤1, i =1,2,…,n . 要把它们装入长为1的箱子(只考虑长度的限制)问至少需要多少只箱子?mj B C B C a mj n i mj j i ,...,2,1,1)()(min 11=≤=∑∑==,C (B j )称为箱子B j 的装入量1—C (B j )称为箱子B j 的空隙近似解的误差估计例5最优二元前缀码问题前缀码:用0-1字符串作为代码表示字符,要求任何字符的代码都不能作为其它字符代码的前缀非前缀码a---001, b---00, c---010, d---010100001: 01, 00, 001 d, b, a010, 00, 01 c, b, d前缀码的存储采用二叉树的结构,每个字符作为树叶,每个前缀码看作根到树叶的路径, x2, …, x n,输入:n个字符x1), i=1, 2, …, n.每个字符传输概率f(xi求:前缀码,使得平均传输一个字符的位数达到最小算法:Huffman树得到最优解3234例如a :45, b :13; c :12; d :16; e :9; f :5, Huffman树为平均位数:4*5%+4*9%+3*16%+3*12%+3*13%+1*45% = 2.24编码:f --0000, e --0001, d --001, c --010, b --011, a --1正确性证明•证明存在一个对应于最优前缀码的二叉树,以最小的频率为树叶,且这两片树叶是兄弟•证明x, y 是树叶兄弟,z 是x, y 的父亲,z 的频率f[z]=f[x]+f[y], 令T’= T−{ x, y },则T’是对应于最优前缀码C’=(C−{ x, y })∪{ z }的树3536则T 与T ’的权之差为其中d T (i )为i 在T 中的层数(i 到根的距离)∑∑≥−=−∈∈Ci Ci T T i d i f i d i f T B T B 0)(][)(][)'()('引理1设C 是字符集,∀c ∈C , f [c ]为频率,x , y ∈C , f [x ], f [y ]频率最小,那么存在最优二元前缀码使得x , y 的码字等长,且仅在最后一位不同.T →T’f [y ] ≤f [c ]f [x ] ≤f [b ]b 与x 交换c 与y 交换37引理2 设T 是最优解对应的树,∀x , y ∈T , x , y 是树叶兄弟,z 是x ,y 的父亲,z 的频率f [z ]=f [x ]+f [y ], 令T’=T −{x , y }, 则T’是对应于最优前缀码C’= (C −{ x , y })∪{ z } 的树证明:∀c ∈C −{ x , y }, 有d T (c )=d T ’(c ) ⇒f [c ]d T (c )=f [c ]d T ’(c ) 由d T (x ) =d T (y ) = d T ’(z ) +1得f [x ] d T (x ) + f [y ] d T (y ) = (f [x ] + f [y ]) (d T ’(z ) + 1)= f [z ]d T ’(z ) + (f [x ] + f [y ])从而B (T ) = B (T ’) + f [x ] + f [y ]若T ’不是关于C ’的最优树,那么存在T*使得B (T*)<B (T ’), z 是T*中的树叶,将x, y 加到z 上作为儿子,那么得到B (T*) + f [x ] + f [y ] < B (T )与T 的最优性矛盾。
定理3 Haffman 算法得到最优前缀码算法•Huffman树的算法•时间O(n log n)42实例44对步数归纳命题:对于任意k < n, 存在一棵最小生成树包含算法前k 步选择的边k=1, 存在一棵最小生成树T 包含边e={1,i}, 其中{1,i}是所有关联1的边中权最小的.设T 为一棵最小生成树,假设T 不包含{1,i}, 则T∪{{1,i}}含有一条回路,回路中关联1的另一条边为{1,j},令T’=(T-{{1,j}})∪{{1,i}},则T’也是生成树,且W(T’)≤W(T).Prim算法的正确性证明45Prim算法的正确性证明(续)归纳步骤,e2,…,e k-1, 这假设算法进行了k-1步,生成树的边为e1些边的k个端点构成集合S. 由归纳假设存在G的一棵最小生成树T包含这些边., 则i k+1到S中顶点的边权最小,算法第k步选择了顶点ik+1={i k+1,i l}。
假设T不含有{i k+1,i l},则将e k加设这条边为ek到T中形成一条回路. 这条回路有另外一条连接S与V-S},则T*是G的一棵生中顶点的边e, 令T*=(T-{e})∪{ek,e2,…,e k, 且W(T*)≤W(T).成树,包含了e1时间T(n)=O(n2)46实例4849对顶点数归纳命题:对于任意n , 使用Kruskal 算法对于n 阶图得到一棵最小生成树.证明n =2, 只有一条边,命题显然为真.假设对于n 个顶点的图算法正确,考虑n +1个顶点的图G , G 中最小权边e ={ i , j }.从G 中短接i 和j ,得到图G ’为n 个顶点的图. 根据归纳假设,由算法存在G ’的最小生成树T ’.令T =T ’∪{e }, 则T 是关于G 的最小生成树.Kruskal算法的正确性证明Kruskal算法正确性证明(续)若不然,存在一棵G的最小生成树T*,W(T*)<W(T). 如果e 属于T*, 则短接e 得到G’的生成树T*−{e}, 且W(T*−{e})<W(T ’), 与T ’的最优性矛盾;如果e不属于T*, 在T*中加上边e,形成回路.去掉回路中任意别的边所得生成树的权小于W(T*),与W(T*)的最小性矛盾.时间:T(m)=O(m log m)50。