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

A line plus a point not on it fixes a plane: build two in-plane directions, cross them for the normal, and write the point-normal equation.

A sequence given by x_{n+1}=f(x_n) converges once you show it is bounded and monotone; then the limit must be a fixed point f(L)=L.

Relative errors of a product don't simply add: $\delta(ab)=\delta(a)+\delta(b)+\delta(a)\delta(b)$. The cross term is the catch, and it vanishes exactly when one factor is exact.

Slice a solid perpendicular to one axis, integrate the cross-sectional area A(y); for a sphere drilled through its center, the leftover ring's volume depends only on the ring's height, not the sphere's radius.

Irrational just means "not a fraction"; algebraic vs. transcendental is a finer split — algebraic numbers are roots of integer polynomials and are closed under arithmetic and radicals, while transcendental numbers like $\pi$ and $e$ satisfy no such polynomial.

$(x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}y^{n-k}$; read backwards, any sum $\sum_k\binom{n}{k}c^{k}$ collapses to $(1+c)^{n}$.

"if" introduces the hypothesis, "only if" the necessary consequent, and "unless" means "if not" — three connectives, three fixed implication patterns that konkur loves to swap.

Each rung pair holds at most one vertex, so a large independent set fixes which columns are used; the empty columns cut the rest into paths, and every path contributes a factor of $2$ (outer/inner must alternate).

Color the cells/vertices in a dependency order; each new one has $k$ minus the number of already-colored neighbors choices, and you multiply.

Count the truth assignments that make a formula true by exploiting free variables, shared-head case splits, and the 2^r - 1 rule for a single clause.

A reflexive, symmetric, transitive relation slices a set into disjoint equivalence classes that partition it; count the distinct classes, not the elements.

To decide if a first-order formula is true, plug the structure's domain and the interpretations of its predicate/function symbols into the formula, then evaluate atoms, connectives, and quantifiers over that domain.

To count tile/object placements on a damaged or restricted board, count on the clean board and subtract the placements the obstruction kills: $\#\text{good}=\#\text{all}-\#\text{blocked}$.

The hypercube Qn connects n-bit strings (or subsets of an n-set) that differ in one bit; it is n-regular and bipartite, and for n >= 1 always has a perfect matching and a Hamiltonian cycle (n >= 2).

$\prod_{i\in I} X_i$ is the set of choice functions $f:I\to\bigcup_i X_i$ with $f(i)\in X_i$ — one element picked from each $X_i$.

A monotone $F:P(A)\to P(A)$ has a least fixed point, equal to $\bigcap\{X : F(X)\subseteq X\}$ — the intersection of all its pre-fixed points.

A tree has at most one perfect matching (uniqueness, via the acyclic symmetric-difference argument); and any graph on $2n$ vertices with minimum degree $\ge n$ has a perfect matching (existence, Dirac-type).

A linear recurrence reduced mod $m$ depends only on a finite state of past residues, so its residue sequence is eventually **periodic** — find the period, then answer any far-out term with $n \bmod p$.

Count injective assignments (distinct objects to distinct slots) under forbidden pairings by placing the most-constrained slot first and multiplying the shrinking choice counts.

$S(n,k)$ counts the ways to split an $n$-set into exactly $k$ nonempty, unlabeled blocks; use the recurrence $S(n,k)=k\,S(n-1,k)+S(n-1,k-1)$ or direct case-by-size counting.

A heap orders each node only against its *children* (vertical, partial); a BST orders each node against *whole subtrees* (horizontal, total) so an in-order walk is sorted — that gap forces an $\Omega(n\log n)$ comparison cost to turn a heap into a BST.

Every square matrix satisfies its own characteristic polynomial; rearranging that polynomial expresses $A^{-1}$ as a cheap polynomial in $A$ — no cofactor matrix needed.

The determinant is linear in each row and alternating, so scaling a row scales it, swapping rows flips the sign, and any repeated row makes it zero — that is all you need to evaluate "transformed-matrix" determinant problems.

For any square matrix the trace equals the sum of the eigenvalues and the determinant equals their product — and these are exactly the constraints that pin down unknown eigenvalues on the exam.

For two subspaces, $\dim(U+W)=\dim U+\dim W-\dim(U\cap W)$ — an inclusion–exclusion for dimensions that pins down (or bounds) the size of an intersection.

A linear map becomes a matrix once you fix a basis: its $j$-th column is the image of the $j$-th basis vector, written in that same basis's coordinates.

An R-linear map on C need not be C-linear; realify it as a 2x2 real matrix in the basis {1, i} and take that matrix's determinant.

A robust, quartile-only measure of asymmetry: $\mathrm{Skew}_Q=\dfrac{Q_3+Q_1-2Q_2}{Q_3-Q_1}$, always in $[-1,1]$, with sign set by which half of the IQR the median sits in.

