搜索三个不同坏硬币的测试次数

§1.简介 设S={c_1,c_2,…,c_n}是由n个外观相同的硬币组成的集合,其中恰有m个稍重的坏硬币,试用最少的测试次数找出这m个坏硬币.以μ_m(n)表示最少测试次数,由信息论可知     

Adaptive spatial information-theoretic clustering for image segmentation

The incorporation of spatial context into clustering algorithms for image segmentation has recently received a significant amount of attention. Many modified clustering algorithms have been proposed and proven to be effective for image segmentation. In this paper, we propose a different framework for incorporating spatial information with the aim of achieving robust and accurate segmentation in case of mixed noise without using experimentally set parameters based on the original robust information clustering (RIC) algorithm, called adaptive spatial information-theoretic clustering (ASIC) algorithm. The proposed objective function has a new dissimilarity measure, and the weighting factor for neighborhood effect is fully adaptive to the image content. It enhances the smoothness towards piecewise-homogeneous segmentation and reduces the edge blurring effect. Furthermore, a unique characteristic of the new information segmentation algorithm is that it has the capabilities to eliminate outliers at different stages of the ASIC algorithm. These result in improved segmentation result by identifying and relabeling the outliers in a relatively stronger noisy environment. Comprehensive experiments and a new information-theoretic proof are carried out to illustrate that our new algorithm can consistently improve the segmentation result while effectively handles the edge blurring effect. The experimental results with both synthetic and real images demonstrate that the proposed method is effective and robust to mixed noise and the algorithm outperforms other popular spatial clustering variants.     

Oblivious Transfers and Privacy Amplification

Oblivious transfer (OT) is an important primitive in cryptography. In chosen one-out-of-two string OT, a sender offers two strings, one of which the other party, called the receiver, can choose to read, not learning any information about the other string. The sender on the other hand does not obtain any information about the receivers choice. We consider the problem of reducing this primitive to OT for single bits. Previous attempts to doing this were based on self-intersecting codes. We present a new technique for the same task, based on so-called privacy amplification. It is shown that our method has two important advantages over the previous approaches. First, it is more efficient in terms of the number of required realizations of bit OT, and second, the technique even allows for reducing string OT to (apparently) much weaker primitives. An example of such a primitive is universal OT, where the receiver can adaptively choose what type of information he wants to obtain about the two bits sent by the sender subject to the only constraint that some, possibly very small, uncertainty must remain about the pair of bits.     

Player Simulation and General Adversary Structures in Perfect Multiparty Computation

The goal of secure multiparty computation is to transform a given protocol involving a trusted party into a protocol without need for the trusted party, by simulating the party among the players. Indeed, by the same means, one can simulate an arbitrary player in any given protocol. We formally define what it means to simulate a player by a multiparty protocol among a set of (new) players, and we derive the resilience of the new protocol as a function of the resiliences of the original protocol and the protocol used for the simulation. In contrast to all previous protocols that specify the tolerable adversaries by the number of corruptible players (a threshold), we consider general adversaries characterized by an adversary structure, a set of subsets of the player set, where the adversary may corrupt the players of one set in the structure. Recursively applying the simulation technique to standard threshold multiparty protocols results in protocols secure against general adversaries. The classical results in unconditional multiparty computation among a set of n players state that, in the passive model, any adversary that corrupts less than n/2 players can be tolerated, and in the active model, any adversary that corrupts less than n/3 players can be tolerated. Strictly generalizing these results we prove that, in the passive model, every function (more generally, every cooperation specified by involving a trusted party) can be computed securely with respect to a given adversary structure if and only if no two sets in the adversary structure cover the full set of players, and, in the active model, if and only if no three sets cover the full set of players. The complexities of the protocols are polynomial in the number of maximal adverse player sets in the adversary structure. Received 31 December 1997 and revised 26 February 1999     

Co op erative Secrecy to Resist Authentication Error in Two-Hop Wireless Networks

The authentication error in two-hop wire-less networks is considered without knowledge of eaves-dropper channels and location. The wireless information-theoretic security has attracted considerable attention re-cently. A prerequisite for available works is the precise distinction between legitimate nodes and eavesdroppers. However it is unrealistic in the wireless environment. Error is always existing in the node authentication process. Best of our knowledge, there are no works focus on solving this problem in the information-theoretic security. This paper presents a eavesdropper model with authentication error and two eavesdropping ways. Then, the number of eaves-droppers can be tolerated is analyzed while the desired secrecy is achieved with high probability in the limit of a large number of relay nodes. Final, we draw two conclu-sions for authentication error: 1) The impersonate nodes are chosen as relay is the dominant factor of the transmit-ted message leakage, and the impersonation attack does seriously decrease the number of eavesdroppers can be tol-erated. 2) The error authentication to legitimate nodes is almost no effect on the number of eavesdroppers can be tolerated.     

一种基于FPGA技术的高速数字化仪的设计

