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

Recognize the right-scan + carry-from-the-right pattern that computes x+1 in binary.

The subset-of-a-subset identity $\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}$ lets you factor a fixed $\binom{n}{k}$ out of any sum over the middle index, after which the leftover collapses to a clean row sum such as $2^{n-k}$.

An edge is a bridge exactly when it lies on no cycle, so a bridgeless graph is one in which every edge sits on some cycle.

Every set is *strictly* smaller than its power set, $|X| < |\mathcal{P}(X)|$, so no surjection (and hence no bijection) $X \to \mathcal{P}(X)$ exists — which is why $|\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} > \aleph_0$.

The set of all functions $A\to B$ has cardinality $|B|^{|A|}$, and cardinal-exponent identities collapse most "big-looking" function spaces over a countable domain down to the continuum $2^{\aleph_0}$.

To keep restricted items apart, seat the unrestricted majority first, then drop the restricted items into the gaps between them.

Countability survives countable unions, finite-subset collections, and surjective images, because $\aleph_0\cdot\aleph_0=\aleph_0$ and a surjection $f:B\twoheadrightarrow A$ forces $|A|\le|B|$.

The number of walks of length $k$ from $i$ to $j$ is the $(i,j)$ entry of $A^k$; length-$2$ paths come from counting neighbor-pairs per vertex.

A consistent theory with no finite models that is categorical in some infinite cardinal is complete (Los-Vaught); DLO without endpoints and the Rado graph are the textbook examples, both made categorical by Cantor's back-and-forth.

$\mathfrak{A} \preceq \mathfrak{B}$ holds iff every existential formula with a witness in $\mathfrak{B}$ already has one in $\mathfrak{A}$ (Tarski-Vaught), and the union of an elementary chain is an elementary extension of each member.

To count tilings or step-climbing sequences, case on the leftmost piece (or first move): each choice removes a fixed prefix and leaves a smaller instance, turning the count into a linear recurrence.

Translate natural language by pairing $\forall$ with $\to$ and $\exists$ with $\wedge$; remember $\forall$ distributes over $\wedge$ and $\exists$ over $\vee$ (and never the mismatched pairs).

For any set $X$ the Hartogs number $\aleph(X)$ is, provably in ZF alone, the least ordinal that does not inject into $X$ — the engine that turns the Axiom of Choice into the Well-Ordering Theorem.

Size of a union of $n$ sets is the alternating sum over all intersections; sieving by the prime divisors of $m$ counts integers coprime to $m$.

When vertices are the $k$-subsets of an $n$-set and edges encode a fixed intersection size, the graph is automatically regular, and its degree and edge count fall straight out of binomial counting.

An argument is valid (and $\Gamma\models\varphi$ holds) exactly when no interpretation makes all premises true and the conclusion false, so one counterexample is enough to refute it.

Pairwise-distinct edge weights force a single MST; uniqueness fails exactly when some cycle has a non-unique heaviest edge (a tie), so ties — not the cheapest edge — decide the count.

Guess a particular solution shaped like the forcing term (polynomial, exponential, or their product), match coefficients to solve for it, and multiply by a power of $n$ whenever the guess collides with a root of the homogeneous part.

DNF is an OR of ANDs of literals and CNF is an AND of ORs of literals; every propositional formula is logically equivalent to one of each.

Ordinal sum and product are defined by "concatenating" order types and are associative but **not** commutative — a finite ordinal is absorbed on the left ($n+\omega=\omega$, $2\cdot\omega=\omega$) yet sticks out on the right ($\omega+n>\omega$, $\omega\cdot 2>\omega$).

Ordinal exponentiation is defined by a supremum at limit stages, so a finite base raised to $\omega$ collapses to $\omega$ ($3^{\omega}=\omega$), whereas the same expression read as cardinals gives the continuum ($3^{\aleph_0}=2^{\aleph_0}$).

If $n+1$ items land in $n$ boxes, some box holds two; generalized, $N$ items force a box with $\lceil N/n \rceil$ — the engine behind "smallest forcing $n$" exam problems via residue/parity coloring.

Being a member of $P(A)$ means being a subset of $A$: $S \in P(A) \iff S \subseteq A$.

When a characteristic root $r$ is repeated with multiplicity $m$, it contributes $(c_0 + c_1 n + \dots + c_{m-1} n^{m-1})\,r^n$ to the general solution, not just $c\,r^n$.

The number of nonnegative integer solutions of $x_1+\cdots+x_k=n$ is $\binom{n+k-1}{k-1}$; clear lower bounds by shifting variables, and switch to the bars-in-gaps count when objects are ordered.

The number of trailing zeros of $n!$ in base $b$ is the minimum, over the prime powers $p^e \| b$, of $\lfloor v_p(n!)/e \rfloor$, where Legendre's formula gives $v_p(n!) = \sum_{i\ge 1} \lfloor n/p^i \rfloor$.

