搜档网
当前位置:搜档网 › Tel Aviv University

Tel Aviv University

Progressive Point Set Surfaces

SHACHAR FLEISHMAN and DANIEL COHEN-OR

Tel Aviv University

MARC ALEXA

TU Darmstadt

and

CL′AUDIO T.SILVA

University of Utah

Progressive point set surfaces(PPSS)are a multilevel point-based surface representation.They combine the usability of mul-tilevel scalar displacement maps(e.g.,compression,?ltering,geometric modeling)with the generality of point-based surface representations(i.e.,no?xed homology group or continuity class).The multiscale nature of PPSS fosters the idea of point-based modeling.The basic building block for the construction of PPSS is a projection operator,which maps points in the proximity of the shape onto local polynomial surface approximations.The projection operator allows the computing of displacements from smoother to more detailed levels.Based on the properties of the projection operator we derive an algorithm to construct a base point set.Starting from this base point set,a re?nement rule using the projection operator constructs a PPSS from any given manifold surface.

Categories and Subject Descriptors:I.3.5[Computer Graphics]:Computational Geometry and Object Modeling—Object hier-archies,Boundary representations;G.1.2[Numerical Analysis]:Approximation—Approximation of surfaces and contours General Terms:Algorithms

Additional Key Words and Phrases:Moving least squares,point-based modeling,surface representation and reconstruction

1.INTRODUCTION

Point sets are emerging as a surface representation.The particular appeal of point sets is their gener-ality:every shape can be represented by a set of points on its boundary,where the degree of accuracy typically depends only on the number of points.Point sets do not have a?xed continuity class nor are they limited to certain homology groups as in most other surface representations.Polygonal meshes, in particular,have a piecewise linear C0geometry,resulting in an unnatural appearance.To overcome the continuity problem,research has been devoted to image space smoothing techniques(e.g.,Gouraud shading),or procedures to smooth the model’s geometry such as subdivision surfaces.

To de?ne a manifold from the set of points,the inherent spatial interrelation among the points is exploited as implicit connectivity information.A mathematical de?nition or algorithm attaches a This work was supported in part by the Israel Science Foundation founded by the Israel Academy of Sciences and Humanities, and by the Israeli Ministry of Science,and by a grant from the German Israel Foundation(GIF).

Authors’addresses:S.Fleishman and D.Cohen-Or,School of Computer Science,Tel Aviv University,Schriber Building,Room 002,Tel Aviv,69978Israel;email:shacharf@cs.tau.ac.il,dcor@post.tau.ac.il;M.Alexa,TU Darmstadt-DGM,Fraunhoferstr.5, 64283,Darmstadt,Germany;email:alexa@informatik.tu-darmstadt.de;C.T.Silva,School of Computing,University of Utah,50 S.Central Campus Drive,Salt Lake City,UT84112;email:csilva@https://www.sodocs.net/doc/0117793668.html,.

Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for pro?t or commercial advantage,the copyright notice,the title of the publication, and its date appear,and notice is given that copying is by permission of the ACM,Inc.To copy otherwise,to republish,to post on servers,or to redistribute to lists requires prior speci?c permission and/or a fee.

c 2003ACM0730-0301/03/1000-0997$5.00

ACM Transactions on Graphics,Vol.22,No.4,October2003,Pages997–1011.

998?S.Fleishman et al.

Fig.1.The progressive series of the Isis model,on the left a model with19K points progressively re?ned up to189K points in the model on the right.

topology and a geometric shape to the set of points.This is nontrivial since it is unclear what spacing of points represents connected or disconnected pieces of the surface.Moreover,most surfaces are manifold, which limits the possibilities of using functions for global interpolation or approximation.Recently, Levin[2000]gave a de?nition of a manifold surface from a set of points,which was used in Alexa et al. [2001]to render shapes.

To achieve a certain geometric?delity,many points are needed to describe a shape.The necessary uniformity of the point’s density might further increase the number of points.The relation between point density and accuracy calls for the de?nition of levels of detail and the notion of progressive-ness.That is,the point set should have a base set that represents a coarse and a smooth version of the surface,which can be re?ned by a series of point insertions in the spirit of progressive meshes[Hoppe 1996],or multiresolution adaptive parameterization of surfaces(MAPS)[Lee et al.1998;Guskov et al. 2000].

Progressive or multiscale representations are useful not only to cut down on the amount of data but also for modeling and visualization purposes(see Figure1).This is because of the connection between detail levels and spectral bands[Kobbelt et al.1998a;1998b;Zorin et al.1997].Ideally,the geometric representations of the levels are relative to each other and independent of the position and orientation of the shape.This is achieved by decomposing the geometric components into a normal and a tangential direction,and encoding each level as a displacement of a coarser level[Khodakovsky et al.2000;Guskov et al.2000].Furthermore,tangential components can be described implicitly by the re?nement rule so that a single scalar per point is suf?cient to encode the shape.Note that this also leads to an ef?cient geometry compression scheme.

ACM Transactions on Graphics,Vol.22,No.4,October2003.

Progressive Point Set Surfaces?999 This approach has been described and analyzed for mesh geometry using subdivision techniques by Guskov et al.[2000]and Lee et al.[2000].Based on the method of moving least squares(MLS) presented in Alexa et al.[2001]and Levin[2000],in this paper we de?ne a projection operator and a re?nement rule.Together,they allow us to re?ne a given base point set toward a reference point set (input model).The projection operator de?nes a local tangential coordinate frame,which allows us to specify the position of inserted points,with a scalar representing the normal component.The tangential components are de?ned by the re?nement rule.As such,the scheme is reminiscent of subdivision techniques for meshes.

Based on the properties of the re?nement process we develop a simpli?cation scheme for point sets to construct a base point set,which represents a smoother version of the original shape.The base point set is then re?ned by point insertion to add levels of detail.The surface could be re?ned adaptively creating point sets with densities varying with respect,say,to the viewing parameters or the local geometric behavior of the surface.In this paper we:

—introduce a point-based geometric modeling technique that is based on the MLS projection mechanism;—present a progressive scheme for point set surfaces,where the levels of an object represent both coarse–to–?ne and smooth–to–detailed hierarchy;

—use a local operator that allows accurate computation of local differential surface properties;—apply an encoding scheme for compressing progressive point sets.

In Section2,we proceed with a presentation of related work.We de?ne the MLS surface and how to compute it in Section3.In Section4,we describe the progressive point set surfaces in detail.Section5 describes how a progressive point set surface is encoded and discusses its ef?ciency.Results are shown in Section6.We end with a discussion on the progressive point set surface and conclude in Sections7and8.

2.RELATED WORK

Our work is related to the recent research efforts in developing point-based representations for shapes [Grossman and Dally1998;Pauly and Gross2001;P?ster et al.2000;Rusinkiewicz and Levoy2000]. Most of the mentioned techniques are targeted at fast processing and rendering of large point-sampled geometry.Our techniques are focused on advancing the“modeling”of primitives with points.In this respect our work?ts into the?eld of digital geometry processing(DGP)[Desbrun et al.1999;Guskov et al.1999,2000;Lee et al.1998;Taubin et al.1995],which aims at extending standard signal processing concepts to the manifold surface domain.Pauly and Gross[2001]have shown how to extend these techniques to point-based representations by collecting sets of points to patches,over which the points de?ne an irregularly sampled function.Most approaches for meshes also construct a multiresolution representation by progressively re?ning a base domain and exploiting the connection of the re?nement levels to spectral properties.Meshes are generally composed of two parts:the connectivity of the mesh; and the geometry(i.e.,the position of the vertices).Few DGP techniques can be directly applied to such a representation(one example is the pioneering work presented in Taubin[1995]).DGP algorithms require parameterization of the surface,which could be represented in mesh form as a subdivision surface[Lee et al.1998;Kobbelt et al.1999;Eck et al.1995].

A recent work related to our surface representation is Carr et al.[2001],which reconstructed three-dimensional(3D)objects by?tting a global radial basis function(RBF)to point clouds.An RBF forms a solid model of an object,allowing analytic evaluation of surface normal,direct rendering and iso-surface extraction,similar to the properties of the surface representation we use.

Several different hierarchical representations have been proposed for geometric objects.Object sim-pli?cation[Cignoni et al.1994;Cohen et al.1996;He et al.1996;Hoppe et al.1993;Zhou et al.1997]

ACM Transactions on Graphics,Vol.22,No.4,October2003.

1000?S.Fleishman et al.

is often used to generate a hierarchical representation,which could be used for many purposes,for example,for rendering [Duchaineau et al.1997;El-Sana and Varshney 1999;Xia et al.1997].

Linsen [2001]also described a multiresolution representation of point-based objects.Similarly to our method,the detail points are inserted using a prediction operator.In our work we focus on a space-ef ?cient progressive representation of a point set.Another recent,related work is Pauly et al.

[2002],which described a number of point-based simpli ?cation methods.The method we present here for building the base point set is similar to their clustering method.

A leading technique for representing hierarchical meshes is progressive meshes [Hoppe 1996],a mesh representation of varying resolution where a series of edge-split operations progressively re ?nes a base mesh up to the original resolution of the source.This representation motivates solutions to mesh simpli ?cation,progressive transmission,and loading from a disk or from a remote server.A number of mesh compression and streaming techniques are based on this concept [Cohen-Or et al.1999;Pajarola and Rossignac 2000;Taubin et al.1998].For a recent survey of mesh simpli ?cation and compression techniques see Gotsman et al.[2001].

Subdivision surfaces [Catmull and Clark 1978;Warren and Weimer 2001]are de ?ned by a topological re ?nement operator and a smoothing rule.Given a mesh of arbitrary topology ,they re ?ne the mesh toward a smooth limit surface.Point set surfaces are similar to subdivision surfaces,in that it is possible to add points to the de ?ned smooth surface without additional information.However,to describe an arbitrary surface using subdivision techniques,inserted points need to be displaced.Normal meshes

[Guskov et al.2000]as well as displaced subdivision surfaces [Lee et al.2000]demonstrate this idea of a multiresolution subdivision mesh where vertices are displaced by a single scalar value in the normal direction.These approaches are attractive since a single scalar value is easier to manipulate or store.The underlying concept can be understood as decomposing the surface representation into a tangential and a normal component (see Guskov et al.[2000]).Note that we use the same idea,however without coding the tangential component explicitly as the mesh connectivity but implicitly as point proximity .

