您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
关于几类图的分数色数论文.doc43页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：200 &&
你可能关注的文档：
··········
··········
论文题目：
关于几类图的分数色数
作者姓名：王 彩 虹
专业名称：应用数学
入学时间：2005 年 9 月
研究方向：数学模型与计
算机算法研究
指导教师：刘 西 奎
论文提交日期：2008 年 5 月
论文答辩日期：2008 年 6 月
授予学位日期：
称： 副 教 授
THE FRACTIONAL CHROMTIC NUMBERS OF SOME
A Dissertation submitted in fulfillment of the requirements of the degree of
MASTER OF SCIENCE
ShanDong University of Science and Technology
Wang Caihong
Supervisor: Associate Professor Liu Xikui
College of Information Science and Engineering
本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公
认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于
其它任何学术机关作鉴定。
硕士生签名：
AFFIRMATION
I declare that this dissertation, submitted in fulfillment of
the requirements for the award of Master of Science in Shandong
University of Science and Technology, is wholly my own work unless
referenced of acknowledge. The document has not been submitted for
qualification at any other academic institute.
Signature:
山东科技大学硕士学位论文
分数着色是顶点着色的一个推广，对于某些具体问题，它能更好地刻画解决。分数
色数作为图的重要参数之一，是非常具有研究价值的。
文中首先给出图的分数色数的定义，研究了简单图的和运算、正规积运算及联运算
的分数色数，并且根据顶点可迁图的分数色数研究循环图、圈的幂的分数色数及其积运
算的分数色数。从而得到各个运算的一个比较严格的上界，进而完善图的运算的分数色
数与其因子的分数色数之间的关系，得到求图的和运算、正规积运算、联运算的分数
正在加载中，请稍后...Course Description -- Probabilistic Analysis of Algorithms and Data Structures
Computer Science 308-690A
Probabilistic Analysis of Algorithms and Data Structures
September 2, 2014
Fall 2014 --- Course Syllabus
Instructor&&
Tel: (514) 398-3738 (office) |
McConnell Engineering Building, Room 300N |
Office hours: Monday and Tuesday, 10-11:30am
Teaching Assistant&&
Tel: TBA |
McConnell Engineering Building, Room 109 |
Office hours: Tuesday, Friday, 11-12am, or by email appointment.
Location&&
Monday, Wednesday 8:30--10am. McConnell Engineering, room 320.
Lectures start September 3, 2014 and run until December 4, 2014.
Special dates:
Lectures that will be moved to another time: Sep 22, 24; Oct 6, 8; Nov 3, 5.
Replacement lectures, on Fridays, 8:30-10am: Sep 12, 19; Oct 17, 24, 31; Nov 14.
No lecture on Thanksgiving, Oct 13.
Special McGill-imposed lecture on Thursday, Dec 4 from 8:30-10. This is also the last day of classes.
Description&&
This course looks at basic methods for analyzing the
average behavior of algorithms and data structures.
It is shown how conventional and modern probability theoretical
techniques can be used in this respect. The list of topics
does not pret rather, it is selected to
give a broad horizontal view of possible applications.
The students should be familiar with elementary concepts in
probability theory and data structures.
Contents&&
Binary search trees
Connection with the theory of records.
Analysis of depth and height.
Quadtrees, k-d trees, union-find trees.
Introduction to branching processes, branching random walks.
Divide-and-conquer
Expected time analysis of divide-and-conquer methods.
Algorithms for outer layers and convex hulls.
Analysis of the cardinality of the random convex hull.
Randomized algorithms
Introduction to the methodology.
Finding the k-th largest quickly on the average.
Exponential large deviation inequalities.
Closest point problems.
Random incremental algorithms.
Randomzed approximation algorithms.
Conditional branching processes
Analysis of simple families of random trees.
Random graphs
Random graphs, independent sets, coloring.
The second moment method.
Analysis of simple heuristics for graph problems.
Linear expected time connectivity algorithm.
Properties of sparse random graphs.
The Erd&s-R&nyi theorem on connected graphs.
Random geometric graphs, the Gilbert disc model, percolation.
Combinatorial search problems
Euclidean traveling salesman problem.
Assignment problems.
Martingales and the bounded differences method.
Concentration inequalities.
Markov chains
Basic properties.
Markov chain Monte Carlo.
Generating random combinatorial objects.
Rapid mixing. Mixing time.
Entropy, coding and compression.
Entropy and random tries.
Digital search trees.
Random walks
Random walks for analyzing trees.
Bin packing heuristics.
Hashing, bucketing
Analysis of various hashing algorithms.
Influence of non-uniform distributions.
Maximal occupancy.
Paradigm of two choices.
Evaluation&&
About 9 sets of theoretical problems will be assigned.
Textbook&&
There is no specific textbook. Course notes
will be handed out.
Selected references&&
Some of the course material is based upon parts of
the following references.
J. Spencer,
and P. Erd&s,
The Probabilistic Method,
John Wiley,
B. Bollobas,
Random Graphs,
Academic Press,
L. Devroye,
"Branching processes in the analysis of the heights of trees,"
Acta Informatica,
pp. 277--298,
L. Devroye,
"Applications of the theory of records in the study of random trees,"
Acta Informatica,
pp. 123--130,
S. Janson,
T. Luczak,
A. Rucinski,
Random Graphs,
Wiley-Interscience,
R. M. Karp,
"The probabilistic analysis of some combinatorial search algorithms,"
in: Algorithms and Complexity,
J. F. Traub,
pp. 1--19,
Academic Press,
R. M. Karp
and J. M. Steele,
"Probabilistic analysis of heuristics,"
in: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys,
pp. 181--205,
John Wiley,
D. E. Knuth,
The Art of Computer Programming, Vol. 3 : Sorting and Searching,
Addison-Wesley,
Reading, Mass,
H. M. Mahmoud,
Evolution of Random Search Trees,
John Wiley,
R. Motwani
and P. Raghavan,
Randomized Algorithms,
Cambridge University Press,
E. M. Palmer,
Graphical Evolution,
John Wiley,
Heuristics. Intelligent Search Strategies for Computer Problem Solving (Chapter 5),
Addison-Wesley,
Reading, Mass,
W. Szpankowski,
Average Case Analysis of Algorithms on Sequences,
Springer-Verlag, New York, 2001.
J. S. Vitter
and P. Flajolet,
"Average-case analysis of algorithms and data structures,"
in: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity,
J. van Leeuwen,
pp. 431--524,
MIT Press,
Amsterdam,}