Laplace Transform and its Properties

The Laplace Transform

• The Laplace transform of a function f(t), defined for t ≥ 0, is the function F(s).
• F(s) is defined by the integral ∫[0 to ∞] e^(-st) f(t) dt, where s = σ + jω is a complex frequency parameter.

Region of Convergence (ROC)

• The Laplace transform exists when the defining integral converges.
• Convergence occurs when Re(s) > a for some real number a. The ROC is defined as Re(s) > a.

Properties of the Laplace Transform

• Linearity: ℒ{ af(t) + bg(t) } = aℒ{ f(t) } + bℒ{ g(t) }
• Time Scaling: ℒ{ f(at) } = (1/|a|) F(s/a)
• Time Shifting: ℒ{ f(t - a)u(t - a) } = e^(-as) F(s), where u(t) is the Heaviside step function.
• Shifting in the s-Domain: ℒ{ e^at f(t) } = F(s - a).
• Differentiation in the Time Domain
  • ℒ{ (d/dt) f(t) } = sF(s) - f(0)
  • ℒ{ (d^2/dt^2) f(t) } = s^2 F(s) - sf(0) - f'(0)
  • ℒ{ (d^n/dt^n) f(t) } = s^n F(s) - s^(n-1) f(0) - s^(n-2) f'(0) - ... - f^((n-1))*(0)
• Integration in the Time Domain: ℒ{ ∫[0 to t] f(τ) dτ } = F(s)/s
• Differentiation in the s-Domain
  • ℒ{ tf(t) } = - (d/ds) F(s)
  • ℒ{ t^n f(t) } = (-1)^n (d^n/ds^n) F(s)
• Convolution: ℒ{ (f * g )(t) } = F(s)G(s), where (f * g )(t) = ∫[0 to t] f(τ)g(t - τ) dτ.
• Initial Value Theorem: lim (t → 0) f(t) = lim (s → ∞) [sF(s)]
• Final Value Theorem: lim (t → ∞) f(t) = lim (s → 0) [sF(s)]

Common Laplace Transforms

• Unit Impulse f(t) = δ(t) transforms to F(s) = 1. ROC: All s
• Unit Step f(t) = u(t) transforms to F(s) = 1/s. ROC: Re(s) > 0
• Ramp f(t) = t transforms to F(s) = 1/s^2. ROC: Re(s) > 0
• Exponential f(t) = e^at transforms to F(s) = 1/(s - a). ROC: Re(s) > Re(a)
• Sine f(t) = sin(ωt) transforms to F(s) = ω/(s^2 + ω^2). ROC: Re(s) > 0
• Cosine f(t) = cos(ωt) transforms to F(s) = s/(s^2 + ω^2). ROC: Re(s) > 0
• Hyperbolic Sine f(t) = sinh(at) transforms to F(s) = a/(s^2 - a^2). ROC: Re(s) > |a|
• Hyperbolic Cosine f(t) = cosh(at) transforms to F(s) = s/(s^2 - a^2). ROC: Re(s) > |a|
• Damped Sine f(t) = e^(-at)sin(ωt) transforms to F(s) = ω/[(s + a)^2 + ω^2]. ROC: Re(s) > -a
• Damped Cosine f(t) = e^(-at)cos(ωt) transforms to F(s) = (s + a)/[(s + a)^2 + ω^2]. ROC: Re(s) > -a
• t to the power of n f(t) = t^n transforms to F(s) = n!/s^(n+1). ROC: Re(s) > 0

Vectores - Vector Addition: Graphical Method

• Vectors A and B are placed head to tail, retaining their magnitude, direction, and sense.
• The resultant vector R is obtained by joining the origin of the first vector to the end of the last vector.

Vectores - Vector Addition: Analytical Method

• Rectangular components of a vector:
  • A_x = A cos θ
  • A_y = A sin θ
• Vector addition using components:
  • R_x = A_x + B_x + ...
  • R_y = A_y + B_y + ...
  • R = √(R_x^2 + R_y^2)
  • θ = arctan(R_y / R_x)

Vectores - Vector Products

• Scalar (dot) product:
  • A · B = AB cos θ = A_x B_x + A_y B_y + A_z B_z
  • The result is a scalar.
• Vector (cross) product:
  • A × B = AB sin θ n̂
  • A × B = | î ĵ k̂ | | A_x A_y A_z | = (A_y B_z - A_z B_y)î + (A_z B_x - A_x B_z)ĵ + (A_x B_y - A_y B_x)k̂ | B_x B_y B_z |
  • The outcome is a vector, and the direction is perpendicular to the plane formed by A and B. It follows the right-hand rule.