3.MLS SURFACES

The MLS surface S P of a set of points P ={p i },p i ∈R 3,i ∈{1,...,N }is de ?ned implicitly by a projection operator.To project a point r onto S P two steps are necessary:?rst,a local reference domain H = n ,d ,where d is the origin of the plane and n is the normal to the plane,is computed.Then,a local bivariate polynomial is ?tted over H to the point set.More precisely ,the local reference domain H ={x | n ,x ?d =0,x ∈R 3},n ∈R 3, n =1is determined by minimizing

N

i =1( n ,p i ?r ?t n )2e ? p i ?r ?t n 2/h 2(1)

in all normal directions n and offsets t .Here d =r +t n .A local coordinate system over H is de ?ned by taking the standard basis for R 3,e 1,e 2,e 3and computing a rotation matrix M such that n =M ·e 3.The local coordinate system is de ?ned by (M ·e 1,M ·e 2).This rotation matrix is not uniquely de ?ned.For our purposes,any solution will do as long as we use the same procedure to compute M in all of our computations.

Let q be the projection of p i onto H ,and f i the height of p i over H ,that is,f i =n ·(p i ?q ).The polynomial approximation g is computed by minimizing the weighted least-squares error

N

i =1

(g (x i ,y i )?f i )2e ? p i ?r ?t n 2/h 2.(2)

ACM Transactions on Graphics,Vol.22,No.4,October 2003.

Progressive Point Set Surfaces ?1001

The projection of r is given by

MLS (r )=r +(t +g (0,0))n .(3)

Formally ,the surface S P is the set of points ( ? )that project onto themselves.In this de ?nition,h is the anticipated spacing of the points.Thus,the point set together with an adequately chosen value for h de ?nes the surface.As part of the projection procedure,we not only determine the position on the surface where a point projects to,but we also obtain high-order derivative information analytically ,which can be used to accurately determine normal,curvature,etc.A detailed description of computing the reference domain and polynomial is presented in Alexa et al.[2003]In the following,S X will generally be the surface with respect to a point set X de ?ned by the above procedure.We will call this the MLS-surface of X .

4.PROGRESSIVE POINT SET SURFACES

First,we give an overview of the concept of progressive point set surfaces (PPSS)and then explain the details in the following sections.

Given a reference (input)point set R ={r i }de ?ning a reference surface S R .The point set R is reduced by removing points to form a base point set P 0?R .This base point set de ?nes a surface S P 0which differs from S R .Next,we will resample the surface adding more points so that the difference between our surface and S R decreases.

The base point set P 0is re ?ned by inserting additional points yielding the set P 1.The re ?nement operator ?rst inserts points independent of the reference set R ,which means P 1?R .Then,the inserted points are displaced so that the difference between the surfaces decreases,that is,d (S P 1,S R )

This process is repeated to generate a sequence of point sets P i with increasing size and decreasing difference from the reference surface.A progressive point set surfaces is de ?ned as the MLS surface of P =P 0,P 1,...,where each point set P i is encoded by the (scalar)displacements of inserted points,yielding a compact representation of the progressive point set surface.

In the following we explain the necessary steps for this procedure in detail.We denote the reference domain plane of a point p with respect to a point set S as H S (p )and the polynomial similarly by g S (p ).

4.1The Re ?nement Operator

Let R be the reference point set as before and P be the point set to re ?ne.The set P is re ?ned by generating additional points A ={a j },which are sampled in the local neighborhoods of the p i .More speci ?cally ,let the local reference domain H p (p i )of a point p i (see Figure 2a)be determined as the local minimum of Equation (1)with respect to the points in P .The reference plane H p (p i )is sampled regularly at intervals ρ,yielding a set of (u ,v )coordinates for the points a j on the plane.These points are placed in the neighborhood of the surface using the polynomial ˉg =g p (p i )(de ?ned by Equation (2)),yielding the set of points a j =(u ,v ,ˉg (u ,v )).To ?nd and encode the positions of the additional points,the plane H p (a j )of a j is computed,and then two local polynomial ?ts are computed on the basis of the given reference domain H p (a j ):the ?rst polynomial g p is with respect to the points in P and the second,g r ,is with respect to the points in R .The height of a point a j is given as g r (0,0),that is,on the local polynomial ?t to the points in the reference set (see Figure 2b).

Since the coordinate (u ,v )is generated implicitly by specifying the regular sampling parameter ρ,only the height has to be encoded.Based on Equation (3),the height of a j can be expressed as the difference:

=g r (0,0)?g p (0,0).(4)

ACM Transactions on Graphics,Vol.22,No.4,October 2003.

1002?S.Fleishman et al.

Fig.2.An illustration of the point set re?nement process:(a)a new point a is generated in the neighborhood of the surface of the current level(the blue points).The reference plane H p(p i)and polynomialˉg=g p(p i)of p i are computed.By scanning the neighborhood of p i,a new point a on H p(p i)is generated and projected on the polynomialˉg,that is,a=ˉg(a ).In(b),a is projected on MLS p(the blue curve)by computing its reference plane H p(a)and polynomial g p(a).Next,a is projected again on S R(de?ned by the black points)using the same reference plane,but with the appropriate polynomial g r(a).Finally,the detail value =a r?a p is computed.

Since the distance between g r and g p is signi?cantly smaller than the distance between g r and the reference plane,the can be ef?ciently encoded.

The regular sampling pattern has to be adapted to avoid oversampling and sampling of empty regions. We introduce two criteria for deciding whether to insert a point.A point a i is inserted only if