For an NP-hard optimization problem, a polynomial-time rho-approximation guarantees a solution within a factor rho of the optimum; the ratio is a monotone worst-case bound (factor c gives every c' >= c for free) and is defined only for optimization, never for decision, problems.

DP applies when an optimal solution is built from optimal solutions of overlapping subproblems; pick a state, write a recurrence, and evaluate it bottom-up (tabulation) or top-down (memoization).

In any flow network the value of a maximum $s$-$t$ flow equals the capacity of a minimum $s$-$t$ cut; a flow is maximum exactly when its residual graph has no augmenting path, which is how Ford-Fulkerson finds it.

A problem is NP-complete when it is both in NP and NP-hard; under the assumption $P \ne NP$ such problems have no polynomial-time algorithm, and we prove hardness by a polynomial-time reduction from a known hard problem like SAT, Knapsack, or TSP.

The arc length of $y=f(x)$ is $\int\sqrt{1+(y')^2}\,dx$; for the catenary $y=a\cosh(x/a)$ the identity $1+\sinh^2=\cosh^2$ erases the square root, giving length $a\sinh(x_1/a)$.

Through any $n+1$ points with distinct nodes there is a unique polynomial of degree $\le n$; Lagrange and Newton are two ways to build the same polynomial.

To solve $f(x)=0$, iterate $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$ — each step replaces $f$ by its tangent line and takes its root; near a simple root it doubles the number of correct digits per step.

Integrate by parts to express an integral with exponent $n$ in terms of the same integral with a smaller exponent, building a recurrence you can iterate down to a base case.

A set of connectives is functionally complete if it can express every truth function; $\{\neg, \land\}$, $\{\neg, \lor\}$, and $\{\neg, \to\}$ all qualify, and the single connectives NAND ($\mid$) and NOR ($\downarrow$) each suffice on their own.

Encode a sequence $a_0,a_1,\ldots$ as the coefficients of a power series $\sum a_n x^n$, then turn counting and recurrence problems into algebra: multiply to combine choices, and extract $[x^n]$ to read off the answer.

Prove propositional formulas with introduction/elimination rules arranged into a derivation tree, discharging temporary assumptions via $\to I$; the system is both sound (only valid conclusions follow) and complete (every tautology is derivable).

Two ordered sets have the same *order type* when an order-preserving bijection links them; a *well-order* (every non-empty subset has a least element) has a unique ordinal as its order type, so being well-ordered and unbounded above does **not** make a set look like $\mathbb{N}$.

A poset is a set with a reflexive, antisymmetric, transitive order; under divisibility $x \preceq y \iff x \mid y$ the integers form a lattice where $\gcd$ is the meet and $\operatorname{lcm}$ is the join.

The rook polynomial counts non-attacking rook placements on a board with forbidden squares; its top coefficient is the permanent of the allowed-cell matrix.

Every nonzero ordinal is either a successor $S(\beta)=\beta\cup\{\beta\}=\beta+1$ (it has a largest element / immediate predecessor) or a limit ordinal (nonzero, no maximum, equal to the supremum of everything below it); $\omega$ is the first limit ordinal, while $\omega+1$ is a successor.

Collisions are resolved by chaining or open addressing; with load factor $\alpha = n/m$ kept $O(1)$, search costs expected $\Theta(1+\alpha) = O(1)$ under simple uniform hashing.

A linked list trades the array's $O(1)$ random access for $O(1)$ insert/delete at a known node, but pays $\Theta(n)$ to *search* — so binary search never applies, even on a sorted list.

Push $1\dots n$ in order and pop at will: the reachable output orders are exactly the 231-avoiding permutations, and there are $C_n = \binom{2n}{n}/(n+1)$ of them.

Trace BFS (queue) and DFS (stack/recursion) deterministically by breaking every tie in alphabetical order — and read off the first/last vertex visited.

Dijkstra finalizes vertices in increasing distance order; each time one is extracted, it relaxes all of that vertex's outgoing edges — so the edge-relaxation sequence is dictated by the extract-min order.

Find the order of the VALUE a loop prints — not its running time — by turning the nested loops into a closed-form sum or product and reading off its leading power.

Pairing geometric and arithmetic means makes one sequence climb and the other fall; AM–GM traps them between each other, so both converge to a shared limit.

The radius of a power series is $1/\limsup|c_n|^{1/n}$ — the root test that always works, even when the ratio test fails.

When an equation mixes $z$ with $\bar z$, $\mathrm{Re}(z)$, $\mathrm{Im}(z)$ or $|z|$, it is not a polynomial — write $z = x + iy$ and solve the real system.

If f is continuous and one-to-one on an interval, it must be strictly increasing or strictly decreasing — and then it maps the interval onto another interval of the same type.

Reflecting the variable across the midpoint of the interval leaves a definite integral unchanged; adding the original to the reflected copy often collapses a hopeless integrand into something trivial.

Any sequence built from a single geometric power rⁿ is decided by where r sits relative to ±1; for aₙ = rⁿ/(rⁿ+1) the limit is 0, ½, or 1 — after first checking the term is even defined.

When the unknown function sits both outside and inside an integral with a variable upper limit, differentiate both sides: the FTC turns the integral into a value of the integrand, collapsing the equation into a solvable ODE.

To find a root of a continuous function, take the supremum of the set where it is still negative — continuity squeezes the value there to exactly zero from both sides.

When a limit has a variable-limit integral $\int_0^x g(t)\,dt$ on top of a $0/0$ (or $\infty/\infty$) quotient, differentiate it with the FTC — its derivative is just $g(x)$ — and the integral disappears.

Replace each piece of a 0/0 quotient by its Maclaurin series, keep terms up to the first surviving power, and read the limit off the leading coefficients.

For continuous nonnegative f on a finite interval, the n-th-root of the integral of fⁿ converges to the maximum of f — so ∫fⁿ grows like (max f)ⁿ.

An equality of two distances in the complex plane is a 'set of equidistant points' — geometrically the perpendicular bisector of the segment joining the two centers.

On an interval the sign of f' gives whether f rises or falls and the sign of f'' gives whether f' rises or falls; a one-sided monotone-bounded f' has a finite limit that equals the one-sided derivative.