rec-4-12-2018

in life

Artificial Intelligence

Resolution

If li¬mjl_i \Leftrightarrow \neg m_j, then:

l1lk    m1mnl1li1li+1lkm1mj1mj+1mn\frac{l_1 \vee \cdots l_k \ \ \ \ m_1 \vee \cdots \vee m_n}{l_1 \vee \cdots \vee l_{i-1} \vee l_{i+1} \cdots \vee l_k \vee m_1 \vee \cdots \vee m_{j-1} \vee m_{j+1} \cdots \vee m_n}

If there is a empty clause after a resolution, it means there are conflicts.

p   ¬p\frac{p\ \ \ \neg p}{\square}

Resolution algorithm to prove α\alpha within KB:

  1. Generate CNF of the knowledge base KB¬αKB\wedge\neg\alpha
    • CNF: (l1,1l1,2l1,n1)(l2,1l2,n2)(lm,1lm,nm)(l_{1,1}\vee l_{1,2} \vee \cdots \vee l_{1,n_1}) \wedge (l_{2,1}\vee \cdots \vee l_{2,n_2})\vee\cdots \vee (l_{m,1}\vee\cdots\vee l_{m,n_m})
    • Also called k-CNF if n1=n2==nm=kn_1 = n_2 = \cdots = n_m = k
  2. Repeat resolution process for every new rule
    1. If there is no new rule, α\alpha cannot be proved.
    2. If there is an empty literal, then stop and α\alpha is proved

Complexity: exponential

Expressiveness: better (not restricted to Horn clauses)

Propositional logic

Jargons

Use functions, predicates to represent relationships:

  • A is a person -> Person(A)Person(A), Person: predicate
  • Person a has a crippled left leg -> Crippled(LeftLegOf(a))Crippled(LeftLegOf(a)), LeftLegOf: function (it’s OK since a human has only one left leg) Formally,

Term ::= Function ( Term {, Term}* ) AtomicSentence ::= predicate ( Term {, Term}* ) …

Model

Forgot that.

Networking

Cisco’s proprietary software, packettracer, couldn’t be downloaded without enrolling in its network course.

IOS

  • use enable to enable the thing
  • show interfaces to have a look at all interfaces, show interface [interface].
  • show vlan to show vlan
  • configure terminal to open the configuration in terminal
  • (config) interface [interface] to select an interface

Dynamic Trunking Protocol

A proprietary protocol invented by Cisco to negotiate trunking on a link between two VLAN-aware switches.

There is several modes for it:

  • access: puts the ethernet port into non-trunking mode and negotiates to convert the link to a nontrunk one, disregarding the neigboring port
  • trunk: puts the ethernet port into trunking mode and negotiates to convert the link to a trunk one, disregarding the neigboring port
  • dynamic auto: willing to trunk, will be trunk if the neighboring port is dynamic desirable or trunk
  • dynamic desirable: actively willing to trunk
  • nonegotiate: disable DTP. No wonder, it is not compatible with dynamic modes.

Except nonegotiate, all modes are triggered by (config-if) switchport mode [mode]. Switch to no-negotiate mode using (config-if) switchport nonegotiate.

Use a no before the statement to do the opposite thing, like:

(config-if) no shutdown: set up the link (config-if) no switchport nonegotiate: turn on DTP

Computer Graphics

Blurring is often used in computer graphics, like, to create HDR(high dynamic range) bloom, depth of field or other post process effects.

HDR bloom: since the real-world camera cannot focus perfectly, so it will convolve the incoming image with an Airy disk. What about the Airy disk? Know what a spot of light looks like in our eyes? That would be one. A perfect lens with a circular aperture would make it because the diffraction of light.

This effect is not noticeable when it is not so bright. However, with more light we can see the blurred edge of the bright part of the image, taken by a camera. And computer graphics tries to reproduce the same effect by blurring.

You can think up an approach instantly: take the average of neighboring blocks, like below:

[1/91/91/91/91/91/91/91/91/9]\begin{bmatrix} 1/9&1/9&1/9 \\\\ 1/9&1/9&1/9 \\\\ 1/9&1/9&1/9 \\\\ \end{bmatrix}

By all means this is bad. It will seem block-ish.

A better one is Gaussian blur. It uses the Gaussian distribution as the weight of neighboring pixels to calculate the average, or more accurately, do the convolution. The weight matrix, like the one above, is called kernel.

A 3x3 Gaussian kernel is like:

[1/161/81/161/81/41/81/161/81/16]\begin{bmatrix} 1/16 & 1/8 & 1/16 \\\\ 1/8 & 1/4 & 1/8 \\\\ 1/16 & 1/8 & 1/16 \\\\ \end{bmatrix}

Some other kernels are here.

It also can be used before downsampling: Gaussian blur gets rid of the sharp edges in the image, thus after downsampling, it will free the image from aliasing like moire patterns. Aliasing happens because of the poor sampling makes different signals indistinguishable, and some high frequency signals might get in the way after sampling. So a low pass filter need to be applied before sampling.

Task: sample => downscale image Reason of problem: high freq. signal => ? Problem: aliasing => moire pattern Solution: low pass filter => blurring

And yes, Gaussian blur is also a low pass filter, with a Bode plot like a parabola. Possibly it seems obvious at first sight: Gaussian distribution has a factor ex2+y22σ2e^{-\frac{x^2+y^2}{2\sigma^2}}, which is stable through Fourier transforms.

We can calculate it out. Let’s put the basic calculus into practice.