(1)none of the already inserted points P∪{a j,j

(2)it is in the convex hull of points in P closer than h or,more formally,if and only if a i∈CH{p i| p i?

a i

The?rst criterion avoids oversampling,and the second aims at detecting boundaries of the manifold by de?ning the extent of the local neighborhood.

The sampling parameterρcan be used to specify the re?nement convergence.Ifρis halved in ev-ery re?nement step the number of points approximately quadruples from one point set to the next. ACM Transactions on Graphics,Vol.22,No.4,October2003.

Progressive Point Set Surfaces?1003

Fig.3.Close-ups of smooth renderings for different levels in the hierarchy of a PPSS.The base level of a PPSS de?nes a smooth surface,which is visualized here by upsampling the smooth surface by adding points without displacing them.Note that higher levels add the missing details to the PPSS representation.

However,ρcan also be used to adapt the sampling density to the application needs,for example,visible regions of the surface or local curvature if piecewise linear approximations are needed.

As the point density increases from one re?nement level to the next,also h should be adapted.We adapt h to the change inρ;for example,ifρis halved in every step,so is h.We assume,however,that

a suitable h is given for the base point set.This is discussed in the following section.

4.2Constructing the Base Point Set

The re?nement operator uses local reference domains on the basis of the reduced point set to compute polynomial?ts to the reference point set.This requires the local reference domain of a point p i with respect to the points in P and to the points in R to be about the same.We use this requirement as a criterion for reducing the reference point set to the base point set.

Given a neighborhood size h and a maximum deviation ,let Q i be the point set which results from removing the points in a h-neighborhood around r i,that is,

Q i={r k| r k?r i >h}.(5) A point r i can be used in the base point set if its original reference domain H R(r i)is close to the reference

domain H Q

i (r i)with respect to the reduced point set Q i.More speci?cally,the distance between H R(r i)

and H Q

i (r i)is measured as the scalar product between their normal components(see Section3).

In practice,the points in R are visited in random order.If r i can be included in P0,all points in the h-neighborhood around r i are discarded for inclusion in P0.The process terminates after all points are tested.

5.THE PPSS ENCODING

Figure4illustrates the magnitudes of the displacements of the progressive set.Observing that the vast majority of the displacements are of small magnitude gives rise to a space ef?cient encoding scheme. To create an encoding of P i+1given P i,we perform the routine described in Section4.1.New points

are generated and projected both on S P

i and on S R.The difference between the two projections is the

displacement denoted by .Since the distance between the two surfaces is small,the displacements are merely the details of the surface and can be encoded in a small number of bits.

To decode P i+1,a reverse procedure is applied.New points are generated as described in the encoding procedure.For each point r,the reference plane and polynomial are computed using Equations(1)

ACM Transactions on Graphics,Vol.22,No.4,October2003.

1004?S.Fleishman et al.

Fig.4.A color-coding of the magnitude of the displacement for the Venus model.Note that smooth regions have small dis-placements,while regions containing?ne detail need larger displacements The magnitude of the displacements essentially corresponds to the energy in the respective frequency band.

and(2).Then the point is projected using a modi?ed Equation(3)as follows:

MLS(r)=r+(t+g(0,0)+ )n.(6) For ef?cient storage,we quantize the displacement values to a user-speci?ed accuracy.An error bound de?nes the maximal tolerated error with respect to the diagonal of the object’s bounding box.The range of the displacements and the error bound de?nes the number of bits required to properly represent the displacements.Recall that the decoding procedure is highly dependent on performing the exact same procedure that the encoder performed.Quantizing the values and reconstructing them creates minor differences that may lead to somewhat different sets of points that are added to each level.If this occurs the encoder and decoder may no longer be synchronized.Therefore,in the encoding process the displacements are quantized to guarantee that the decoder generates the exact set of points that is encoded.

6.RESULTS

We have implemented the progressive point set representation as described in the previous sections and applied it to several models.Table I summarizes the results by showing the average number of bits per displacement required with respect to error tolerance.The error is expressed with respect to the diagonal of the bounding box of the given model.Note that the error is merely subject to the quantization applied to the displacements.For the models in Table I,?ve(for the dino model)to seven(for the dragon model)levels were generated.Our experiments as shown in Table II and Figures5and7suggest that an average of?ve bits/point yields a pleasing visual quality.The base point set P0is compressed by triangulating the points using the ball-pivoting algorithm(BPA)[Bernardini et al.1999]and applying a mesh compression tool[Gotsman et al.2001].The time to compress the models in Table I range from several minutes to120minutes on Pentium TM III1Ghz;our code was not optimized and computes the MLS reference plane using nonlinear optimization.

Table II shows the compression achieved by varying the number of bits for the displacement values. We measured the accuracy of the reconstructed model in the spirit of Metro[Ciampalini et al.1997], ACM Transactions on Graphics,Vol.22,No.4,October2003.

Progressive Point Set Surfaces?1005 Table I.Achieved Bit-Rates for Given Error Bounds(The user can specify an error

bound on the displacement values.Depending on the error bound,a quantization

scheme is chosen,which in?uences the number of bits necessary to encode the

displacements.The small number of quantization levels typically results in a

systematically smaller error as compared to the error bound(shown in parentheses))

bits/displacement

Points(error10?4)

Name Points in P00.0010.010.10.5

Dragon437K16K9.7 6.6 3.4 2.4

(0.026)(0.044)(0.29)(1.6)

Isis187K9K9.9 6.9 4.7 1.8

(0.01)(0.04)(0.31)(1.9)

Venus134K7K9.28.3 5.5 3.0

(0.08)(0.13)(0.27)(1.2)

Dino56K4K10.98.1 4.9 2.9

(0.25)(0.24)(0.35)(0.97)

Table II.A Comparison of the Size Versus Accuracy for the Dragon Model

(Each line shows the size of the model as a function of the number of bits

used for quantization of the displacement values.The base point set

contains16772points compressed to37.4bits/point(b/p).)

Inserted Bits/Total Total Average error

points points size b/p(10?4)

476370 2.3493142139K 3.66 2.7

472330 2.4489102144K 3.77 1.6

440907 3.5457679192K 4.920.29

439652 6.6456424364K8.060.044

4398409.7456612534K11.10.026

Fig.5.Rate distortion curve:shows a comparison of size vs.accuracy achievable with our compression method.The error is measured on a scale of10?4of the bounding box of the model.

that is,by sampling distances in normal direction.To measure the distance between an MLS surface S1de?ned by a set of points P1and the reference MLS surface S de?ned by P,we sample arbitrary points in the neighborhood of S1,and use the MLS projection procedure to project each point on S1and on S.The average difference between the two projections is the error.

We compared the PPSS–based compression technique with techniques for multiresolution mesh com-pression.In particular,we have used Khodakovsky’s mesh compression technique[Khodakovsky et al. 2000]to generate meshes with increasing accuracy with respect to a reference mesh.The vertices of

ACM Transactions on Graphics,Vol.22,No.4,October2003.

1006?S.Fleishman et al.

https://www.sodocs.net/doc/0117793668.html,parison of meshes using Metro.The top row displays several steps during the re?nement process of Khodakovsky’s algorithm.The numbers below the?gures show their size and mean error with respect to the bounding box of the object,as reported by the I.E.I-CNR Metro tool.The bottom row displays three meshes reconstructed from a PPSS and compared to the input mesh.Note that the PPSS does not?t the reference mesh but rather the smooth MLS-surface over the vertices.The point sets are triangulated using BPA to be able to apply Metro.Color ranges from blue to green with respect to the error.Note that the Metro tool normalizes the color map to the maximal error of the model being colored.

the reference mesh were used to build a PPSS.Since we do not have connectivity information the BPA was used to generate meshes from the point sets.The resulting meshes have been compared to the reference using Metro.Figure6shows a visualization of the results.Note that the PPSS does not?t the piecewise linear geometry of the reference mesh(as the mesh compression technique)but the MLS surface de?ned by the vertices.This adds some bias to the resulting error for the PPSS.

Figure7shows a series of progressively re?ned point sets,where the shaded images are rendered by an upsampling procedure[Alexa et al.2001],which requires no displacements.The rendering performs a local re?nement of the surface around each point of the model.The images in the second column of Figure8are rendered with the above upsampling method and the images in the third column are rendered using the OpenGL TM glPointSize function.Since the MLS surface is continuous and smooth, the quality of the upsampled renderings is higher than a splat rendering.

The MLS surface is smooth and as such does not reconstruct sharp features(since it is not able to model discontinuities in its derivatives).While reconstructing point samples of Computer-aided design ACM Transactions on Graphics,Vol.22,No.4,October2003.

Progressive Point Set Surfaces?1007

Fig.7.A progressive series of the Venus and Dragon models.

Fig.8.Two intermediate representations of the Venus model in the hierarchy.On the left we show the set of points.In the middle, the set of points are rendered by splatting using OpenGL TM.The images on the right are rendered using an MLS upsampling procedure,requiring no additional data.

(CAD)models with sharp features(see Figure9),those sharp features are smoothed out,while the rest of the object is reconstructed faithfully.Our method deals with boundaries by computing the convex hull of the neighborhood of a point(as previously described in Section4.1).For sharp edges in boundaries like the rectangular hole in Figure9c and d,our method converges to round corners with radius of the size of the input feature size,that is,the spacing between points.

ACM Transactions on Graphics,Vol.22,No.4,October2003.

1008?S.Fleishman et al.

Fig.9.Reconstruction of sharp edges and boundaries.On the left((a)and(c)),we show the input models.(b)and(d)are the reconstructions of the models using our algorithm.

7.DISCUSSION

As in other multilevel shape representations,the levels essentially correspond to different bands in the spectrum of the shape.The Gaussian weight function leads to a Gaussian?ltering of the shape (compare Equations(1)and(2)).The spatial radius h of the?lter is inversely related to the Gaussian in the frequency domain.Thus,the base point set represents the shape with the most relative en-ergy in the low frequency bands,while the re?nement levels add higher frequency bands(see the shape hierarchy in Figure1,and the details in Figure3).The projection operator allows us to com-pute the scalar displacement necessary to lift a point from one level to the next.The displacements are with respect to local frames(as in[Kobbelt et al.2000]).The magnitude of this displacement is, thus,a measure of the energy in the respective frequency band.This is illustrated with color codes in Figure4.

The MLS surface de?nition is based on differential geometry,namely,that the surface can be locally approximated by a function.If this assumption is not met,we fail to de?ne the plane(Equation1)and cannot reconstruct the surface.This ill condition happens when the surface is not sampled densely enough in areas of high curvature or in areas with low signal-to-noise ration(SNR),that is,when the ACM Transactions on Graphics,Vol.22,No.4,October2003.

Progressive Point Set Surfaces?1009 noise is larger than the expected feature size.These conditions can be identi?ed,see Alexa et al.[2003] for more details.

Because point-sampled objects contain no explicit topological information,it is necessary to make assumptions about the underlying sampling density in order to properly reconstruct this connectivity information.In general,this is a tough problem,and substantial practical and theoretical work has been performed in the area[Amenta and Bern1999].Provably good techniques,for example,Amenta et al.[1998],have been shown to be effective,but quite slow for actual use,mostly due to the need to compute3D Delaunay triangulation of the complete point sets.For modeling point sets,simpler (and computationally cheaper)techniques have been used.Zwicker et al.[2002]and Pauly et al.[2002] used k-nearest neighbor queries to reconstruct a neighborhood.This works well for objects with fairly isotropic and uniform sampling density;furthermore the k-nearest neighbor query may unintuitively ?ll“real”holes in the model.Linsen[2001]used the angle criterion for choosing the neighbors of a points,assuming the object is of genus zero,or otherwise de?ned some threshold on the point spacing. The approach we currently use for de?ning the neighborhood of a point is to query for nearest neighbors in a user-de?ned radius,assuming that the distribution of points is fairly uniform.This assumption is reasonable for scanned objects.As shown in Alexa et al.[2003],this method can deal with some variation in the input point density,but will fail if the density varies signi?cantly.

Recently,Kalaiah and Varshney[2001]introduced an effective method for rendering point primitives that requires the computation of the principal curvatures and a local coordinate frame for each point. This approach is natural for the MLS surface representation since it requires a local coordinate frame and the principal curvature for each.During the MLS projection procedure a local coordinate frame is computed,and the principal curvatures can be estimated analytically from Equation(2).

8.CONCLUSIONS

Our technique has several unique features.First of all,it works directly on points,avoiding the need to triangulate the source point set,and the costly remeshing of the surface into subdivision connectivity. This is especially important for large and detailed datasets.Another important property of our tech-nique is its locality.This leads to a numerically stable computation,linear time and space complexity, and small memory footprint,which may lead to the development of out-of-core algorithms.Further-more,progressive point set representations lead to a compression scheme,where the range of the error decreases with each level in the hierarchy.As shown above,at each level it is possible to upsample the surface from the sparse representation.

The lack of connectivity in the representation could also be the source of shortcomings.As shown in Amenta et al.[1998],there are limits on surface samplings which can be proven to de?ne a given surface.That is,our approach might need a relatively dense base set to resolve possible ambiguities in the modeling of certain complex surfaces.Moreover,it is considerably easier to handle discontinuities by triangulated models.

A considerable amount of research has been devoted to developing and optimizing the“mesh-base world.”Many advanced methods require a local parameterization and local differential properties.The MLS projection procedure inherently has these qualities;for example,texture synthesis techniques may be applied on surfaces using surface marching similar to[Turk1992,2001].We believe that the importance of point set representation and of MLS surfaces in particular is likely to play an increasing role in3D geometric modeling.

ACKNOWLEDGMENTS

Part of this work was done while Shachar Fleishman and Cl′audio Silva were at AT&T Labs-Research. The datasets appear courtesy of Cyberware and the Stanford3D scanning repository.

ACM Transactions on Graphics,Vol.22,No.4,October2003.

1010?S.Fleishman et al.

This paper would not be possible without the many people who made their software available:Fausto Bernardini for his implementation of the ball-pivoting algorithm;Igor Guskov,Andrei Khodakovsky, Peter Schroeder,and Wim Sweldens for their remeshing and compression code;Craig Gotsman and Virtue Ltd for“Optimizer”;and The Visual Computing Group of CNR-Pisa for Metro.We would like to thank Wagner Correa for help throughout this project.

REFERENCES

A LEXA,M.,

B EHR,J.,

C OHEN-O R,D.,F LEISHMAN,S.,L EVIN,D.,AN

D S IL VA,C.T.2001.Point set surfaces.In Proceedings of IEE

E Visualization2001.21–28.

A LEXA,M.,

B EHR,J.,

C OHEN-O R,D.,F LEISHMAN,S.,L EVIN,D.,AN

D S IL VA,https://www.sodocs.net/doc/0117793668.html,puting and rendering point set surfaces. IEE

E https://www.sodocs.net/doc/0117793668.html,pt.Graph.Vis.9,1(Jan.),3–15.

A MENTA,N.AND

B ERN,M.1999.Surface reconstruction by Voronoi?ltering.Discrete Comput.Geom.22,4,481–504.

A MENTA,N.,

B ERN,M.,AND K AMVYSSELIS,M.1998.A new voronoi-based surface reconstruction algorithm.In Proceedings of SIGGRAPH98(Orlando,FL.).415–422.

B ERNARDINI,F.,M ITTLEMAN,J.,R USHMEIER,H.,S IL VA,C.,AND T AUBIN,G.1999.The ball-pivoting algorithm for surface reconstruc-tion.IEEE https://www.sodocs.net/doc/0117793668.html,pt.Graph.5,4(Oct.-Dec.),349–359.

C ARR,J.C.,B EATSON,R.K.,C HERRIE,J.B.,M ITCHELL,T.J.,F RIGHT,W.R.,M C C ALLUM,B.C.,AN

D

E VANS,T.R.2001.Reconstruction and representation of3d objects with radial basis functions.In Proceedings of SIGGRAPH2001.67–76.

C ATMULL,E.AN

D C LARK,J.1978.Recursively generated B-spline surfaces on arbitrary topological https://www.sodocs.net/doc/0117793668.html,put.-Aided Des.10,350–355.

C IAMPALINI,A.,C IGNONI,P.,M ONTANI,C.,AN

D S COPIGNO,R.1997.Multiresolution decimation based on global https://www.sodocs.net/doc/0117793668.html,-put.13,5,228–246.

C IGNONI,P.,F LORIANI,L.D.,M ONTONI,C.,P UPPO,E.,AN

D S COPIGNO,R.1994.Multiresolution modeling and visualization of volume data based on simplicial complexes.In Proceedings of the1994Symposium on Volume Visualization.19–26.

C OHEN,J.,V ARSHNEY,A.,M ANOCHA,D.,T URK,G.,W EBER,H.,A GARWAL,P.,F REDERICK,P.,B ROOKS,J.,AN

D W RIGHT,W.1996.Simpli-?cation envelopes.In Proceedings of SIGGRAPH96(New Orleans,LA).119–128.

C OHEN-O R,D.,L EVIN,D.,AN

D R EMEZ,O.1999.Progressive compression of arbitrary triangular meshes.In Proceedings of IEE

E Visualization’99(San Francisco,CA).67–72.

D ESBRUN,M.,M EYER,M.,S CHR¨ODER,P.,AND B ARR,A.H.1999.Implicit fairing of irregular meshes using diffusion and curvature ?ow.In Proceedings of SIGGRAPH99(Los Angeles,CA).317–324.

D UCHAINEAU,M.A.,W OLINSKY,M.,S IGETI,D.E.,M ILLER,M.C.,A LDRICH,C.,AND M INEEV-W EINSTEIN,M.B.1997.Roaming terrain: Real-time optimally adapting meshes.In Proceedings of IEE

E Visualization’97.81–88.

E CK,M.,D E R OSE,T.D.,D UCHAMP,T.,H OPPE,H.,L OUNSBERY,M.,AND S TUETZLE,W.1995.Multiresolution analysis of arbitrary meshes.In Proceedings of SIGGRAPH95(Los Angeles,CA).173–182.

E L-S ANA,J.AND V ARSHNEY,A.1999.Generalized view-dependent simpli?https://www.sodocs.net/doc/0117793668.html,put.Graph.Forum18,3(Sept.),83–94.

G OTSMAN,C.,G UMHOLD,S.,AND K OBBELT,L.2001.Simpli?cation and compression of3d meshes.In European Summer School on Principles of Multiresolution in Geometric Modelling(PRIMUS),Munich.Published as Tutorials on Multiresolution in Geometric Modelling,A.Iske,E.Quak,and M.S.Floater,Eds.Springer-Verlag,Berlin,Germany.

G ROSSMAN,J.P.AND D ALLY,W.J.1998.Point sample rendering.In Proceedings of the Eurographics Rendering Workshop1998 (Vienna,Austria).181–192.

G USKOV,I.,S WELDENS,W.,AND S CHR¨ODER,P.1999.Multiresolution signal processing for meshes.In Proceedings of SIGGRAPH 99(Los Angeles,CA).325–334.

G USKOV,I.,V IDIMCE,K.,S WELDENS,W.,AND S CHR¨ODER,P.2000.Normal meshes.In Proceedings of SIGGRAPH2000.95–102.

H E,T.,H ONG,L.,V ARSHNEY,A.,AND W ANG,S.W.1996.Controlled topology simpli?cation.IEEE https://www.sodocs.net/doc/0117793668.html,pt.Graph.2,2 (June),171–184.

H OPPE,H.1996.Progressive meshes.In Proceedings of SIGGRAPH96(New Orleans,LA).99–108.

H OPPE,H.,D E R OSE,T.,D UCHAMP,T.,M C D ONALD,J.,AND S TUETZLE,W.1993.Mesh optimization.In Proceedings of SIGGRAPH 93(Anaheim,CA).19–26.

K ALAIAH,A.AND V ARSHNEY,A.2001.Differential point rendering.In Rendering Techniques,S.J.Gortler and K.Myszkowski, Eds.Springer-Verlag,Berlin,Germany.

K HODAKOVSKY,A.,S CHR¨ODER,P.,AND S WELDENS,W.2000.Progressive geometry compression.In Proceedings of SIGGRAPH 2000.271–278.

ACM Transactions on Graphics,Vol.22,No.4,October2003.

Progressive Point Set Surfaces?1011 K OBBELT,L.,C AMPAGNA,S.,AND S EIDEL,H.-P.1998a.A general framework for mesh decimation.In Proceedings of Graphics

Interface’98.43–50.

K OBBELT,L.,C AMPAGNA,S.,V ORSATZ,J.,AND S EIDEL,H.-P.1998b.Interactive multi-resolution modeling on arbitrary meshes.In Proceedings of SIGGRAPH98(Orlando,FL).105–114.

K OBBELT,L.P.,B AREUTHER,T.,AND S EIDEL,H.-P.2000.Multiresolution shape deformations for meshes with dynamic vertex https://www.sodocs.net/doc/0117793668.html,put.Graph.Forum19,3(Aug.),249–260.

K OBBELT,L.P.,V ORSATZ,J.,L ABSIK,U.,AND S EIDEL,H.-P.1999.A shrink wrapping approach to remeshing polygonal surfaces. Comput.Graph.Forum18,3(Sept.),119–130.

L EE,A.,M ORETON,H.,AND H OPPE,H.2000.Displaced subdivision surfaces.In Proceedings of SIGGRAPH2000.85–94.

L EE,A.,S WELDENS,W.,S CHR¨ODER,P.,C OWSAR,L.,AND D OBKIN,D.1998.Maps:Multiresolution adaptive parameterization of surfaces.In Proceedings of SIGGRAPH98(Orlando,FA).95–104.

L EVIN,D.2000.Mesh-independent surface interpolation.Technical report.Tel-Aviv University,Tel-Aviv,Israel.Available online at http://www.math.tau.ac.il/~levin.

L INSEN,L.2001.Point cloud representation.Tech.Rep.3.Fakultaet fuer Informatik,Universitaet Karlsruhe,Karlsruhe, Germany.

P AJAROLA,R.AND R OSSIGNAC,https://www.sodocs.net/doc/0117793668.html,pressed progressive meshes.IEEE https://www.sodocs.net/doc/0117793668.html,put.Graph.6,1(Jan.–March), 79–93.

P AULY,M.AND G ROSS,M.2001.Spectral processing of point-sampled geometry.In Proceedings of SIGGRAPH2001.379–386. P AULY,M.,G ROSS,M.,AND K OBBELT,L.P.2002.Ef?cient simpli?cation of point-sampled surfaces.In Proceedings of the13th IEEE Visualization Conference.163–170.

P FISTER,H.,Z WICKER,M.,VAN B AAR,J.,AND G ROSS,M.2000.Surfels:Surface elements as rendering primitives.In Proceedings of SIGGRAPH2000.335–342.

R USINKIEWICZ,S.AND L EVOY,M.2000.Qsplat:A multiresolution point rendering system for large meshes.In Proceedings of SIGGRAPH2000.343–352.

T AUBIN,G.1995.A signal processing approach to fair surface design.In Proceedings of SIGGRAPH95(Los Angeles,CA). 351–358.

T AUBIN,G.,G UEZIEC,A.,H ORN,W.,AND L AZARUS,F.1998.Progressive forest split compression.In Proceedings of SIGGRAPH 98(Orlando,FL).123–132.

T URK,G.1992.Re-tiling polygonal https://www.sodocs.net/doc/0117793668.html,put.Graph.26,55–64.(Proceedings of SIGGRAPH’99(Chicago,IL)).

T URK,G.2001.Texture synthesis on surfaces.In Proceedings of SIGGRAPH2001.347–354.

W ARREN,J.AND W EIMER,H.2001.Subdivision Methods for Geometric Design:A Constructive Approach.Morgan Kaufmann, (San Francisco,CA).

X IA,J.C.,E L-S ANA,J.,AND V ARSHNEY,A.1997.Adaptive real-time level-of-detail-based rendering for polygonal models.IEEE https://www.sodocs.net/doc/0117793668.html,pt.Graph.3,2(April-June),171–183.

Z HOU,Y.,C HEN,B.,AND K AUFMAN,A.E.1997.Multiresolution tetrahedral framework for visualizing regular volume data.In Proceedings of IEEE Visualization’97.135–142.

Z ORIN,D.,S CHR¨ODER,P.,AND S WELDENS,W.1997.Interactive multiresolution mesh editing.In Proceedings of SIGGRAPH97 (Los Angeles,CA).259–268.

Z WICKER,M.,P AULY,M.,K NOLL,O.,AND G ROSS,M.2002.Pointshop3d:An interactive system for point-based surface editing. ACM Trans.Graph.21,3(July),322–329(Proceedings of ACM SIGGRAPH2002).

Received June2002;revised October2002;accepted December2002

ACM Transactions on Graphics,Vol.22,No.4,October2003.

南开大学计算机与控制工程学院806运筹学历年考研真题汇编(含部分答案)52p

南开大学计算机与控制工程学院 806运筹学历年考研真题汇编(含部分答案) 最新资料,WORD格式,可编辑修改! 目录 第一部分南开大学806运筹学历年考研真题.......................................................................................................................... 2011年南开大学信息技术科学学院813运筹学考研真题 ......................................................................................................... 2011年南开大学信息技术科学学院813运筹学考研真题及详解 ............................................................................................. 2005年南开大学信息技术科学学院运筹学考研真题................................................................................................................. 2004年南开大学信息技术科学学院运筹学考研真题................................................................................................................. 第二部分南开大学其他学院运筹学历年考研真题.................................................................................................................. 2012年南开大学商学院915运筹学考研真题............................................................................................................................. 2011年南开大学商学院915运筹学考研真题............................................................................................................................. 2011年南开大学商学院915运筹学考研真题及详解................................................................................................................. 2010年南开大学商学院887运筹学考研真题............................................................................................................................. 说明: (1)2013年7月,南开大学对信息技术科学学院学科进行优化整合,分别组建计算机与控制工程学院 和电子信息与光学工程学院。 (2)2004年和2015年南开大学信息技术科学学院的“运筹学”科目代码不详。

计算机文化基础答案

1. 简述计算机的几种主要类型,它们的主要应用领域是什么 2. 计算机内部的信息为什么要采用二进制编码表示 3. 一台服务器的网络地址是它是由四个十进制数表示的,在计算机内部 以二进制形式存储在 4个字节中。请写出该地址对应的 4个二进制数。 4. 简述冯·诺依曼型计算机的组成与工作原理。 5. 什么是计算机的指令系统机器指令通常有哪些类型 6. 简述操作系统的形成过程。操作系统的功能是什么 7. 进程的概念是什么举例说明在使用计算机过程中涉及到进程的一些操作 8. 在 Windows中,启动一个程序有哪几种途径 9. “文件”的概念是什么如何定义文件名和扩展名 10. 注册表的功能是什么 11. 利用 Delete键是否能够安全卸载某个应用程序为什么 12. 在 Windows中,应用程序之间的数据交换有哪些形式,它们各自的特点是什么 13. 什么是计算机网络,举例说明计算机网络有哪些应用 14. 简述计算机网络的基本组成(软硬件)。 15. 什么是计算机网络的拓扑结构常见的拓扑结构有哪几种 16. 什么是计算机网络协议说出 OSI七层协议的名称。 17. 什么是 Internet,举例说明 Internet上有哪些应用 18. Internet采用的标准网络协议是什么 19.在网络应用中采用客户机/服务器模式有什么好处 20. 在 Internet中,IP地址和域名的作用是什么它们之间有什么异同 21.什么是 HTML 什么是主页 22. 目前 Internet上主要的搜索引擎有哪些如果利用它们查找所需的信息 23.什么是电子邮件举例说明电子邮件地址的格式。 24. 计算机病毒通常由哪些危害请具体介绍你在自己学习或工作中使用的计算机上利用了哪些软件工具或使用了哪些方法防治计算机病毒的。 25. 请结合个人经验谈谈对于网络安全的认识。

同济大学研究生历年考试试卷回忆

同济大学2010年攻读硕士学位研究生入学考试试卷(请在答题纸上 做答,试卷上做答无效,试后本卷必须与答题纸一同交回)科目名称:交通工程适用专业:交通信息工程及控制,交通运输规划与管理,交通运输工程(专业学位) 本卷满分:150 分共 4 页第1 页 一、(每小题1分,共10分)判断题正确请在括号“()”中打“√”,错误请打“╳” 1、一人送货去某单位,送完货又去商店购物,然后回家,则其完成了一次出行。() 2、道路交通最基本的三要素是人、车、路。() 3、交通标志视认性的决定要素是交通标志的形状、颜色和图符。() 4、道路通行能力是指在一定的道路、交通状态和环境下,单位时间内(良好的天气情况下),一条车行道或道路的某一断面上能够通过的最大车辆或行人数量.亦称道路容量、交通容量或简称容量。() 5、在同一车道上,车辆突然遇到前方障碍物,如行人过街、违章行使交通事故以及其他不合理的临时占道等,而必须及时采取制动停车所需要的安全距离停车视距。这一过程包括:停车视距、制动距离和安全距离。() 6、交通标线按功能分为禁止标线和警告标线。() 7、地铁系统中,驾驶员的作用在于导向和控制车辆的行驶速度,而轨道仅仅起着支承车辆的作用。() 8、直线、圆曲线、缓和曲线是道路设计中平面线形的组成要素。() 9、城市公共交通是城市中供公众乘用的、经济方便的各种交通方式的总称,是由公共汽车、电车、轨道交通、出租汽车、轮渡、索道等交通方式组成的客运交通系统。() 10、山城或丘陵地区的城市交通干道的非直线系数一般建议控制在1.4之内。()第2 页

二、(每小题2分,共10分)名词解释,并说明其用途。 1. 高峰小时系数PHF。 2. 设计车速(Design speed)。 3. 车流密度。 4. 道路通行能力。 5. 延误 四、(每小题6分,共30分)简答题。 1. 影响道路交通行车速度的有关因素是什么? 2、单向交通的利弊及其实施条件是什么? 3、如何确定一般行车道的宽度? 4、什么是道路服务水平?划分依据是什么? 5、交通规划一般包括哪些基本内容和工作步骤? 五、(每小题12分,共60分)计算题。 1、一个周长为2公里长的圆环形车道上有三辆车分别以每小时100、120、140公里的速度不停地匀速行驶。假设可以自由超车,忽略超车时的距离和时间变化,根据这些数据计算如下基本交通特性参数: 1)计算环道车流密度; 2)在环路上一个固定点P观测1小时,求断面流量; 3)对整个环路进行瞬时观测,求空间平均速度; 4)求时间平均速度。第4 页