Series blocks multiply reliabilities; parallel blocks multiply *unreliabilities*. Collapse the network inside-out, treating each block as one component.

When several groups are pooled, the total sum of squared deviations from the grand mean splits cleanly into a within-group part plus a between-group part — the discrete parallel-axis (ANOVA) identity.

Run two DFAs in lockstep on the same input — states are pairs ⟨q1,q2⟩ — then pick the accepting pairs to realize any Boolean combination: AND for ∩, OR for ∪, XOR for symmetric difference, AND-NOT for set difference.

Rip out states one by one, rerouting their paths into edge labels, until only start and accept remain; what's left on that edge is the regular expression — Arden's rule does the same job algebraically.

Regular languages are closed under every standard operation — union, intersection, complement, concatenation, star, reversal, homomorphism — but a countably infinite union of regular languages need not be regular.

Every regular language has a pumping length p such that any long string splits as xyz with y pumpable; find one long string whose every legal split breaks membership, and the language cannot be regular.

P is the set of languages decided by ONE algorithm in ONE fixed polynomial time bound for ALL inputs — the order ∃A ∃c ∀x is what makes it polynomial.

On an array of size n, Quicksort's comparison count is a random quantity ranging from n*log n (best) to n(n-1)/2 (worst), determined entirely by how each pivot splits its subarray.

Checking whether a claimed list of probes is the exact sequence a binary search would make costs only Θ(n) — replay the deterministic search and compare, never re-sort or re-search.

An alternating series converges if its terms shrink monotonically to 0; combine with absolute convergence to label it absolutely, conditionally, or divergent.

If a series' terms are eventually trapped between 0 and a constant multiple of a known convergent series, it converges too — the engine behind reasoning about square-summable sequences.

The condition number measures how much a linear system amplifies input error, costing you about log10(kappa) reliable digits.

The outward flux of a vector field through a closed surface equals the triple integral of its divergence over the enclosed solid.

At every point the gradient points toward the fastest increase, and its magnitude is exactly that maximum rate of change.

The sector swept from the origin along the unit hyperbola $x=\cosh t,\,y=\sinh t$ has area exactly $t/2$ — the geometric meaning of the parameter.

When a system implicitly defines several variables in terms of others, differentiate the equations in place and solve a small linear system (Jacobian) for the partials — no explicit formulas needed.

A monotone function can only have jump discontinuities, and the set of those jumps is always at most countable — never an interval, never uncountable.

How to transform a second-order PDE under a linear change of variables: build the first-order operators from the chain rule, apply them twice to get the second derivatives, and substitute to simplify (e.g. the wave equation into canonical form).

To find [x^n] of an integral with a variable upper limit, expand the integrand as a power series, then bump each exponent up by one and divide: the x^n coefficient is c_{n-1}/n.

For a solid with rotational symmetry, switch to cylindrical coordinates ($dV=r\,dz\,dr\,d\theta$) and integrate $\rho\,r^{2}$ to get the moment of inertia $I_z$ about the axis.

A 2-(v,k,λ) design is a family of k-subsets (blocks) of a v-set in which every pair of points lies in exactly λ blocks. Two counting identities fix r and b; the Fano plane is the 2-(7,3,1) design, and complementing its blocks gives the 2-(7,4,2) design.

Interior is the largest open set inside A, closure the smallest closed set containing A, and boundary what is left over; complementing swaps interior and closure via two duality identities.

Every simple planar graph on n ≥ 3 vertices has at most 3n−6 edges — a direct consequence of Euler's formula, and an instant non-planarity test.

If a count cares only about the relative order of k special positions and otherwise treats all their orderings symmetrically, exactly 1/k! of the unconstrained configurations realize each fixed order.

Each ZF axiom is a license to form a new set from old ones; knowing which axiom does which job lets you justify every set-building step.

An AVL tree keeps every node's left/right subtree heights within 1; after an insert or delete, a single or double rotation at the lowest unbalanced node restores the invariant in O(log n).

Given an ordered basis B of a vector space, every vector has a unique tuple of coordinates: the scalars in its expansion over B. Finding them means solving a linear system.

Factor out a common matrix power, then left- or right-multiply by its inverse to cancel it — only legal when that factor is invertible.

The minimal polynomial equals the characteristic polynomial exactly when each eigenvalue has a single Jordan block (one eigenvector apiece).

Sampling k items without replacement from a population of N with K special ones: count the favorable draws sequentially, or use the hypergeometric formula — both give the same answer.

A stem-and-leaf plot lists every data value as stem + leaf; rebuild the values, sum them, and divide by the count to get the mean.

One stack = exactly the CFLs; TWO independent stacks = a full Turing machine. The number of stacks, not the fancy access rules, is what jumps you past context-free.