Energy Bands and Charge Carriers in Semiconductors - Energy Bands

• Solutions to Schrödinger's equation in a crystal lattice can be expressed in an E vs. k diagram.
• Metals: The Fermi level lies within an allowed band, resulting in a partially filled band.
• Semiconductors: The Fermi level lies within a band gap separating a completely filled valence band and an empty conduction band.
• Insulators: The Fermi level lies within a band gap that is much larger than in semiconductors.

Energy Bands and Charge Carriers in Semiconductors - Intrinsic Semiconductor

• An intrinsic semiconductor is a perfect crystal with no impurities or defects.
• Silicon (Si) and Germanium (Ge) are Group IV elements with a diamond crystal structure, each atom bonded to four neighbors.
• At T = 0K, valence band states are full, and conduction band states are empty.
• At T > 0K, some electrons are thermally excited, creating electron-hole pairs; n = p = n_i, where n_i is the intrinsic carrier concentration.
• Intrinsic carrier concentration (n_i) increases exponentially with temperature.
• Fermi level (E_F) lies near the middle of the band gap (E_g).
• Mathematical Expression
  • ni​=√Nc​Nv​ ​e−Eg​/2kT
  • N_c is the effective density of states in the conduction band.
  • N_v is the effective density of states in the valence band.
  • E_g is the band gap energy.
  • k is Boltzmann's constant.
  • T is the Kelvin temperature.

Energy Bands and Charge Carriers in Semiconductors - Extrinsic Semiconductor

• Doping is intentionally adding impurities to control electrical properties.
• n-type Semiconductor: Doped with donor impurities (e.g., Phosphorus in Silicon) leading to n > n_i, and E_F closer to , and .
• p-type Semiconductor: Doped with acceptor impurities (e.g., Boron in Silicon) leading to p > n_i , and E_F closer to E_v​.
• Compensation: Occurs when both donor and acceptor impurities are present in the same material; the conductivity type depends on the higher concentration.

Energy Bands and Charge Carriers in Semiconductors - Carrier Transport Phenomena

• Drift: Motion of charge carriers in response to an electric field.
  • J_drift = σE = q(nμ_n + pμ_p)E
    • σ: conductivity
    • E: electric field
    • q: elementary charge
    • n and p: electron and hole concentrations
    • μ_n and μ_p: electron and hole mobilities
• Diffusion: Movement of charge carriers from high to low concentration regions.
  • J_diffusion = qD_n (dn/dx) − qD_p (dp/dx)
    • D_n and D_p are the electron and hole diffusion coefficients.
    • dn/dx and dp/dx are the electron and hole concentration gradients.
• Einstein Relation:
  • D_n/μ_n = D_p/μ_p = kT/q
    • k: Boltzmann's constant, T: temperature in Kelvin, q: elementary charge

Algorithmic Complexity - What?

• Quantifies the amount of resources an algorithm needs.
• Compares the efficiency of algorithms.
• Predicts how an algorithm scales with input size.

Algorithmic Complexity - Why?

• To choose the right algorithm for a task.
• For code optimization.
• To understand the limits of computation.

Algorithmic Complexity - How?

• Choose a model of computation
• Define input size, n
• Count number of operations as a function of n
• Express complexity using Big-O notation

Algorithmic Complexity - Models of Computation

• Turing Machine is a theoretical model using symbols on tape.
• Random Access Machine (RAM) is a practical model allowing random access to memory.
• Word RAM is a RAM model with memory divided into fixed size words.
• Real RAM is a RAM model allowing real numbers in memory.

Algorithmic Complexity - Big-O Notation

• f(n) = O(g(n)) means there exist constants c > 0 and n_0 > 0 such that f(n) ≤ cg(n) for all n ≥ n_0. Also $n^2 + n = O(n^2)$, $100n = O(n)$ and $log(n) = O(n)$.
• f(n) grows no faster than g(n) as n approaches infinity.
• Common complexities
  • Constant is O(1)
  • Logarithmic is O(log n)
  • Linear is O(n)
  • Log-Linear is O(n log n)
  • Quadratic is O(n^2)
  • Cubic is O(n^3)
  • Exponential is O(2^n)

Simplifying Big-O Expressions

• Drop lower order terms, so $n^2 + n → n^2$
• Ignore constant factors, so $100n → n$
• $O(n^2 + n) \rightarrow O(n^2)$
• $O(log_a n) = O(log_b n)$

Algorithmic Complexity - Example: Searching

• Linear Search: $O(n)$
• Binary Search: $O(log n)$

Algorithmic Complexity - Example: Sorting

• Bubble Sort: $O(n^2)$
• Merge Sort: $O(n log n)$

Caveats