山东建筑大学

山东建筑大学第五届“艺术杯”大学生乒乓球赛 秩 序 册 主办:校团委 体育教学部 学生处 承办:艺术学院

2015.03. 第五届“艺术杯”大学生乒乓球比赛规程 一、比赛项目:设男、女团体。 二、报名形式:以学院为单位,男、女团体分别报4名队员,另报领队、教练各一人。 三、组织单位: 主办:山东建筑大学校团委、学生处、体育教学部 承办:艺术学院 四、比赛方法: 1.团体赛: 比赛分两个阶段进行。 第一阶段是分组循环,上届比赛前4名作为种子抽签分别进入A、B、C、D四个组别,其他院队随机抽入,每小组有3—4个参赛队。经单循环分别决出前两名,进入下一阶段。 第二阶段是淘汰加附加赛。各小组第一名重新抽签定位,分别进入上、下两个半区(1、4、5、8位):然后各小组第二名再抽签,分别进入上、下两个半区(2、3、6、7位),且只能进入同组别第一名的另一个半区,最后经淘汰加附加赛决出前八名。 五、奖励办法:团体奖励前八名(一等奖:一名;二等奖:两名;其余为三等奖)。 六、比赛地点:山东建筑大学新体育场北看台下乒乓球球室。

七、比赛时间:2015年4月11日 2015年4月11日(星期六)上午08:00-11:30 下午13:30-16:30 八、活动注意事项: 1)要求各学院体育部部长选派男、女团体分别报 4名队员,另报领队、教练各一人。(要求运动员身体健康,符合比赛条件方可参赛)请各参赛团队按水平高低进行报名,水平最高的运动员放在第一位,由高到低依次填写在报名表上。 2)请各学院根据学院具体情况进行训练,参赛时球拍自备,乒乓球由我院提供各学院带队学生认真组织本学院学生参加,不明事宜及时联系我院。 3)参赛者4月11日上午参赛者08:00到场,查看上场顺序。 八、比赛流程: 1)团体赛: 第一阶段(4月11日上午8:0 0-11:30 )分组循环赛各队抽签进入A、B、C、D四个组,经单循环分别决出各组的前两名进入下一阶段。 第一轮 8:30~9:30 第二轮9:30~10:30 第三轮10:30~11:30 第二阶段淘汰赛(4月11日下午13:30-16:30) 晋级参赛队重新进行抽签定位,经过淘汰加附加赛,分别决出前八名。*具体时间以比赛进程为准! 闭幕式暨颁奖典礼:4月11日16:30赛场举行闭幕式