介绍了一种基于FPGA的高速数字化仪的理论设计和实现方法,从硬件角度给出了设计思路和实现方法．整个系统核心器件包括：高速数模转换芯片,拥有14b精度,150MHz转换速率等性能;高性能FPGA;板载4片32bSDRAM,能够增加采样深度,提高存储速率,实现大数据量的实时存储．使用Verilog语言编写底层FPGA程序．测试结果表明：可以实现可控深度的预采样;ADC有效位达14b,输入10MHz的正弦信号时,通道间相干系数能达到0．9983,信号完整,能满足对高速信号的采集要求．     

一种适用于低测量噪声系统的粒子滤波算法

针对常规粒子滤波算法使用先验密度函数来采样粒子,从而使粒子分布依赖动态模型来降低估计精度 的问题,以基于观测量相似函数采样的相似采样粒子滤波为基础,提出一种改进的粒子相关性预采样相似采样粒子 滤波算法．在系统测量噪声较小的情况下,利用相似采样获得更加贴近真实后验分布的粒子来提高估计精度;而相 关性预采样则通过计算相邻时刻粒子的转移概率并淘汰概率较低的粒子来提高粒子利用效率,在保证估计精度的同 时显著降低粒子数量需求．设计了算法的重要性密度函数并推导了权值递推公式．通过蒙特卡洛仿真分析了本文提 出的算法．最后通过一个混合坐标系下的目标跟踪实例阐述了算法的应用．     

Video key frame extraction through dynamic Delaunay clustering with a structural constraint

Key frame based video summarization has emerged as an important area of research for the multimedia community. Video key frames enable an user to access any video in a friendly and meaningful way. In this paper, we propose an automated method of video key frame extraction using dynamic Delaunay graph clustering via an iterative edge pruning strategy. A structural constraint in form of a lower limit on the deviation ratio of the graph vertices further improves the video summary. We also employ an information-theoretic pre-sampling where significant valleys in the mutual information profile of the successive frames in a video are used to capture more informative frames. Various video key frame visualization techniques for efficient video browsing and navigation purposes are incorporated. A comprehensive evaluation on 100 videos from the Open Video and YouTube databases using both objective and subjective measures demonstrate the superiority of our key frame extraction method.     

An information-theoretic approach to quantitative association rule mining

Quantitative association rule (QAR) mining has been recognized an influential research problem over the last decade due to the popularity of quantitative databases and the usefulness of association rules in real life. Unlike boolean association rules (BARs), which only consider boolean attributes, QARs consist of quantitative attributes which contain much richer information than the boolean attributes. However, the combination of these quantitative attributes and their value intervals always gives rise to the generation of an explosively large number of itemsets, thereby severely degrading the mining efficiency. In this paper, we propose an information-theoretic approach to avoid unrewarding combinations of both the attributes and their value intervals being generated in the mining process. We study the mutual information between the attributes in a quantitative database and devise a normalization on the mutual information to make it applicable in the context of QAR mining. To indicate the strong informative relationships among the attributes, we construct a mutual information graph (MI graph), whose edges are attribute pairs that have normalized mutual information no less than a predefined information threshold. We find that the cliques in the MI graph represent a majority of the frequent itemsets. We also show that frequent itemsets that do not form a clique in the MI graph are those whose attributes are not informatively correlated to each other. By utilizing the cliques in the MI graph, we devise an efficient algorithm that significantly reduces the number of value intervals of the attribute sets to be joined during the mining process. Extensive experiments show that our algorithm speeds up the mining process by up to two orders of magnitude. Most importantly, we are able to obtain most of the high-confidence QARs, whereas the QARs that are not returned by MIC are shown to be less interesting.     

Development and application of an integrated ecological modelling framework to analyze the impact of wastewater discharges on the ecological water quality of rivers

Modelling is an effective tool to investigate the ecological state of water resources. In developing countries, the impact of sanitation infrastructures (e.g. wastewater treatment plants) is typically assessed considering the achievement of legal physicochemical quality standards, but ignoring the ecological water quality (EWQ) of the receiving river. In this paper, we developed a generic integrated ecological modelling framework quantifying the impact of wastewater discharges on the EWQ of the Cauca river (Colombia). The framework is flexible enough to be used in conjunction with different approaches/models and integrates a hydraulic and physicochemical water quality model with aquatic ecological models. Two types of ecological models were developed, habitat suitability models for selected macroinvertebrate groups and ecological assessment models based on a macroinvertebrate biotic index. Four pollution control scenarios were tested. It was found that the foreseen investments in sanitation infrastructure will lead to modest improvements of the EWQ, with an increase lower than six units of the ecological index BMWP-Colombia. Advanced investments, such as the collection and treatment of all wastewater produced by the cities of Cali, Yumbo and Palmira and upgrading of the treatment systems should be considered to achieve a good EWQ. The results show that the integration of ecological models in hydraulic and physicochemical water quality models (e.g. MIKE 11) has an added value for decision support in river management and water policy. The integration of models is a key aspect for the success in environmental decision making. The main limitation of this approach is the availability of physicochemical, hydraulic and biological data that are collected simultaneously. Therefore, a change in the river monitoring strategy towards collection of data which include simultaneous measurements of these variables is required.