一元二次方程的根的判别式的应用

一元二次方程的根的判别式是初中代数的重要内容之一 ,它在中学数学中有着广泛的应用 ,成为近几年全国各地中考的热点问题 .为了帮助读者更好地掌握好这部分知识内容 ,现对它在初中数学中的应用进行归纳 ,以餮读者 .应用一 :判断一元二次方程 (或二元二次方程组 )的根的情况 ;或已知根的情况 ,求方程 (或组 )中的待定系数的取值范围 .一元二次方程ａｘ2 +ｂｘ +ｃ =0 (ａ≠ 0 )的根的判别式为△ =ｂ2 - 4ａｃ,它与这个方程的根有着十分密切的关系 :( 1)△ >0 方程有两个不等的实数根 ;( 2 )△ =0 方程有两个相等的实数根 .( 3)△ <0 方程…     

多项式的根的一个性质的判定

文献[1]在讨论多项式型的函数迭代方程的局部解析解的存在性时涉及到了多项式的根的一个性质.本文给出了判定该性质是否成立的一个简洁的条件,证明了多项式λ_nzⁿ+…+λ₂z²+λ₁z+λ₀有一个根α满足inf{｜λ_nα^nm+…+λ₂a^2m+λ₁α^m+λ₀｜：m=2,3,…｝>0当且仅当如下两个条件之中至少有一个成立：(i)该多项式有一个根β满足｜β｜>1;(ii)该多项式有一个根β满足｜β｜<1,且λ₀≠0.     

单圈图的最大特征值的上界的改进

Let G（V, E） be a unicyclic graph, Cm be a cycle of length m and Cm G, and ui ∈ V（Cm）. The G - E（Cm） are m trees, denoted by Ti, i = 1, 2,..., m. For i = 1, 2,..., m, let eui be the excentricity of ui in Ti and ec = max{eui ： i = 1, 2 , m}. Let κ = ec＋1. Forj = 1,2,...,k- 1, let δij = max{dv ： dist（v, ui） = j,v ∈ Ti}, δj = max{δij ： i = 1, 2,..., m}, δ0 = max{dui ： ui ∈ V（Cm）}. Then λ1（G）≤max{max 2≤j≤k-2 （√δj-1-1＋√δj-1）,2＋√δ0-2,√δ0-2＋√δ1-1}. If G ≌ Cn, then the equality holds, where λ1 （G） is the largest eigenvalue of the adjacency matrix of G.     

图的邻域复形的同调群的不变性

本文研究了图的邻域复形同调群的不变性质。设G是一个简单连通图,x是G的一个顶点,以G/x表示G中剔去点v及其关联边而得到的图,给出了G和G/x的邻域复形的同阶同调群同构的充要条件。     

纯正的群的正则带的构造

本文研究纯正的群的正则带.在给出这类半群的若干特征后,建立了纯正的群的正则带的构造定理.作为应用,同时给出了纯正的群的右拟正规带的构造定理.     

逆周期的交换半群生成的簇的子簇

In this paper, all subvarieties of the varieties Ak （k ∈N） generated by aperiodic commutative semigroups are characterized. Based on this characterization, the structure of lattice of subvarieties of Ak is investigated.     

树的最大特征值的上界的一个注记

设T是一个树,V是T的顶点集．记dv是υ∈V的度,△是T的最大顶点度．设υ∈V且dw=1．记k=ew+1,这里ew是w的excentricity．设δj′= max{dυ:dist(υ,w)=j},j=1,2,…,k-2,我们证明和这里μ1(T)和λ1(T)分别是T的Laplacian矩阵和邻接矩阵的最大特征值．特别地,记δo′=2．     

多维的一般的BBM-Burgers方程解的逐点估计

研究R~n中一般的BBM-Burgers方程解的渐进行为.运用Green函数法和Fourier分析方法得到了在非零常状态u~*附近小扰动解的逐点估计,作为一个推论,又得到了L~p(R~n)(1≤p∞)空间解的最佳的衰减估计.     

鞅的极大函数的Lp-范数的上界

设 2 ≤ p<∞ ,(fn)是一个鞅 ,利用P(｜fn｜>λ‖T(fn)‖∞)型的概率指数界 ,其中 ,T是作用在鞅上的拟线性算子 ,本文估计了鞅的极大函数的Lp_范数的上界。本文结果改进与推广了先前由HITCZENKO [7,8,9]与作者 [1 0 ]得到的结果     

关于分次环的群环的根的注记

本文研究了分次环的群环的Jacobson根,Brown-MCcoy根和强素根及其分次根．     

离线k-服务器问题算法的改进

阐述了在k-服务器猜想的证明中改进经典的离线k-服务器问题算法的必要性,从而对经典算法进行了改进,设计了一种新算法,其复杂度由原来的O(m(nk)2)下降为O(mk2).     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

一个求解水平线性互补问题的高阶可行内点算法的多项式复杂性

最近,Zhao和Sun提出了一个求解sufficient线性互补问题的高阶不可行内点算法.不需要严格互补解条件,他们的算法获得了高阶局部收敛率,但他们的文章没有报告多项式复杂性结果.本文我们考虑他们所给算法的一个简化版本,即考虑求解单调水平线性互补问题的一个高阶可行内点算法.我们证明了算法的迭代复杂性是     

A more efficient algorithm for MPR problems in phylogeny

A discrete optimization problem of assigning linearly ordered character-states to the hypothetical ancestors of an evolutionary tree under the principle of maximum parsimony has been discussed. Under the transformation relation of linearly ordered character-states, Farris (1970) and Swofford and Maddison (1987) have dealt with the problem on completely bifurcating phylogenetic trees and presented a solution. Hanazawa et al. (1995) have mathematically formulated the problem with its generalization to any tree and called it the MPR (most-parsimonious reconstruction) problem. Then they have presented clear algorithms for the MPR problem and the related problems. We present a more efficient algorithm for one of the problems, the problem of obtaining the MPR sets. The complexity of the previous algorithm for this problem is O(n²) for the number n of nodes in a given tree, but that of the new algorithm is O(n).     

所有点对之间最快路问题

所有点对之间最快路问题就是要在所有点对(Vs，Vt)之间传送数据δs,t,并找出一条最快的路线．解决所有点对之间最快路问题的关键是产生有效解的等价集合．运用动态点对最短路的算法，本文首先设计了一个时间复杂性为O(mn^2)的产生有效解等价集合的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂性分别为O(mn^2)和O(m^2n^2)．最后本文研究了求和对最小的路问题，证明该问题可以在O(mn^2)时间内解决．     

关于最小化最大延迟的分批排序问题的一个动态规划算法的注解（英文）

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n~2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.     

Notes on the complexity of sorting in abstract machines

The complexity of sorting with pointer machines and successor-predecessor random access machines is studied. The size of the problem is defined as the length of the problem string. A linear time algorithm is achieved for sorting by pointer machines. For successor-predecessor random access machines linear time is sufficient in a special case.     

基于一类新方向的宽邻域路径跟踪内点算法

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.     

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Given a finite set V, and a hypergraph H⊆2^V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.     

次最小树及其相关问题-算法设计和复杂性分析

支撑树问题已经有很长的研究历史了,见[1].在许多工程问题中,需要产生一个网络G的所有支撑树,见[2,3,4].当G为赋权图时,每棵支撑树T有长度L（T）.在产生G的所有支撑树时,许多工程问题希望按照L（T）的非降顺序产生,见[5,6].在按照L（T）的非降顺序产生的支撑树中,有许多支撑树长度是相同的,而支撑树的数目又非常大（可以高达nn-2个）,因此算法的计算量非常大.本文希望能够按照L（T）的严格上升顺序产生所有的支撑树,从而避免大量的重复计算.