南开大学--远程教育学院计算机应用基础考试题目在线作业

计算机应用基础教学大纲 练习题及答案 计算机基础知识 1.自计算机问世至今已经经历了4个时代,划分时代的主要依据是计算机的_____。A.规模 B.功能 C.性能 D.构成元件 答案 D 2.第四代计算机的主要元件采用的是_____。 A.晶体管B.电子管C.小规模集成电路 D.大规模和超大规模集成电路答案:D 3.世界上第一台电子数字计算机采用的逻辑元件是_____。 A.大规模集成电路B.集成电路C.晶体管D.电子管 答案 D. 4.当前的计算机一般被认为是第四代计算机,它所采用的逻辑元件是_____。 A.晶体管B.集成电路C.电子管D.大规模集成电路 答案 D

5.早期的计算机体积大、耗能高、速度慢,其主要原因是制约于_____。A.工艺水平B.元器件C.设计水平D.原材料 答案 B 6.个人计算机属于_____。 A.微型计算机 B.小型计算机 C.中型计算机 D.小巨型计算机 答案A 7.以下不属于数字计算机特点的是_____。 A.运算速度快 B.计算精度高 C.体积庞大D.通用性强 答案 C 8.冯.诺伊曼在研制EDVAC计算机时,提出了二个重要的概念,它们是_____。A.引入CPU和内存储器概念B.采用机器语言和十六进制 C.采用二进制和存储程序控制的概念D.采用ASCII编码系统 答案:C 9.计算机可以进行自动处理的基础是_____。 A.存储程序B.快速运算C.能进行逻辑判断D.计算精度高 答案 A

