中国科大学位与研究生教育
课程名称: 教师:
当前位置:
 >> 
 >> 
Covering Perfect Hash Families
Covering Perfect Hash Families
教师介绍

本讲教师:Charles J. Colbourn
所属学科:理科
人  气:310

课程介绍
Abstract: Covering arrays are used to test the correctness of complex engineered systems with k components each having v options, when collections of at most t component options can cause failures. Of most interest are cases when 2 ≤ t ≤ 6 and 2 ≤ v ≤ 10, but kcan be quite large, perhaps in the hundreds or thousands. The construction of covering arrays with few tests is a challenging mathematical and computational problem. Covering perfect hash families represent certain covering arrays compactly. In this talk we describe how covering perfect hash families lead to an improvement upon the best known asymptotic upper bound for the minimum number of tests (rows) in a covering array with v symbols, k columns, and strength t. We then show that the compact representation makes the computation of ‘large’ covering arrays meeting the new bound feasible: One method uses the deterministic Lov′asz local lemma, another uses a conditional expectation approach. For example, we report on improved bounds for covering arrays of strength 3 with k ≤ 10000, and demonstrate that the methods remain feasible even for strength 7, for which no explicit computational results have earlier been reported.We close by outlining connections with ?nite ?elds and ?nite geometry, and suggestsome important next steps.This is joint work with Erin Lanus and Kaushik Sarkar (ASU).

评论

针对该课程没有任何评论,谈谈您对该课程的看法吧?
  • 用户名: 密 码:
致谢:本课件的制作和发布均为公益目的,免费提供给公众学习和研究。对于本课件制作传播过程中可能涉及的作品或作品部分内容的著作权人以及相关权利人谨致谢意!
课件总访问人次:9418870
中国科学技术大学研究生网络课堂试运行版,版权属于中国科学技术大学研究生院。
本网站所有内容属于中国科学技术大学,未经允许不得下载传播。
地址:安徽省合肥市金寨路96号;邮编:230026。TEL:+86-551-63602922;E-mail:wlkt@ustc.edu.cn。