کارت‌های مفهوم و فرمول کنکور ارشد علوم کامپیوتر

Turn a constant-coefficient recurrence into a polynomial; its roots (and their multiplicity) give the closed form.

A machine operation is error-free only when its exact result fits a normalized t-bit mantissa (leading bit 1) times a power of two.

The bottom-right block H of M^{-1} satisfies det(M)det(H)=det(A), the diagonally opposite block.

CV = sigma/mu normalizes spread so data sets with different means can be compared for relative variability.

A map between C-vector spaces is C-linear iff it is additive and homogeneous for every complex scalar.

Split the conditioning event into disjoint pieces to expand its probability, then apply the conditional-probability definition.

A real cubic is bijective exactly when its derivative never changes sign, i.e. the discriminant of P' is non-positive.

Eigenvalues are the roots of $\det(A-\lambda I)$, and structure pins them down: triangular matrices show them on the diagonal, nilpotents force $0$, and real symmetric matrices have real eigenvalues with orthogonal eigenvectors.

On subsets of N, A is equivalent to B iff A delta B is finite: each class is countable, but there are continuum-many classes.

The symmetric 5-point stencil approximates f'' to order h^4 using coefficients {-1, 16, -30, 16, -1}/(12h^2).

The order of a fixed-point iteration equals the index of the first non-vanishing derivative of g at the fixed point.

A geometric series with |r| < 1 converges to (first term) / (1 - r).

An invertible idempotent matrix must equal the identity, so all its eigenvalues are 1.

A function is a total single-valued map; injectivity/surjectivity/bijectivity control cardinality, and preimages commute with every set operation while images only respect unions.

Convert a radially symmetric integral over the whole plane to polar form, reducing it to a single improper p-integral in r.

Count the union of two sets by adding their sizes and subtracting the double-counted overlap.

For nested indexed intervals, a union takes the largest member and an intersection takes the smallest.

If f is increasing on [a,b], then g(x)=∫_a^x f is convex, continuous, and Lipschitz, but increasing only when f≥0.

Compute an iterated double integral from the inside out, treating the outer variable as a constant during the inner integration.

An overdetermined system Ax=b is fit by least squares via the normal equations A^T A x = A^T b.

Minimize the plane-distance formula over the surface, often collapsing to an algebraic inequality.

To negate a quantified sentence, push the negation inward: flip every quantifier ($\forall\leftrightarrow\exists$) in order and negate the innermost predicate, turning $\wedge/\vee$ and $\to$ by De Morgan.

For an m x n matrix, dim(null space) = n - rank(A), so any wide matrix (more columns than rows) always has nonzero kernel.

Infinite unions of closed intervals can be open and infinite intersections of open intervals can be closed, so always compute the actual set.

When some elements are locked into specific slots, only permute the remaining free elements.

For a plane curve $r(t)=(x(t),y(t))$, the radius of curvature is $R=1/\kappa$ with $\kappa=|x'y''-y'x''|/((x')^2+(y')^2)^{3/2}$.

Convert a hard closed line integral into a curl flux through any bounding surface.

A function continuous on R with finite limits at both +inf and -inf is uniformly continuous.

When one hit strikes exactly one of n items uniformly, any k specific items all survive with probability (n-k)/n.

Zorn's Lemma, the Hausdorff Maximal Principle, well-ordering, and cardinal comparability are all logically equivalent to the Axiom of Choice.

Fit data exactly with the unique degree-n polynomial (Lagrange/Newton) or a smooth C^2 cubic spline, and bound the polynomial error by f^(n+1)/(n+1)! times the node product.

Insertion sort is adaptive: it runs in $\Theta(n)$ on nearly-sorted input where merge/quicksort still pay $\Theta(n\log n)$.

Floyd-Warshall is the dynamic-programming algorithm that finds shortest paths between every pair of vertices in $\Theta(n^3)$.

Adding terms of lower-or-equal order keeps Theta; the largest term dominates, and identities can break when f is not assumed to grow.

Backtracking suits feasibility/constraint-satisfaction searches; Branch and Bound adds a cost bound for optimization.

On adjacency lists, BFS touches every undirected edge twice (once per endpoint), giving total work $\Theta(V+E)$.

A plain BST is not balanced, so its height ranges from $\Theta(\log n)$ down to $n-1$ and its leaf count from $1$ to $\lceil n/2\rceil$.

A plain BST has no balance guarantee, so its worst-case height is $\Theta(n)$, making search/min/max $O(n)$.

Read off the single count equality each grammar branch enforces, then test a candidate string by comparing letter counts instead of building derivations.

A language is context-free if its only stack obligation is one matching, plus regular filters that closure preserves.

When almost all states accept, count total strings and subtract those that fall into the trap state.

Dijkstra is correct iff all edge weights are non-negative; cycles (even directed) are irrelevant.

Dijkstra is correct only when all edge weights are non-negative; 'no negative cycle' is not enough.

Huffman greedily merges the smallest weights into an optimal prefix-free tree; the same rule gives k-ary (e.g. ternary) Huffman and optimal-merge patterns whose cost is the weighted path length.

Merging $k$ sorted lists with $n$ total elements costs $\Theta(n\log k)$, which is $O(n)$ only when $k$ is constant.

Kruskal sorts edges by weight and accepts an edge only if its endpoints lie in different components; otherwise it would close a cycle and is rejected.

When the per-call work f(n) outgrows the watershed n^(log_b a), the recurrence is dominated by the top level and T(n)=Theta(f(n)).

Picking the exact median as pivot gives a perfectly balanced split, yielding $T(n)=2T(n/2)+f(n)+\Theta(n)=O((n+f(n))\log n)$.

Greedily build a cheapest set of edges that connects all vertices with no cycle, using exactly n-1 edges.

Pick the right boundary string, then show every split uvxyz with |vxy|<=p can be pumped out of the language.

BST over n keys with access frequencies that minimizes expected search cost, not height.

An algorithm cannot run faster than the size of the output it must produce, so enumerating exponentially many objects takes exponential time.

Simulate the PDA step by step, tracking the stack; accept only if input is fully consumed AND you land in a final state (or empty the stack).

Translate a regular expression into a forbidden-pattern rule, then test a string by structure instead of full parsing.

L/{a} = {w : wa in L} is regular: keep the DFA, only re-mark accepting states.

Finite (bounded) memory like parity stays regular; comparing unbounded counts does not.

Each element of an n-set sits in exactly $2^{n-1}$ subsets, so the total of all subset-sums is $2^{n-1}$ times the element sum.

When the argument shrinks by a constant (n-1) instead of a factor, unroll the recurrence; a branching factor a>1 gives exponential growth $\Theta(a^n)$.

A worst-case upper bound ("runs in at most ...") limits the slowest run but says nothing about average case or behavior on a specific input.

A product automaton that advances one component per symbol recognizes the shuffle of the two languages.