10.计算机进行数值计算时的高精确度主要取决于_____。 A.计算速度B.内存容量C.外存容量D.基本字长 答案 D 11.计算机具有逻辑判断能力,主要取决于_____。 A.硬件 B.体积 C.编制的软件 D.基本字长 答案 C 12.计算机的通用性使其可以求解不同的算术和逻辑问题,这主要取决于计算机的_____。 A.高速运算B.指令系统C.可编程性D.存储功能 答案 C 13.计算机的应用范围很广,下列说法正确的是_____。 A.数据处理主要应用于数值计算 B.辅助设计是用计算机进行产品设计和绘图 C.过程控制只能应用于生产管理 D.计算机主要用于人工智能 答案B

山东建筑大学计算机科学与技术学院2017年硕士研究生复试及拟录取办法【模板】

**大学计算机科学与技术学院 2017年硕士研究生复试及拟录取办法 一、复试时间 1、复试安排在在3月23-25日进行。 2、参加加试和笔试超过2小时以上复试科目的考生,在上述时间提前1天到学院教学办报到,报到时间为上午8:30-9:00,考试时间安排在上午9:30开始。 复试前2天,复试考生名单在学校研究生处网站公布(动态)。 二、招生学科及计划 三、调剂说明 调剂考生(含校内调剂)请在中国研招网调剂系统内填报志愿。 四、拟录取总成绩 1、笔试成绩不合格(少于60分)、或面试成绩不合格(少于90分)、或复试成绩不合格(少于180分)的考生不予录取; 2、复试专业笔试科目见招生简章; 3、面试时间20分钟/人左右。 五、拟录取办法 (一)拟录取程序 复试合格考生,按拟录取总成绩由高到低排序,按报考志愿在学科(培养方向)招生计划内确定拟录取名单,其中: 1. 我校校聘首席岗、重点岗教授(见导师简介),可自主优先录取1人; 2.在学科(培养方向)招生计划内,一志愿考生优先录取。 (二)相近学科(培养方向)调剂录取 复试合格但未被一志愿报考学科(培养方向)录取的考生,按拟录取总成绩由高到低征求考生意见,可调剂至有缺额的学科(培养方向),并签订学科(培养方向)调剂录取确认书。

(三)拟录取结果公示与确认 全部学科复试结束3天内,拟录取名单在学校研究生处网站公示。 调剂考生在接到拟录取通知24小时内,登陆研招网确认接收我校拟录取通知,未按规定时间确认者,视作放弃录取资格。 六、其他 1、请考生近期关注我校复试安排的有关通知,复试前确定复试笔试科目; 2、根据复试时间安排,考生25日上午9:00-12:00在BW011报到并完成资格审核后,请到计算机学院教学办(信息楼225)报到,随后到校医院查体。

全国高分子化学与物理排名

07中国研究生教育分专业排行榜(武汉大学中国科学评价研究中心):070305高分子化学与物理 排名学校等级排名学校等级排名学校等级 1 吉林大学A+ 6 南京大学A 11 中国科学技术大学A 2 复旦大学A+ 7 浙江大学A 12 北京化工大学A 3 南开大学A+ 8 四川大学A 13 清华大学A 4 北京大学A 9 上海交通大学A 14 武汉大学A 5 中山大学A 10 华南理工大学A B+ 等(22 个) :兰州大学、苏州大学、西北工业大学、东华大学、华中科技大学、郑州大学、华东理工大学、湘潭大学、山东大学、湖南大学、青岛科技大学、西北师范大学、大连理工大学、厦门大学、福建师范大学、河北大学、河南大学、安徽大学、福州大学、西北大学、广东工业大学、湖北大学 B 等(22 个) :东南大学、华侨大学、东北大学、河北工业大学、济南大学、哈尔滨工业大学、合肥工业大学、华东师范大学、南京工业大学、江西师范大学、西安交通大学、鲁东大学、北京师范大学、南京理工大学、江苏工业学院、北京航空航天大学、哈尔滨理工大学、上海大学、太原理工大学、华南师范大学、中北大学、陕西师范大学 C 等(15 个) :名单略 国家重点学科 北京大学南开大学中山大学复旦大学吉林大学南京大学 博士点 安徽大学北京大学北京化工大学北京师范大学大连理工大学东北师范大学东华大学福建师范大学福州大学复旦大学河北大学河南大学湖南大学华东理工大学华东师范大学华南理工大学华中科技大学吉林大学兰州大学南京大学南开大学青岛科技大学清华大学山东大学山西大学陕西师范大学上海交通大学四川大学苏州大学天津大学同济大学武汉大学西北大学西北工业大学西北师范大学厦门大学湘潭大学浙江大学郑州大学中国科学技术大学中国科学院研究生院中山大学

同济大学研究生指导教师工作(管理)细则(规定)

同济大学研究生指导教师管理工作条例(2008年11月25日校第九届学位评定委员会第五次会议审议通过) 一、总则 1.根据《中华人民共和国学位条例》和《同济大学学位授予工作细则》,制定本条例。 二、研究生指导教师岗位任职要求 2.本校在职教师申请担任研究生指导教师的基本条件 (1) 具有教师资格。 (2) 热爱研究生教育事业,了解并遵守国家有关研究生教育的政策法规,能教书育人,为人师表,具有高尚的科学道德、严谨的治学态度。 (3) 有较高的学术造诣和丰富的科研工作经验,所从事的研究方向有重要的理论意义或实际应用价值,承担国家或省部级科研项目或其它有重要价值的项目,科研经费充足。 (4) 年龄在人事部门规定的退休前三年。 3.博士生指导教师应具备的岗位任职条件 (1) 一般应具有博士学位的教授或研究员;或具有博士学位的副教授或副研究员,其所在学科应是评估质量良好、有两届以上博士生毕业的国家重点学科或上海市重点学科,并是学校批准的可由部分副教授或副研究员担任博士生指导教师的学科。 (2) 原则上全程指导过1届以上(含1届)硕士研究生,培养质量良好,且承担一定工作量的研究生教学任务。

(3) 须具有以下科研业绩: A.申请人文社科类学科和建筑学学科:近五年,应作为第一作者或国际学术期刊的通讯作者在SSCI、A&HCI、CSSCI收录的学术期刊源或经全国性学科专业指导机构认定的学术期刊上发表一定数量的学术论文或在国内外学术期刊发表并已被SSCI、A&HCI检索一定数量的学术论文,或正式出版高水平学术专著(或学术译著);近三年,作为第一负责人承担过本学科领域的国家、省部级科研项目,作为主要成员获得过省部级及以上科研成果奖。 B.申请理学、医学类学科:近五年,应作为第一作者或国际学术期刊的通讯作者在SCI收录的学术期刊源上发表一定数量的学术论文或在国内外学术期刊发表并已被SCI检索一定数量的学术论文,或正式出版高水平学术专著(或学术译著);近三年,作为第一负责人承担过本学科领域的国家、省部级科研项目,作为主要成员获得过省部级及以上科研成果奖或获得过国内外发明专利。 C.申请工学类学科:近五年,应作为第一作者或国际学术期刊的通讯作者在SCI或EI收录的学术期刊源上发表一定数量的学术论文或在国内外学术期刊发表并已被SCI或EI检索一定数量的学术论文,或正式出版高水平学术专著(或学术译著);近三年,作为第一负责人承担过本学科领域的国家、省部级科研项目,作为主要成员获得过省部级及以上科研成果奖或获得过国内外发明专利。 具有博士学位的副教授或副研究员应作为第一负责人承担过国家级基金项目。 4.硕士生指导教师应具备的岗位任职条件 (1) 具有硕士或博士学位的副教授、副研究员及以上职称;或具有博

高分子院士解析

2004年院士介绍 曹 镛 高分子化学家。 出生于湖南长沙。1965年毕 业于原苏联列宁格勒大学化学系。1987年获日本东京大 学理学博士学位。华南理工大学教授、高分子光电材料与 器件研究所所长。国内最早从事导电高分子研究的科学家 之一。与他人合作用稀土催化剂合成了有新的结构和形貌 特色的聚乙炔。率先合成苯胺及噻吩的齐聚物,并对其进 行掺杂和研究其结构与性能关系。他在用有机质子酸掺杂 聚苯胺制备可溶性的聚合物的基础上,提出“对阴离子诱 导加工性”的概念,解决了导电高分子的高导电性与加工性不能同时并存的难题,其研究结果已得到实际应用。此 外,成功地研制出可弯曲的塑料片基发光二极管;使铝阴极LED 的电荧光量子效率达到甚至超过钙阴极器件等。 2001年当选为中国科学院院士。 现有院士 程镕时 高分子物理及物理化学家。江苏宜兴人。1949年毕业 于金陵大学化学系。1951年毕业于北京大学化学研究部。南京 大学、华南理工大学教授。早年参加高分子分子表征的研究工 作,其结果为顺丁橡胶的工业化选型和优化提供了科学依据。 在高分子溶液粘度的研究工作中,提出一系列新概念和应用广 泛的公式。在凝胶色谱的研究工作中,阐明了多孔填料的成孔 机理并给出控制孔度的理论关系,建立了简易凝胶色谱方法、 凝胶色谱扩展和分离效应的统一理论、凝胶色谱的绝对定量化 原则和一种研究分子水平上的吸附作用以及分子间配合作用的有效而直接的定量方法,拓展了凝胶色谱的应用范围。近年在 对高分子溶液凝聚过程的研究中又取得新的进展。 1991年当选为中国科学院院士(学部委员)。 现有院士 冯新德

山东建筑大学计算机网络复习资料