eiωxex2+y22σ22πσ2 dxdy=e2σ2ω2e(x2σ2ωi)2+y22σ22πσ2 dxdy=e2σ2ω2\begin{aligned} &\iint e^{i\omega x}\cdot\frac{e^{-\frac{x^2+y^2}{2\sigma^2}}}{2\pi\sigma^2}\ dxdy\\ =&e^{-2\sigma^2\omega^2}\iint \frac{e^{-\frac{(x-2\sigma^2\omega i)^2+y^2}{2\sigma^2}}}{2\pi\sigma^2}\ dxdy\\ =&e^{-2\sigma^2\omega^2} \end{aligned}

So the amplification is:

dB=20loge2σ2ω2=40ln10σ2ω2\begin{aligned} dB&=20\log{e^{-2\sigma^2\omega^2}}\\ &=-\frac{40}{\ln 10}\cdot \sigma^2\omega^2 \end{aligned}

Perfect! It is a parabola after all.

Leave Kawase to the next day.

Misc

マシンガンでも壊せなくて キャタピラーでも潰せなくて

Comment and share

Notes for 4-10

in life

Database

PL/SQL

Anonymous and named PL/SQL block

  • Anonymous PL/SQL block
    • Need to compile every time
    • Not stored
  • Named PL/SQL block
    • Can be stored in DB

Stored Procedure

Grammar:

Procedure ::= CREATE [OR REPLACE] PROCEDURE ProcedureName '(' Parameters ')' (AS|IS) RETURN ReturnType DECLARE Declaration BEGIN Body END ';'
Parameters ::= Nothing | Parameter {, Parameter}
Parameter ::= ParameterName (IN|OUT|IN OUT) Type ':=' DefaultValue
  • Note:
    • In the parameter list, varchar cannot be specified with a length.
    • MySQL has no AS|IS in the procedure, and IN/OUT is put before the parameter name.
    • In MySQL ,one has to change the delimiter before defining a procedure or function.

Loop statement

  • for x in [Reverse] 1…20 loop … end loop;
  • while … loop … end loop; To escape from a loop:
  • exit when …;

Conditional statement

  • if … then … elseif … end if;

Cursor

  • Used to process a set of records. PL/SQL record variable can only store one record at a time.
  • Technically, it acts like an iterator, which means one cannot process multiple records at the same time(though we can store them as a whole).
  • In declaration, a cursor is declared with a SELECT statement, and we can use this cursor to access the data returned by that SELECT statement
  • A cursor is bind to one specific SELECT clause, that is, one cannot bind it to another SELECT statement
  • The SELECT statement is and only is executed when the cursor is OPENed(see below).
  • CLOSE the cursor to free the memory space. Synopsis:
  1. Declaration

cursor cursor_name is select statement;

  1. Open cursor

OPEN cursor_name;

  1. Get the data

FETCH cursor_name into variable;

  • The cursor will move forward, just like python’s next function do.
  1. Check if there is no more entry

IF NOT cursor_name%FOUND THEN …;

  1. Close the cursor

CLOSE cursor_name;

  1. For loop Unique to Oracle. No need to open, close, or fetch from a cursor.

FOR variable in cursor_name LOOP – do something to the variable END LOOP;

Artificial Intelligence

Knowledge base && Inferrence

* Truth table

* Brute force search

* Forward chaining
    * reliable
    * completeness
        * -> only have these two properties for the knowledge bases able to be expressed with Horn clauses
        * Horn clause: a disjunction of literals with at most one unnegated literal
            * E.g. {% katex %}
\neg x_1 \vee \neg x_2 \vee \cdots \vee x_n \vee u
{% endkatex %}

* Backward chaining
    * To prove q, with p->q now prove p
    * Avoid repeating by check if a clause is already proved or disproved

Misc

Panning derives from panorama.

4/11 Record

Programming Languages

Polymorphic Functions

  • Static: cost grows exponentially with parameters
  • Dynamic:
    • supply a tag when calling the function

Example: Overloading Equality

  1. Equality was overloaded as an operator
  2. Make type of equality fully polymorphic
  3. Make equality polymorphic in a limited way
    • (==) :: ''t -> ''t -> Bool, ''t is a type t with equality
    • will be a static error if t is not Eq type

Type Classes

  1. Merchanism in Haskell
  2. Dictionary-passing style implementation [ESOP1988]
    • Type class declaration – dictionary
    • Name of a type class method – label in the dictionary
    • Parametric overloading – passing the dictionary to the function
class Show a where
show :: a -> String

instance Show Bool where
show True = "True"
show False = "False"

print :: Show a => a -> IO ()
print x = putStrLn $ show x
type 'a show = {show: 'a -> string}
let show_bool : bool show =
{
show = function
| true -> "True"
| false -> "False"
}

let print : 'a show -> 'a -> unit =
fun {show=show} x -> print_endline (show x)

Smalltalk: subtyping

  • Object -> super class -> method table

  • If interface A contains all of interface B, then A objects can also be used as B objects

    • need to look up all instances(members) at runtime

Javascript has the same problem

  • v8 engine: hidden class
function Person(first_name, last_name) {
this.first_name = first_name;
this.last_name = last_name;
}

var potus = new Person('D.', 'Trump');
var potrf = new Person('V.', 'Putin');

Computer Architecture

Optimizing cache

Merging write cache

DRAM and SRAM

Misc

最低だ 最低だ 最低だ

Comment and share

  • page 1 of 1
Author's picture

NoirGif

A progamer.

(click me to see some )


Student(probably)