• Big-O describes asymptotic algorithm behavior.
• Constant factors are important in practice.
• Big-O doesn't tell you real running time of algorithms.
• Worst-case vs. average-case analysis.

Algorithmic Game Theory - What is Game Theory

• Mathematical models study of strategic interaction among rational agents
• Cooperative: focuses on groups forming coalitions
• Non cooperative: focuses on induvial players and their strategies

Algorithmic Game Theory - Normal-Form Games

• Games are are described via a payoff matrix
• A normal-form game is a tuple (N, A, u), where:
  • N is a finite set of n players, indexed by i
  • A = A_1 × … × A_n, where A_i is a finite set of actions available to player i. Each a = (a_1, …, a_n) ∈ A is an action profile
  • u = (u_1, …, u_n), where u_i : A ↦ ℝ is a real-valued utility function for player i. u_i(a) specifies the payoff to player i when the action profile is a.

Algorithmic Game Theory - Example: Prisoner's Dilemma

• Two suspects are arrested and charged with a crime. The police lack sufficient evidence to convict them, unless at least one confesses. The police tell each suspect separately that if he confesses and the other does not, he will be freed and the other will be jailed for 3 years. If both confess, they will both be jailed for 2 years. If neither confesses, they will both be jailed for 1 year.
• N = {1, 2}
• A_i = {Cooperate, Defect}, for i ∈ N

Game Representation

Algorithmic Game Theory - Strategies

• Pure Strategy: A pure strategy for player i is simply an action a_i ∈ A_i.
• Mixed Strategy: A mixed strategy for player i is a probability distribution over A_i.
  • S_i denotes the set of all possible mixed strategies for player i.
  • s_i(a_i) is the probability of playing action a_i ∈ A_i under mixed strategy s_i.
• Strategy Profile: A strategy profile is a tuple s = (s_1, …, s_n), where s_i ∈ S_i is a mixed strategy for player i.
  • S = S_1 × … × S_n denotes the set of all strategy profiles.

Algorithmic Game Theory - Expected Utility

The expected utility of player i under strategy profile s is:

• u_i(s) = Σ(a∈A) u_i(a) ∏(j∈N) s_j(a_j)

Algorithmic Game Theory - Nash Equilibrium

A strategy profile s* ∈ S is a Nash Equilibrium if, for every player i ∈ N and every strategy s_i ∈ S_i:

• u_i(s*_i, s*_-i) ≥ u_i(s_i, s*_-i)
• s*-i​ denotes the strategies of all players except i.

Algorithmic Game Theory - Interpretation

• No player has an incentive to unilaterally deviate from their strategy in a Nash Equilibrium.
• The only Nash Equilibrium is (Defect, Defect)

Algorithmic Game Theory - Existence of Nash Equilibrium

Every normal-form game with a finite number of players and actions has at least one Nash Equilibrium (possibly in mixed strategies).

Systèmes d'équations linéaires - Introduction

• Systèmes d'équations linéaires is a set of forms such as -$a_{11} x_1 + a_{12} x_2 +…+ a_{1n} x_n = b_1$ -$a_{21} x_1 + a_{22} x_2 +…+ a_{2n} x_n = b_2$
  • … -$a_{m1} x_1 + a_{m2} x_2 +… + a_{mn} x_n = b_m$ -$x_1, x_2,…, x_n$ are unknowns, $a_{ij}$ are the coefficients, and $b_i$ are constant terms.
  • Une solution d'un système d'équations linéaires is a set of values for unknowns which satisfy all the equations in the system simultaneously. For example: $x - y = 1$ and $x + y = 3$. Then the solution is $x = 2, y = 1$.

Systèmes d'équations linéaires - Méthodes de résolution

• Substitution: express an unknown in terms of others
• Élimination: Combine equations to eliminate an unknown.
• Méthode de Gauss: Transform to equivalent system form, then resolve the system.

Systèmes d'équations linéaires - Matrices et systèmes linéaires

A system of linear equations can be represented in matrix form as

• Ax = b
• A is the coefficient matrix
• x is the vector of unknowns
• b is the constant terms
• For example: For the system x - y = 1 and x + y = 3, matrix form would be [1 −1 1 1] [xy] = [1 3]

Systèmes d'équations linéaires - Opérations élémentaires

Element row operations:

• Échanger deux lignes.
• Multiply a line by a non-zero scalar.
• Add a multiple from one line to another.
• These steps will not change set solutions.

Systèmes d'équations linéaires - Rang d'une matrice

Le rang d'une matriceis the number of non-zero lines in it. un système d'équations linéaires Ax = b has a if and only if le rang de A is equal to le rang de la matrice augmentée [A|b]\