各章重点内容 说明:通读教材、精读重点、熟练掌握作业题。 第1章计算机网络和因特网 1、通过网络链路和交换机移动数据有两种基本方法(构建网络核心的基本方法):电路交换和分组交换各自的特点以及适用情况(如课后习题2(简称为T2))。 电路交换:(circuit switching):网络为数据传输在传输路径上预留资源电话网(专用)通信双方在发送数据之前必须建立一条专用电路,在沿途预留资源。 特点:(专用)分配专用资源;性能保障;建立连接(传输、拆除连接) 多路复用(Multiplexing):将资源(如带宽)分成多个小片,一个小片分给一个call,拥有资源小片的Call不使用该小片时,该资源小片空 闲(资源独占) 时分复用:时间划分成一个个定长时间的Frame(结构,帧等),每个Frame 被划分成固定数量的时间槽(时隙)。当建立连接时,网络为每个连接分配Frame中的一个固定的时间槽(slot)。 适用情况: 分组交换:(packet-switching):数据被分成一个一个的分组计算机网络,将长报文分成一个一个的分组(packet),每个分组均携带目的地址,沿途所经过的packet switches根据packet所携带的目的地址决定其输出链路。交换机在转发一个分组时的速度为其输出链路的full速度。 特点:资源不预留,而采用按需分配的原则 与其他会话共享资源 无性能保证

统计时分复用:传统的时分复用接入的每个终端都固定地分配了一个公共信道的一个时隙,是对号入座的。正因为终端和时隙是“对号入座”的,所以它们是“同步”的。而异步时分复用或统计时分复用是把公共信道的时隙实行“按需分配”,即只对那些需要传送信息或正在工作的终端才分配给时隙,这样就使所有的时隙都能饱满地得到使用。 适用情况: 两者对比:1 Mbps link 每个用户: “活动时”所需数据传输速率:100Kbps 活动概率为:10% 电路交换: 10 个用户 分组交换: 如果有35个用户,11或更多个用户同时上网的概率小于 分组交换可以使用链路的full rate发送数据 例如 10个用户,其中一个用户突然产生一个 1000-bit 长的分组, 而 其他用户保持静默。 链路速率是1Mbps(即1000000bps) 电路交换 1000/100000=10ms 分组交换 1000/1000000=1ms 2、时延的分类及计算。(如T5、T18、T19、T21、T26)

同济大学研究生奖学金管理办法(同研[2014]31号)

同济大学文件 同研〔2014〕31号 关于印发《同济大学研究生 奖学金管理办法》的通知 各单位: 修订后的《同济大学研究生奖学金管理办法》经2014年5月26日第16次校长办公会议讨论通过,现予以印发,请遵照执行。 同济大学 2014年5月30日 —1 —

同济大学研究生奖学金管理办法 (2014年5月26日经第16次校长办公会议通过) 第一章总则 第一条为了激励我校研究生勤奋学习,刻苦钻研,积极进取,促进研究生全面发展,根据高校研究生培养的总体目标,结合我校研究生培养的实际情况,制定本办法。 第二条本办法适用于研究生国家奖学金、校级研究生奖学金(包括社会捐资设立的校级研究生奖学金和学校出资设立的奖励性质的研究生奖学金)以及在学校相关部门备案并与校级研究生奖学金统一评审的院(系)级研究生奖学金。面向港澳台研究生、外国来华留学研究生的奖学金管理办法,由学校另行制定。 第二章奖励标准 第三条研究生国家奖学金的奖励标准由国家制定,目前标准为:博士研究生国家奖学金3万元/人,硕士研究生国家奖学金2万元/人。 第四条学校出资设立的奖励性质的研究生奖学金奖励标准:优秀博士新生奖学金5000元/人,优秀博士生奖学金1万元/人,优秀硕士生奖学金5000元/人,研究生社会活动奖学金5000元/人。 第五条社会捐资设立的校级研究生奖学金奖励标准,根据捐赠协议确定。 —2 —

第三章奖励对象和基本申请条件 第六条本办法所指研究生奖学金的奖励对象,为在我校就读的具有中华人民共和国国籍且纳入全国研究生招生计划的全日制(全脱产学习)研究生(入学时人事档案和人事关系全部转入同济大学的研究生)。除特别说明外,一般为以下各类研究生(分类标准详见附件):普通研究生中的非定向学术型硕士、非定向专业学位硕士、非定向学术型博士、非定向专业学位博士研究生,人事档案和人事关系转入同济大学的少数民族高层次骨干人才计划研究生。除特别注明年级或修读期限的,均为二年级以上且在最长学习年限内的研究生。 第七条研究生奖学金的基本申请条件为: 1.热爱社会主义祖国,拥护中国共产党的领导; 2.遵守宪法和法律,遵守学校各项规章制度; 3.诚实守信,道德品质优良; 4.积极参加校内外科研和各种有益活动; 5.勤奋学习,刻苦钻研,学习成绩优秀,科研成绩明显,发展潜力突出。学术型研究生要有较强的科研创新能力,原则上要有体现创新能力的科研成果;专业学位研究生要有较强的专业实践能力和适应专业岗位的综合素质。 6.申请研究生社会活动奖学金者,要求积极参与组织各种有益活动或积极参加公益活动且表现突出。 7.申请面向新生的奖学金者,要求入学考试成绩或考核评价 —3 —

三本生考入南开大学计算机研究生的经历

南开大学软件学院专硕308分英语67 政治53 数学73 专业课115 考研复习最忌讳的就是跟别人去比较自己的复习进度,打乱自己的脚步,考研复习,不用报什么辅导班,那些我感觉都是骗人的,反正我是没报,拿同学的去听了一次,感觉太坑人了,自己对自己的复习要有计划,慢不要紧,但要有自己的节奏,我说说我当时的复习计划。英语9月分之前一直被单词,单词顶多背了2遍,最主要的是看考研语法,我用的是《新东方考研语法新思维》,我语法知识比较薄弱,我只看到第六章,虚拟语气之前,主要感觉时间不够了,但后来做题感觉六章已经够用,9月中旬之后才开始做真题,我用的《考研真相》,盗版的,20元一本,没必要买正版,一天做两篇阅读,一份卷子三天,但是一天必须翻译一篇文章,要把文章的每个句型结构搞清楚,分析清楚,《考研真相》做的挺好,里面带翻译,而且带个别句子的语法分析,一天坚持一篇,要把里面不会的单词抄出来(记得要把音标写上去),不要背过去就不看,要天天看,没事了就翻一下,(这里再说一点,会音标的同学最好,不会的同学最好抽时间学一下音标,我是9月分之前背单词,不会读,学的音标,发现单词记起来很快),做阅读的时候要抓住技巧,总结出自己的规律,刚开始做题错的很多,一篇阅读错三四个很正常,但别灰心,要继续做,正确率会越来越高。我刚开始准备报学硕,但后来感觉专把握更大,转了专硕,英语一改考英语二,但我还是用英语一的真题来练习,但只做到10年,主要是通过文章记单词,还有就是分析语法,就这样到十一月中旬,开始做英语二的真题,英语二真题只有三年,我之前翻译的文章03-09的真题,两个月下来应该有40多篇了,单词已经记了两个小本子,三年的卷子,做了两套,留了一套考前10天做一次,估一下自己的分数,这个分数也不准确,不要因为这个影响心情,就这样到考前,自己翻译的文章最少有60篇了,应付考试应该没多大问题,翻译也不用担心,因为平时翻译文章,再次提醒,翻译文章很重要。 可能还有就是担心作文,我是考英语二,大作文我用的《蒋军虎英语二高分作文》这上面的作文模板很有用,英语二考图标,把上面的作文模板背一下,应该背2篇就足够,考试大作文就没什么问题。 小作文用的新东方《考研英语写作范文100篇》主要是后面的小作文模板,有10多篇,但我把他们总结成4篇,因为很多小作文是关联的,那些模板我都给扔了,要不也给大家发上来,这样英语基本没什么问题了,67分不算太高,但对于我英语薄弱的人来说,我已经很知足了。 政治复习不复习感觉都没多大用,平时陪我的同学,政治考前看了看,乱翻了翻,竟然神奇般的考了56,我只考了53,我就感觉政治不怎么能拉开分,10月分开始就可以,两个月,红宝书就不用看了,感觉看不看没用,主要就是做题,还有就是考前那几本小册子记得要买,那个挺管用,大概写上去,别反动,基本上都能上50。 数学我就不想多说了,考的那叫一个差,73分,南开今年幸亏画到70,要不我本壁挂,我数学是考数学二把考的那些课本全看了,课后题全做了,《考研1500道客观题》做了两遍,考研真题做了两遍,本感觉数学复习的最好,谁知道今年那题有点变态,跟往年的风格根本不一样,能写的写,最后弄了73,万幸啊,李永乐复习全书线性代数挺好的,把那部分看看,不会的就翻课本,查复习全书,《考研1500道客观题》做两遍,基本上知识点就掌握了,但是我分数不高,没什么发言权。 专业课,南开大学今年专业课自主命题,提供了往年三分真题,我编程还算不错,数据结构学的还行,就报了南开的,今年软件学院专硕专业课编程题占到100分,数据结构填空50分,编程就是平时练得结果,我本科编程还算可以,数据结构用《高分笔记》这本挺好的,考试考得上面都有,然后就是红宝书《算法与数据结构考研试题精析》第二版这书相当好,上面都会了,哪个学校都一样考,但我只做了上面填空题,选择题,大题感觉没必要就没做,专业课115我们那排名倒数第二,哈哈,不过那些都是工作一年以上的人考的,咱认了。

中国传媒大学2018年《数据结构与计算机网络》考试大纲

中国传媒大学2018年《数据结构与计算机网络》考试大纲 一、考试的总体要求 《数据结构与计算机网络》是计算机科学与技术及相关学科的重要基础,本科目要求考生在数据结构方面:掌握数据结构的基本概念、基本原理和基本方法;掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析;能够运用数据结构基本原理和方法进行问题的分析与求解,具备采用C或C++或JAVA语言设计与实现算法的能力。在计算机网络方面:掌握计算机网络的基本概念、基本原理和基本方法;掌握计算机网络的体系结构和典型网络协议,了解典型网络的组成和特点,理解典型网络设备的工作原理;能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。 二、考试的内容 (一)线性表 1.线性表的定义和基本操作 2.线性表的实现:顺序存储,链式存储,线性表的应用 (二)栈、队列和数组 1.栈和队列的基本概念 2.栈和队列的顺序存储结构 3.栈和队列的链式存储结构 4.栈和队列的应用 5.特殊矩阵的压缩存储 (三)树与二叉树 1.树的概念 2.二叉树:二叉树的定义及其主要特征,二叉树的顺序存储结构和链式存储结构,二叉树的遍历,线索二叉树的基本概念和构造 3.树、森林:树的存储结构,森林与二叉树的转换,树和森林的遍历 4.树与二叉树的应用:二叉排序树,平衡二叉树,哈夫曼(Huffman)树和哈夫曼编码 (四)图 1.图的基本概念 2.图的存储及基本操作:邻接矩阵法,邻接表法 3.图的遍历:深度优先搜索,广度优先搜索 4.图的基本应用:最小(代价)生成树,最短路径,拓扑排序,关键路径 (五)查找 1.查找的基本概念 2.顺序查找法 3.折半查找法 4.散列(Hash)表 5.查找算法的分析及应用 (六)排序 1.排序的基本概念 2.插入排序 3.起泡排序(Bubble Sort) 4.简单选择排序 5.希尔排序(Shell Sort)

同济大学研究生课程教学大纲

同济大学 研究生课程教学大纲 课程名称 所在院(系、所) 适用专业 填表日期 同济大学研究生院培养处制

课程编号:(请用4号字填写) 课程名称:(请用黑体4号字填写) 英文名称:(请用4号字填写) 开课单位:(请用宋体5号字填写)开课学期:(请用宋体5号字填写)课内学时:(请用宋体5号字填写)教学方式:(请用宋体5号字填写)适用专业:(请用宋体5号字填写)考核方式:(请用宋体5号字填写)预修课程:(请用宋体5号字填写) 一、教学目标与要求(请用宋体5号字填写) 二、课程内容与学时分配(请用宋体5号字填写) 三、实验及实践性环节(注:此项没有的不填)(请用宋体5号字填写)

四、教材(序号,编著者姓名,教材名称,出版社,版次,出版日期) (请用宋体5号字填写) 主要参考书(序号,编著者姓名,教材名称,出版社,版次,出版日期) (请用宋体5号字填写) 大纲撰写负责人:(请用宋体5号字填写)授课教师:(请用宋体5号字填写)

课程编号:000109 课程名称:矩阵论 英文名称:The Theory of Matrices 开课单位:081(理学院数学系)开课学期:1 课内学时:60 教学方式:讲授 适用专业:工科各专业考核方式:考试 预修课程:线性代数、高等数学 一、教学目标与要求 本课程较全面、系统地介绍矩阵的基本理论、方法和某些应用,重点是线性空间及其映射、变换,以及矩阵运算等。难点是理解线性空间、线性映射、线性变换的不变子空间、 λ矩阵在相抵下的标准形和矩阵算子范数等抽象概念以及计算线性映射在基下的矩阵、- 的各种因子分解等。通过本课程中基本概念和基本定理的阐述和论证,培养研究生的抽象思维与逻辑推理能力,提高研究生的数学素养。在重视数学论证的同时,强调数学概念的物理、力学等实际背景,培养研究生应用数学知识解决实际工程技术问题的能力。通过本课程的学习,要求研究生掌握矩阵的基本理论和方法,为学习后续课程、开展科学研究打好基础。 二、课程内容与学时分配 第一章线性空间与内积空间(8学时) 1.1 预备知识:集合·映射与数域 1.2 线性空间 1.3 基与坐标 1.4 线性子空间 1.5 线性空间的同构 1.6 内积空间 第二章线性映射与线性变换(8学时) 2.1 线性映射及其矩阵表示 2.2 线性映射的值域与核 2.3 线性变换 2.4 特征值与特征向量 2.5 矩阵的相似对角形 2.6 线性变换的不变子空间 2.7 酉(正交)变换与酉(正交)矩阵 第三章λ-矩阵与矩阵的Jordan标准形(8学时) 3.1 一元多项式 3.2 λ-矩阵及其在相抵下的标准形3.3 λ-矩阵的行列式因子和初等因子 3.4 矩阵相似的条件 3.5矩阵的Jordan标准形 3.6 Cayley-Hamilton定理与最小多项式 第四章矩阵的因子分解(8学时) 4.1 初等矩阵 4.2 满秩分解 4.3 三角分解 4.4 QR分解 4.5 Schur定理与正规矩阵 4.6 奇异值分解

山东建筑大学计算机学院算法分析算法复习题(Yuconan翻译)上课讲义

山东建筑大学计算机学院算法分析算法复习题(Y u c o n a n翻译)

1.The O-notation provides an asymptotic upper bound. The Ω-notation provides an asymptotic lower bound. The Θ-notation asymptotically a function form above 2.To represent a heap as an array,the root of tree is A[1], and given the index i of a node, the indices of its parent Parent(i) { return ?i/2?; },left child, Left(i) { return 2*i; },right child, right(i) { return 2*i + 1; }. 代表一个堆中的一个数组,树的根节点是A[1],并且给出一个节点i,那么该节点的父节点是左孩子右孩子 3.Because the heap of n elements is a binary tree, the height of any node is at most Θ(lg n). 因为n个元素的堆是一个二叉树,任意节点的树高最多是 4.In optimization problems, there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem. 在最优化问题中,有很多可能的解,每个解都有一个值,我们希望找到一个最优解(最大或最小),我们称这个解为最优解问题。 5.optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. 最优子结构中问题的最优解,至少包含它的最优解的子问题。 6. A subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1, 2, ..., k, we have x i j= z j . Let X = and Y = be sequences, and let Z = be any LCS of X and Y. (1). If x m = y n, then z k = x m = y n and Z k-1 is an LCS of X m-1 and Y n-1. (2). If x m ≠ y n, then z k ≠ x m implies that Z is an LCS of X m-1 and Y. (3). If x m ≠ y n, then z k ≠ y n implies that Z is an LCS of X and Y n-1. 7. A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. 贪心算法经常需要在某个时刻寻找最好的选择。正因如此,它在当下找到希望中的最优选择,以便引导出一个全局的最优解。 8.The greedy-choice property and optimal sub-structure are the two key ingredients of greedy algorithm. 贪心选择和最优子结构是贪心算法的两个重要组成部分。 9.When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has overlapping subproblems. 当一个递归算法一遍一遍的遍历同一个问题时,我们说这个最优化问题是重叠子问题。 10.greedy-choice property is a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. 贪心选择性质是一个全局的最优解,这个最优解可以做一个全局的最优选择。

同济大学考研初试复试经验

刚同济大学复试结束,空闲点时间,经常有打算考研的学弟学妹问情况,本主牺牲一下,倚老卖老写点,希望有点帮助。预祝每个人都有好的前程。 我不想讨论上研有没有用的问题,我个人以为如果起点太低,很难发展,蚁族蜗居,连工作都是问题,仅仅用理想来麻痹自己罢了,浪费青春。不要把自己放在很低的起点上和别人竞争,没有优势的。 考研前期准备,一定要找一个很合得来的研友,不管同性异性,一定要在一起很舒服的那种,一个人很难熬,撑不下来的。么有研友,有一个固定陪你上自习的也好。 还有,最好给自己一个理由坚持,不然你自己都迷茫,我给自己的理由就是,如果不参加研究生考试,不走进考场,我一辈子都会遗憾。我没有拿研究生就业发展什么的对比,就是给了自己这么一个简单的理由,有时候,理由越简单越不容易被各种杂七杂八影响。 考研分初试和复试,都很重要,哪步错了都不可能。 关于初试 初试四门,一般都是英语政治,再加数学专业课,或者两门专业课。总分500分。复习的时间最好在五一左右,不管别人怎么样,你自己一定要有充足的准备,否则后期会手忙脚乱,一瞬间就可能崩溃。复习时效率尽可能高,你可以周六周天休息一下,但学习时就认真学。 辅导班个人以为一点没必要,百分百浪费时间,而且会让你很浮躁,静不下心学点真正有用的知识。其实如果你想上,石油大学的辅导班有一个同学报了,跟着去噌课就行。 政治(100分,不拉分,一般都60—70)复习的重点在教育部的大纲,不要相信什么辅导班,更不要把自己的前途押在那些烂题海中。他们讲他们押中多少题,那百分百放屁,每年都这样,他们根本不可能的,一个也没有。如果你把大纲放一边,去参加浪费时间的辅导班,那你就低估了教育部命题的人。不要相信那些辅导班的老师,什么什么原命题小组的哪个专家,毕竟今年不是他们命题,而且今年命题的都盯着他们呢,说不定他们预测的,命题小组都刻意不采用的。 英语(100分,不拉分50—60之间,很难考高)一点不用报班,真的没有用,因为英语不拉分,考高不可能。没有听力,阅读很重要,作文不用放心上,复习不复习作文分值差不了几分的,最后几天背一篇万能范文就行了。刚开始一个月把考研单词句子好好看一遍,以后的重点就是阅读和真题,英语真题特别重要,一定要保证三遍以上。吃透,每一个题,其实每年阅读的题型都差不多,答案甚至可以在近似的部位找到。完型阅读中,答案A/B/C/D 的数目是一样的,为了防止瞎蒙题得高分,所以如果你的答案ABCD的数目不相等,刚好其它的你都有把握,这样就按这个规律就行了,我也是偶尔发现的。关于排序题,一般第一段都是字母B,因为不可能把开头段落放在后面,这样你不好找。 数学(150分,挺拉分,最好不要低于120)更不用报班了,考研数学全在自己,其他什么辅导班啦绝对帮不上忙,还会让你更浮躁。刚开始把课本(同济大学数学和线代,高教或者浙大的概率论)夯实基础,复习材料就用李永乐的那本厚书就行,挺好用,上面的每一个细节都要夯实,不要图省事怕麻烦,不考研不就更省事了。也许你嫌一个公式难记,侥幸心理不要有,不要有漏洞,关键时候可能会造成不可弥补的损失。后期就把400题,还有超越135分好好看看,尤其是新题型做好,二李还是很牛的,今年试卷的新题型很可能是上年400题和135分上面的。 专业课(150分,挺拉分,最好不低于120)重点在历年真题,每年的重复率都很高,在70%以上。一定要想方设法弄到历年真题,不要相信没有真题,真题不外流,那是他没搞到,都有的,最好联系你要报考学校的学长帮你弄题。不要相信网上卖的,很多都是假的,即使要网上买,一定要确认身份,把他的身份证号要来,去专门网站核实一下。网上的骗子很多的,银行卡的话打完钱不给你发货的很多,要留意。

相关主题