preface

Video link address:

B23.tv /a33Kwq 【【 Computer Science 】 – Computer Science- b23.tv/a33Kwq 【【 Computer Science 】 – Computer Science- B23.TV /a33Kwq

Meaning of video

  • You get to see the big names in action, and you get to see the efforts of other people behind the scenes. It can be seen that the development of a technology requires the cooperation of human beings, and the crystallization of human wisdom has created today’s computer world.

  • Quickly understand the development history of computer and related technology

  • You can see the “constant abstraction” of ideas and technology as computers evolve

1. The early history of computers

  • The development history

    • Abacus → stepping calculator → difference machine → analysis machine → punch card tabulating machine. It was not until relay, vacuum tube and transistor that the modern computer era was truly entered.

2. Electronic computers

relay

The control circuit is a set of coils. When the coil is energized, it will produce magnetism. The magnetism will pull one end of the circuit over and the circuit will pass. Then control coil power, lose magnetism, one end of the circuit will automatically disconnect, why will disconnect? Because there is a spring, the magnetic force when the control coil is energized is greater than the resistance of the spring, and the spring will play a role in the loss of magnetic force.

Vacuum tubes

Under normal state, the vacuum in the bulb, the positive and negative poles of the bulb are disconnected, which is unable to be energized. However, when the control coil is energized, the coil heats up and the negative electrons are in an excited state, thus breaking down the vacuum and forming a loop.

Electronic computer

ENIAC electronic numerical integration computer

The transistor

  • Transistor is a solid semiconductor device (including diode, transistor, field effect tube, thyristor, sometimes especially bipolar device), with detection, rectification, amplification, switching, voltage regulator, signal modulation and other functions. As a variable current switch, the transistor can control the output current based on the input voltage. Different from ordinary mechanical switches (such as Relay and switch), transistors use electrical signals to control their own opening and closing, so the switching speed can be very fast, the switching speed in the laboratory can reach more than 100GHz.

  • The history of the transistor

    • Triode -> Point contact Transistors -> Bipolar and monopole transistors -> Silicon transistors -> Integrated Circuits -> MOSFET -> Microprocessor (CPU)

Boolean logic and logic gates

Logic gate

  • Boolean variables have values true and false. The operations in Boolean algebra are respectively not gates, and gates, or gates, and xor gates.

gate

Take the inverse operation. In normal state, the output is on. When the input side is energized true, the node is connected and the current is grounded. The output is false.

With the door

As shown, conditions A and B must both be true for the output to be true

Or gate

A or B, if one condition passes, the output is true

Xor gate

  • The xOR gate is a little more complicated, using an OR gate first. The result of the Xor gate is very similar to the result of the OR gate, except that the result is different if both are true. If the “or” gate is combined with an “and” gate, it will only be true if the “or” gate is both true. This property is borrowed, and then the result is strung together with a “not” gate. If the “or” gate is both true, it will become false.

4. The binary

  • Binary: At first the transistor was used to represent base 3, base 5. But binary has easy to distinguish, noise – resistant.

  • In a computer, all data is stored and computed using binary numbers (because computers use high and low levels to represent 1 and 0, respectively)

  • Binary addition and subtraction

  • Binary representation symbols: ASCII code, Unicode

  • ASCII uses a specified combination of 7 – or 8-bit binary numbers to represent 128 or 256 possible characters. Standard ASCII, also known as basic ASCII, uses seven binary digits (the remaining one binary digit is zero) to represent all upper and lower case letters, digits 0 through 9, punctuation marks, and special control characters used in American English.

  • **ASCII encoding: ** is used to represent The English language. It is represented by one byte, in which the first byte is specified as 0, and the other seven bits store data. A total of 128 characters can be represented.

  • ** Extended ASCII encoding: ** is used to represent more European characters, storing data in 8 bits, a total of 256 characters

  • **GBK/GB2312/GB18030: ** indicates Chinese characters. GBK/GB2312 indicates simplified Chinese, and GB18030 indicates traditional Chinese.

  • **Unicode encoding: ** Contains all characters in the world and is a character set.

  • **UTF-8: ** is one of the implementations of Unicode characters that use 1-4 characters to represent a symbol, varying the length of bytes depending on the symbol.

5. Algorithm logic unit

A half adder

Used to calculate the addition of two one-bit binaries, without regard to low carry.

The half-adder is used to calculate the sum of two single-bit binary numbers A and b, output sum (s) and carry (c). In multi-bit calculations, carry C is used as the addition of the next adjacent bit. A single half-adder results in 2c+s. The truth table, logical expression, Verilog description, and circuit diagram are shown below, respectively.

Truth table

Full adder

In the simulation of 1101+1001, it can be seen that there will be a carry. The carry and the original two numbers will be added together to calculate, so there will be at most three numbers added, while the half adder only has two numbers added, so we need a full adder that can handle the addition of three numbers. What are the characteristics of the total adder? Then add the sum bits of the result AB to the sum bits of C to obtain the final sum bits. What about the rounding bits? The carry X of the addition of AB, and then the carry Y of the addition of the first result to the addition of C, those two carry phases might be the final carry. Why? Actually two carry y is 0 + 0, 1, 0, 0 + 1 is well understood, XY phase or the result is 0,1,1 this is completely in line with, but the result of the 1 + 1 should not be 10? That would overflow, no, because you can’t carry 1+1, so you can work backwards, if X of A+B is 1, that means that both A and B have to be 1, and the sum of A+B has to be 0, 0+C, and no Y has to carry 1 whether C is 0 or 1. If ABC = 0 and ABC = 1, then 222=8, you will find that the result of the total adder is exactly the same.

Truth table

Floating point Numbers

Travelling wave carry adder

Form an 8bit adder, input A and B (8bit bit width), you can calculate the result, C0 bit add has carry, carry and C1 two numbers A1 and B1 add is three numbers add using the full adder, arranged in sequence, form an 8bit width adder, the final result can be seen, There will be a final carry, which will reflect the overflow case. The previous sum0-7 already has 8 bits.

ALU logical computing unit

  • The part of a computer that performs various arithmetical and logical operations. The basic operations of an arithmetic unit include four operations: addition, subtraction, multiplication and division; logical operations such as and, or, not, xor; and operations such as shift, comparison and transmission, also known as arithmetic logic unit (ALU). When the computer is running, the operations and types of operations of the arithmetic unit are determined by the controller. The data processed by the arithmetic unit comes from memory; The processed result data is usually returned to memory or temporarily stored in an arithmetic unit. A Data arithmetic unit deals with data, so the length of data and the representation method of computer data have A great impact on the performance of arithmetic unit.

  • Serial adder, only one full adder, data bit by bit serial into the adder for operation. If the operand is n bits long, the addition is done n times. The serial adder has the advantages of few components and low cost, but the operation speed is slow, and it is mostly used for some special arithmetic devices with low speed.

  • Parallel adder, which is made up of multiple full adder, its digits is the same as the word length of the machine, all data operations at the same time, although the operands of everyone is provided at the same time, but bit by bit carry produced by low operation will affect to the highest level, so the maximum operation time of parallel adder is mainly determined by the carry signal transmission time, The sum delay of each full adder itself is only a secondary factor.

    The carry expression is Gi is the carry function, Gi=AiBi; Pi is the carry transfer function,

    The carry of parallel adder is usually divided into serial carry and parallel carry.

    When n full adders are connected in series, they can add two n digits. This adder is called parallel adder of serial carry.

6. Registers & Memory

  • Layer by layer abstract encapsulation: logic gates -> latches -> 1. Registers (juxtaposed), 2.256-bit memory (matrix) -> small chunks of memory -> whole chunks of memory

  • The matrix compresses the amount of leads used

latch

How do we keep the information of A bit unchanged? The construction of this picture is to keep the information of 1 OR true unchanged. When AB is both 0 at the beginning and A enters 1, OUTPUT is also 1. So if A inputs 0 or 1, the OUTPUT doesn’t change.

How do we keep the information of A bit constant, the construction of this picture is to keep the information of tfalse constant, whether A inputs 0 or 1, the OUTPUT does not change.

When the reset is turned on to 1, it does not matter what the OUTPUT is set to. When reset to 0, it locks 1, but if reset to 0, SET to 1, OUTPUT will be 1, and then SET won’t work. You have to set the reset to one for this to work.

Door lock

If you try this circuit, the switch that allows the write line to determine whether the data input is valid or not. It’s just how did this circuit come up? Our goal is to build a circuit that can store data, input a value, and save it, starting with a simple 1bit. A value is entered and the circuit can store it. As you can see from the self-connected or gate and gate above, it’s easy to lock a value, but once you lock it, you can’t change it, and then you want to expand, put in a control first, and let it be controlled. The latch comes out. The operation of the latch is not easily understood by us. Then the lock came out. Such a step by step circuit, of course, there must be a lot of very familiar logic gate understanding, the design of this circuit is the embodiment of experience and creativity. Let me go over the flow of this lock again. For writing convenience, I set the data input end as A, and the allowed write end as B. Starting from the content in the figure, we set the B end as 1, and the result directly connected with the gate at the A end is the result output by the A end, and then through the or gate. Let’s just put in 1, ok, now let’s look at the gate below, since it goes through a no gate and becomes 0, and then through a no gate it must be 0, and then through a NO gate it becomes 1 again, so the input below the last gate is 1, the input above it is also 1, and the final output is 1. Now let’s change the input of A to 0. Again, the result of the upper and gate must be 0. The result of the lower and gate will be 1 after the gate of A passes through 0 and then the gate of A passes through 0 and then becomes 0. Now enter into 0, namely the B are not allowed to write, we will just 0 latches, can now put A side into 1 try change as A result, the B side is zero, will control up and down, even with the result of the door is 0, no matter what you A client-side input, so below 0 through the gate into 1, again at the end of the day and gate, the and gate output the final result of 0 or 1, It depends on the top input line, the top input line is from the gate, or the bottom line of the gate we have determined must be 0, and the result of that or the gate depends on the value that has been locked, and whatever is locked remains, so it is not allowed to write.

By understanding the logic of the circuit, we can achieve the results we want, and we don’t have to worry about the logic. We abstract it, a data input line, an allow write line, and a data output line. The lock is affected by data input only when the allow data write line is open, otherwise the lock remains locked.

register

A door lock is finished, but its data volume is obviously too small, only 1bit, expand it, put 8 side by side, use 1 line to control the 8 door lock allowed to write lines, 8 data lines send data, 8 data lines output data. When we open the control line, the input can be stored in this register. When the control line is closed, the input can’t affect the register. The register retains the previous data. In fact, the idea here is that our default experience is to have a data input and store it uniformly, for example, this register has 8 bits, so if I type in 10010011, I can store this value, yes, but it doesn’t, in fact, The locks in this row only store 1bit of information in a particular location of the data, because the contents of the sequence are indexed to different addresses. The following door lock matrix can be more intuitive to reflect this point.

Multiplexer

  • In electronics, the multiplexer or MUx capable of selecting and forwarding a signal from multiple analog or digital input signals, putting different selected signals into the same output line.

  • Reuse technologies may follow one of the following principles, such as TDM, FDM, CDM, or WDM. Reuse is also applied to software operations, such as the simultaneous flow of multithreaded information to a device or program.

In order to save cost in industry, we have to expand the memory, if the door lock is placed side by side according to the above, it will produce a lot of unnecessary overhead. For example, to make a 256bit register, 256+256+1=513 lines. Let’s think another way, arrange them into a matrix, 16*16, each door lock corresponds to a unique position, determined by the row number and column number.

In order to save cost in industry, we have to expand the memory, if the door lock is placed side by side according to the above, it will produce a lot of unnecessary overhead. For example, to make a 256bit register, 256+256+1=513 lines. Let’s think another way, arrange them into a matrix, 16*16, each door lock corresponds to a unique position, determined by the row number and column number.

The 1616 lines are connected to the multiplexer separately, and a 4bit of position information can determine which line to go, for example, 0010, that is line 2, row and column are the same principle, and then an 8bit of row and column information can control a lock in the 1616 matrix. The locks in this matrix actually correspond to addresses. So this matrix is going to be 16 plus 16 plus 1 plus 1 is 34, not a little bit.

The above door lock magnify, it can be seen that only when the row and column of the door lock are through, the door lock may take effect, such as this time so that you can read, and the row and column get with the door and again, the diode will pass the DATAOUT line will have the result of the door lock out, so as to read the data.

RAM

  • Random Access Memory (RAM), also known as main Memory, is an internal Memory that exchanges data directly with the CPU.

  • It can be read and written at any time (except when refreshed) and is fast, often serving as a temporary data storage medium for the operating system or other running programs.

  • RAM can write (store) or read (retrieve) information from any specified address at any time. The biggest difference between it and ROM is the data volatility, that is, once the power is off the stored data will be lost. RAM is used in computers and digital systems to temporarily store programs, data, and intermediate results.

256bit memory, by an 8bit address line, in fact, the address line can see the size of memory, 28=256, and then a data line, one allows writing line, one allows reading line. Very simple, but a memory like this is useless, it can only hold 1bit of information in a specified place.

We parallel 8 memory, address line unified management, such as 00100101 address, 8 memory are to the same address door lock, are the second row and column 5 address. Then we tied for the administration of eight memory data, determined the pecking order, this time to enter a number, can be 8 bit number, enter 01010001, for example, is respectively 0,1,0,1,0,0,0,1 respectively in the same address under,2,3,4,5,6,7,8 1 piece of memory, Of course, this allows the write line to open, and then when it reads, as long as the address is the original address, it reads the original value.

Let’s abstract it a little bit further, and this is our RAM, random access memory. By 8bit address, can access 8bit wide (8bit value) data, and then one read, one write line to control. If we want to increase the bit width, we add parallel memory blocks. If we want to increase the number of addresses, we increase the number of door lock matrices.

This is our common memory RAM, which can hold 8 million bits in a small space.

7. CPU

Analyze how the CPU operates instructions

As shown in the figure:

RAM is divided into ADDRESS and DATA

CPU code fetching phase

CPU decoding phase

Now we start to simulate running our CPU, prepare a RAM, remember that an 8-bit wide RAM will leave at least a set of 8 data lines, a set of address lines, then write lines and read lines. ABCD four registers, actually a 8 bit register just have introduced above, is composed of eight side by side door locks, 8 input thread that eight output line, 1 write enable thread control, of course we register here, will be more than one allowed to read thread, another eight root is abstracted into one input line, how to connect these lines, we don’t care about now. Ok, let’s start with the instruction address register. We’ll start with address 00000000, which will be indexed to Address0 in RAM (actually 16*16=256 address bits). We’ll get Address0, where the DATA is 00101110. As to what meaning is in fact the line design of CPU time is ok, we will differentiate instruction 4 | 4, four is the operation instruction before, after four is operating address. Get this string of DATA and then go to the instruction register, and then make instruction judgment by the instruction register.

Here we list the most basic four instructions, 0010 to load register A, 0001 to load register B,0100 to store the value of register A, 1000, add the values of registers.

Let’s look at the first instruction. 00101110, the first four digits 0010, is the instruction to load into register A. Load who? Load the data at address 1110, and the part of 1110 is connected to the ADDRESS line of RAM, which is multiplexed to open the door lock at the specified address, address 14. The part of 0010 will be judged by the command checking logic.

When the instruction is 0010, the logic gate group will output 1. When the logic group path passes, the instruction is 0010.

According to the logic judgment of the logic gate group, 0010 is laod-A, so the line of the logic gate group or the allowed read line of open RAM is connected to the read line instead of the write line. This is because 0010 is loaded as stipulated in the design of CPU, so 0010 should be connected to the read line. And the allowed write line connecting register A. The DATA of which address is read is determined by the address of 4-bit 1110 in the latter part, because the latter part 1110 is connected with the address line, the multiplexer only opens the door lock with RAM address 14, and the DATA OUTPUT of RAM is the DATA of this address, that is, the DATA of RAM is connected with the input line of ABCD. But only A’s write line is open, so RAM’s address 14 00000011 is stored in register A. In this way, the execution logic flow of each operation instruction is smooth. The other instructions are the same logic, only through the logic gate group judgment after the connection is different.

In this case, we know the control principle inside, the control unit into a whole well, further abstraction.

CPU execution phase

Next, the instruction is decoded by the control unit to check whether the circuit of the LOAD A instruction can open the RAM read line and pass the address 14.

  • Enable the allow write line of register A with the circuit that checks if the load A instruction.

  • The CPU is programmable and can be controlled by software.

  • Low-level commands

    • Such as ADD, SUB, HALT, JUMP

    • The underlying implementation of JUMP is to overwrite the instruction address register by overwriting the memory address of the last four bits of the instruction.

8. Instructions and procedures

  • Program = set of instructions

  • To extend the instruction set by increasing the address width or address length

Let’s do A few simple instructions for RAM, starting with addres0, loada-14, to load address 14 into register A, which is 11; Next loadB-15 loads address 15 data into register B; Next SUDB A, register A minus B goes into register A; If ALU FLAGS negative is true, jump to 5. Otherwise, skip to 2. If ALU FLAGS negative is true, jump to 5, then run JUMP2, jump to 2. Store the value of register A to address 13, finally terminating HALT. This sequence of instructions is really a program that computes the remainder of 11/5. So the CPU goes.

9. Advanced CPU design

The cache

  • The cache is the memory that can exchange data at high speed. It exchanges data with the CPU before the memory, so the speed is very fast.

  • L1 Cache is the CPU’s first level Cache. The capacity and structure of the built-in L1 cache have a great influence on THE performance of CPU. However, the cache memory is composed of static RAM and its structure is relatively complex. Under the condition that the area of CPU core is not too large, the capacity of L1 cache cannot be too large. The capacity of L1 cache is usually between 32 and 256KB.

  • L2Cache(level 2 cache) is the second layer of CPU cache, which has internal and external chips. The internal chip level 2 cache runs at the same rate as the main frequency, while the external level 2 cache runs at half the main frequency. The L2 cache size also affects CPU performance. The larger the size, the better. The L2 cache size of a desktop CPU ranges from 128KB to 2MB or higher, while the L2 cache size of a laptop, server, and workstation can range from 1MB to 3MB. The higher the speed, the more expensive the cache, so some computer systems have two or more levels of cache. Level 1 caches, which are immediately adjacent to memory, have the highest speed and the lowest volume, and level 2 caches are slightly larger and slower.

  • The working principle of cache is that when the CPU wants to read a data, it first looks up the data from the CPU cache, and immediately reads it and sends it to the CPU for processing. If the data is not found, it is read from the relatively slow memory and sent to the CPU for processing. At the same time, the data block in which the data resides is transferred to the cache, so that the future reading of the whole data block is carried out from the cache without the need to call the memory. It is this reading mechanism that makes the CPU read cache hit ratio very high (around 90% for most cpus), which means that 90% of the data to be read by the CPU next time is in the CPU cache and only about 10% needs to be read from memory. This saves the CPU a lot of time to read directly from memory, and makes it almost unnecessary for the CPU to read data. In general, the CPU reads data in the order of cache first and memory later.

Pipeline cycle

When pipelining technology is not adopted, the execution mode and execution cycle of instructions are as follows:

If you follow this process, it’s all done before you can execute the next one, which creates a lot of idle time.

The use of assembly line operation, can greatly save idle time.

  • Development: Execute multiple alUs simultaneously -> multi-core -> multiple cpus -> supercomputers

10. Early programming

  • The earliest programming: the loom, a single perforated card representing different patterns, the programmable loom could be spun according to the perforated card.

  • Use plugboard to store program, different plugboard means different program

  • The program is stored in memory, and the computer reads the program on punched cards and stores it in the program. The memory is easier to use than the plugboard, smaller and more reusable.

  • Use switches to store programs. Different switch combinations represent different instructions.

  • Programming in the early days (before 1980) was very professional and tedious

History of programming languages

Pseudo code

Evolution of instruction

Instructions by the start of the 00101000 such binary primitive expression, improve became instead of instruction in simple language, easy to remember and understand a lot, in the original binary instructions, want to jump from one address to another address, retrieve the address code is not very convenient, with the tag was good way to solve the problem, the position of jump And even if the data instruction is added dynamically, the original address is changed, but the position we want to identify is the label, so it will not be affected by the address change.

The compiler

  • A compiler is the process of converting binary to abstract language in reverse, from high-level language into machine code, which the CPU can directly recognize and run.

  • A compiler is a program that translates “one language (usually a high-level language)” into “another language (usually a low-level language).” The main workflow of a modern compiler: Source code → Preprocessor → Compiler → Object Code → Linker → executables

  • Working methods

    • First, the compiler does the parsing, which means separating out the strings.

    • Then semantic analysis is to clarify the meaning of each grammar unit analyzed by grammar analysis.

    • The final result is the object file, also known as the OBj file.

    • The final EXE file can be generated through the link of the linker.

    • Sometimes you need to link object files generated by multiple files to produce the final code. This process is called cross-linking.

A programming language

  • The combination of Unix system and C language

  • Abstract again: With programming languages, we don’t care about registers or memory locations, simply declare variables, and the compiler will translate this statement into all the instructions you need.

12. Programming languages – statements and functions

  • If statement

  • The while loop

  • function

  • Function calling function

13. Introduction to algorithms

  • Merge sort

  • Bubble sort

  • Selection sort

  • Insertion sort

  • Quick sort

14. Data structures

The complexity of the

Time complexity

Spatial complexity

An array of

  • Stored in contiguous space, so the memory address of each data can access the target data by subscript.

  • Adding and deleting data can be time-consuming

  • Time complexity of accessing data: O(1)

The list

  • Classification of the list

    • Singly linked list

    • Two-way linked list

    • Circular linked list

  • Data is generally stored in the memory separately. Therefore, if you want to access data, you have to start from the first data and follow the pointer to access data one by one.

  • Adding and removing is faster

  • The access time is order n.

The stack

  • The linear table

  • Fifo, or last in, first out, or FILO

  • Defines linear tables that only perform insert and delete operations at the end of the table

  • The bottom of the stack is fixed, while the top floats

  • A stack with zero elements is called an empty stack. An insert is commonly called a PUSH, and a delete is called a POP. A stack is also called a fifin-out table

  • Related terms

    • To the top of the stack

    • The stack is low

    • Push: The operation of putting elements from the top of the stack

    • Out of stack: Take out elements

The heap

  • A heap always satisfies the following properties:

    • The value of a node in the heap is always no greater than or less than its parent;

    • The heap is always a complete binary tree.

  • The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap. Common heap have binary heap, Fibonacci heap and so on.

The queue

  • The linear table

  • First in, first out, or FIFO

  • Queues can add elements at one end and take them out at the other

  • Related terms

    • Putting an element from one end is called queuing, and taking an element out is queuing.

Hash table

  • Hash table is the Key function is called by a fixed algorithm hash function converts an integer number, then you will be taking more than the number of array length, take as an array subscript under-pressure sieve analyzer, to store the value in the figure as the suffix array space, can make full use of the storage space array to find the advantages to look for the element, So it’s very fast.

  • Array structure after jdk8:

    • Array + linked list structure

    • Hashing conflicts need to be considered

Binary tree

  • Common binomial trees are: complete binomial trees, full binomial trees, balanced binomial trees, red black trees

  • B+ tree: Typically used in databases and file systems of operating systems. Contains root nodes, internal nodes, and leaf nodes.

figure

  • A graph consists of a finite set V of nodes and a set E of edges. In order to be different from tree structure, nodes are often called vertices in graph structure, edges are ordered pairs of vertices, and if there is an edge between two vertices, it means that the two vertices have adjacent relationship.

15. Alan Turing

Turing machine

An abstract machine with an infinite strip of paper divided into squares, each of which has a different color. There was a machine head moving on the tape. The machine head has an internal set of states and some fixed programs. At each moment, the machine head will read a grid information from the current paper tape, and then search the program table in combination with its own internal state, output information to the paper tape grid according to the program, and transform its own internal state, and then move.

Halting problem

Turing machine, it is not certain whether a calculation will execute the result and stop, “given the Turing machine description and input paper tape, is there an algorithm that can determine whether the machine will go on forever or stop at a certain point? The Turing machine proved that the shutdown problem could not be solved by clever logical contradictions. We illusion a Turing machine, give it the input tape and rules, the output Yes said it would stop, No output says it will not stop, the Turing machine called H, we have developed a new machine with H, if H says the program will “stop”, so the new machine will run (that is, will not stop), if the result of the H to No, representative will not stop, Essentially a machine that is the opposite of the H output, and we also need to put a separator in front of the machine, so that the machine only receives one input. What if you take the description of the new machine as its own input, and if H says Yes, it will stop, then the new machine will go on forever, and if H says No, it will stop. This paradoxical result proves that the downtime problem cannot be solved.

The tag on Turing’s body

  • The father of computer science

  • Proposed the concept of the Turing Test

  • Artificial intelligence thought

The fall of a scientific superstar

16. Software engineering

  • objectification

Integrated Circuits & Moore’s Law

lithography

The advancement of computer hardware went through several stages, from vacuum tubes to transistors to integrated circuits, and the photolithography was born in this environment. In fact, the whole photolithography process is layering, etching, cleaning, layering, etching, cleaning, and finally making integrated transistors. Sometimes it conducts electricity, sometimes it doesn’t. We can control the timing. How does this process happen? Starting from the bottom layer, wafer (silicon material), oxide layer, photoresist, photomask, photomask hollow out is designed circuit, exposed part, after light, can directly illuminate the photoresist, photoresist dissolve, put in a specific lotion, this part of the dissolved photoresist is removed. Then dissolve the oxide layer again with a substance that can dissolve the oxide layer and remove the exposed oxide layer. Note that the solution will only work on certain layers and will not corrode other layers of material. In the same process, the wafer is dissolved and doped with the dissolved parts, such as phosphorus that penetrates into the exposed silicon, changing the electrical properties and making the parts semi-conductive.

After melting the layer, repeat the above process with a new photomask. This time the pattern is different and a gap is opened above the doping region. Some of the silicon is then doped with another gas to convert it into another form.

Dissolve a specific area to reveal the prepared area.

Covered with a metal layer, the three regions of a transistor are formed, non-conductive, semi-conductive and conductive. Each region is doped differently. This is called a bipolar transistor.

We can focus the photomask to a very small area and produce very fine details.

18. Operating system

  • Operating System, short for OS.

  • It is also a software program that has special privileges to operate hardware and can run and manage other programs.

  • The operating system is generally the first program to start after boot, and all other programs are started by the operating system.

  • Operating systems provide apis to abstract hardware, called device drivers, through which programmers can standardize mechanisms to interact with input/output hardware I/O. If a programmer calls print, the operating system handles the details typed to the paper.

  • The first supercomputer, Altas, was developed by a machine that processed data quickly and wanted to make the most of it. So the operating system can batch, load programs automatically, and run several programs simultaneously on a single CPU.

  • Virtual memory

    • CPU can multi-task processing, each program will occupy memory, cut to another can not lose data, so, how to deal with?

    • Allocate a dedicated block of memory to each program.

    • Real memory can be allocated in dozens of places, and lists can be in a bunch of discrete chunks.

    • To hide this complexity, operating systems virtualize memory addresses. It can be assumed that memory always starts at address 0. But in reality, it is hidden and abstracted by the operating system.

    • The operating system automatically handles the mapping between virtual memory and physical memory.

    • This mechanism of virtual memory makes the memory size of the program can be flexibly increased or decreased, that is, dynamic memory allocation.

    • It is more flexible to allocate dedicated memory areas to programs and run multiple programs at the same time, which is better isolated. If a program goes wrong, it will only mess up its own memory and will not affect other programs. This is called memory protection. Isolation can also be used.

    • Supplement knowledge

      • Virtual Memory is also called Virtual Memory. All the programs running in a computer need to be executed through memory. If the program that is executed takes up a lot of memory, it will run out of memory. To solve this problem, Windows uses virtual memory technology, which sets aside a portion of hard disk space for memory use.

      • When it runs out of memory, the computer automatically calls on its hard drive to act as memory to relieve the strain. When a computer doesn’t have enough RAM to run a program or operation, Windows compensates with virtual memory. It combines the computer’s RAM with temporary space on the hard disk. When RAM is slow, it moves data from RAM into a space called a paging file. Moving the data into a paging file frees up RAM so that work can be done. In general, the more RAM a computer has, the faster its programs run. If your computer’s speed slows down due to lack of available RAM space, try to compensate by adding virtual memory. However, computers can read data from RAM at a faster rate than from a hard disk, so expanded RAM capacity (with memory sticks) is the best choice. [2]

  • Development: multi-tasking, multi-user

  • Time-sharing operating system

    • Time-sharing operating system is a kind of operating system that makes a computer serve several, dozens or even hundreds of users at the same time by means of time slice rotation.

    • The computer is connected with many end users, and the time-sharing operating system transfers the system processor time and memory space to each end user’s program at a certain time interval in turn. Because of the short time interval, each user feels as if he owns the computer. The characteristic of time-sharing operating system is that it can increase the utilization rate of resources effectively. UNIX systems, for example, use deprivation-first dynamic CPU scheduling to support time-sharing operations.

    • Time slice: The system resources (especially THE CPU time) of a computer are divided into time slices. Each time segment is called a time slice, and each user uses the time slice in turn.

    • Time-sharing technology: the processor’s running time is divided into very short time slices and the processor is assigned to each online job in turn.

    • Typical examples of time-sharing operating systems are the Unix and Linux operating systems. It can connect to multiple terminals at the same time and rescan the process every once in a while, reallocate the priority of the process, and dynamically allocate system resources.

  • The Unix system

    • Core functions: such as memory management, multitasking and input/output processing, are called the kernel.

    • A bunch of useful tools: but it’s not part of the kernel (like programs and runtime libraries)

    • In 1969, Ken Thompson of Bell LABS wrote a set of kernel programs, some kernel tools, and a small file system in assembly language. This system was a prototype of UNIX, known as Unics (UNIX did not yet exist). This filesystem has two important concepts:

      All programs or system devices are files

      Whether you build an editor or a satellite file, you write a program that has only one goal: to accomplish that goal effectively

Memory & Storage media

A storage medium

A storage medium is used to record information. The following content contains the expansion content:

Punch cards and punch tape

Basile Bouchon invented the punch card (punch card) in 1725. He punched holes in paper to store patterns and used them to control the weaving of patterns on a loom. In 1801, Joseph Marie Jacquard used Punched cards in a Jacquard loom by bundling them together in sequence, which was the prototype of Punched paper Tape (Punched Tape). Alexander Bain used perforated paper tape to send telegrams in 1846. In 1890, Herman Hollerith invented the punch card tabulating machine for collecting and counting census data, marking the beginning of the era of semi-automated data processing systems. Not only did the machines do statistics faster, but they were able to understand information in new ways, quickly finding their way into every industry. In 1896 Herman Hollerith founded the Tabulating Machine Company, the forerunner of what became known as IBM. Punch cards and paper tape continued to be used until the 1980s, for more than two centuries.

Delay line memory sequential access

Fill a tube with a liquid, such as mercury, and place a speaker at one end of the tube and a microphone at the other. When the speaker emits a pulse, it creates a pressure wave. The pressure wave takes time to travel to a microphone at the other end, which converts the pressure wave back into an electrical signal.

The principle of the delay line memory is to store data by using the propagation delay of pressure waves. 支那

There’s a pressure wave representing a 1, there’s no pressure wave representing a 0. An internal circuit connects the microphone and speaker, and amplifiers compensate for signal weakness, thus realizing a cycle of storing data.

There’s a pressure wave representing a 1, there’s no pressure wave representing a 0. An internal circuit connects the microphone and speaker, and amplifiers compensate for signal weakness, thus realizing a cycle of storing data.

Core memory

Audio tape, which can store analog signals.

The principle is: magnetic field lines are changed with the change of audio current, so the degree of magnetization of each tape in the process of moving also changes with the strength of the audio signal current, so that the sound can be recorded on the tape. The use of magnetic tape in computers began in 1951.

A magnetic core can be magnetized in one direction by winding a wire and applying an electric current. If the current is turned off, the core remains magnetized. If a current is applied in the opposite direction, the direction of magnetization (polarity) is reversed, so that it can be used to distinguish between storing 1s and 0s.

By arranging cores in a grid, wires are used to select rows and columns, and wires run through each core to read and write a bit.

tape

A magnetic tape is a long, thin, flexible strip of magnetic tape wound on a shaft. The tape can be moved back and forth in a “tape drive” with a “write head” around the wire. A magnetic field is generated by an electric current that magnetizes a small part of the tape.

Since tape is a sequential access device, it is particularly suitable for traditional storage and backup and sequential reading and writing of large amounts of data. However, due to its slow speed and large size, it is mainly used for commercial backup.

Cheaper, but disks are continuous and must be rewound or fast-forward to a particular location.

Drum memory, a precursor of hard disk drives (HDDS)

It consists of a large metal cylinder coated with a ferromagnetic recording material. It was widely used in computer memory before the advent of core memory. It is also used for secondary storage and is considered a precursor to hard disk drives (HDDS). Like hard drives, drums have heads, but instead of looking for data, drums have lots of static heads and just wait for the right fan to rotate into place. Tauschek’s original drum memory had a capacity of about 500,000 bits (62.5 kilobytes).

disk

This is the prototype of the modern hard disk, in which the magnetic head is suspended above the high-speed disk without direct contact.

The advantage of hard disks is that they are thin and can be stacked on top of each other, providing more surface area for storing data.

Read-only Optical disk storage (CD-ROM)

Dynamic random access memory DRAM

Today, DRAM is still the most commonly used random access device (RAM), used as memory (or main memory) in personal computers and workstations. DRAM memory can come out, mainly based on semiconductor transistor and integrated circuit technology.

Floppy Disk

For nearly three decades, from 1971 until the 1990s, floppy disks were used to store and exchange data.

Flash memory

DAT (Digital Audio Tape)

Digital Multipurpose CD-ROM DVD (Floppy Disk)

USB Flash drive

Secure Digital Memory Card (SD) Secure Digital Memory Card

Professional term

Seek time

Average seek time refers to the average time it takes for the magnetic head to move to the track where the data is located after the MO disk receives the system instruction. It refers to the time it takes for the computer to issue an addressing command and the corresponding target data to be found, in milliseconds (ms). Refers to the time required for the head to move to the track where the data is located. In different head scheduling algorithms, there are different seek times

Files and file systems

  • A file is a long string of binaries at the bottom.

  • Storage is no file concept, just store a lot of bits. So in order to store multiple files, you need a special file that keeps track of the locations of other files, and this special file has a lot of names, but it’s called a directory file.

  • This file is often present at the beginning for easy lookup.

  • Directory files that store the names, creation time, type, modification time, size, and so on of all other files.

  • To prevent several files from overwriting the following, so:

    • Divide the space into Blocks: So that there is some space reserved, directory files record which Blocks the files are in.

    • Split file: Store files in multiple blocks. If the file is too large, it will find an unused block to use. So directory files don’t record just one block.

    Files can easily grow and shrink as long as blocks are allocated.

  • Virtual memory is what makes an application think it has contiguous available memory (a contiguous complete address space), when in reality it is usually divided into multiple physical memory fragments, with portions temporarily stored on external disk memory for data exchange as needed. At present, most operating systems use virtual memory, such as “virtual memory” in the Windows family; Linux swap space, etc.

  • If you want to delete a file, simply delete the record of the directory file to make a space available. At some point later, those blocks are overwritten with new data, but until then the data is still there. So computers can recover data.

  • Pieces:

    • For example, when adding text data, the operating system allocates a new block to it. The data will be divided into three blocks, separated and out of order. This is called a shard.

    • Fragmentation is caused by adding/deleting files and is inevitable.

    • On disk, fragmentation is bad, such as reading block 1, fast-forwarding to block 5, and then reverting to block 3.

    • Large files may be in multiple blocks and open slowly? Defragmentable. That’s moving the data back and forth, putting it in the right order.

  • Hierarchical file system

    • Currently files are made up of folders and files.

    • Directory files point not only to files, but also to directories. Then, additional metadata is needed to distinguish files from directories.

    • The directory files are at the top level, the root directory, where all the files and folders are.

    • For example, if you move a file, you do not need to move any data blocks. You only need to change two directory files, one is the record of deleting the original directory file, the other is the record of adding a new directory file.

    • Metadata, also known as intermediary data or relay data, is used to describe data property information, which is used to indicate storage location, historical data, resource search, and file recording. Metadata is a kind of electronic catalogue. In order to achieve the purpose of cataloguing, it is necessary to describe and collect the content or characteristics of data, so as to achieve the purpose of assisting data retrieval

21. The compression

  • Same as data content compression

    • In a document, some data are repeated, such as 7 consecutive yellow, we do not need to write the yellow seven times (255,255,0), we only need to write the yellow once, and then write the number of repeat 7 in front, can accurately represent the data, the data size is also compressed. Of course, some of our cases are not repeated, in order to avoid computer retrieval can not distinguish which is repeated and which is not repeated, we add the repetition times in front of all the color blocks, do not repeat is.

  • The dictionary compression

    • We divided the color blocks in pairs into different types of color blocks, and then summarized the number of different color blocks and recorded their frequency, such as WY yellow and white twice, YY yellow and yellow four times

    • All the different color block combinations are listed, namely YY4,WY2,BY1 and WW1. We select the two combinations with the least frequency and combine them into branches under a root. Then, the combined node and the remaining combinations are combined into branches under a node, and the process repeats until the combination is complete. As shown in the left side of the picture, we give all branches a value of 0 on the left and 1 on the right, so there will be YY code 0, WY code 10, BY code 110 and WW code 11. Note that all of these color block combinations are coded identically and do not have the same prefix.

    • At this point, the color block is represented by code 10110000111100, which is only 14 bits in total. Unfortunately, this is not enough. We need to add the information of the dictionary color block code, otherwise this column of data is meaningless.

    • After adding the dictionary information, the total is 30 bytes, which is much better than 48 bytes, and the later compression efficiency will amortize the boundary cost of the dictionary as the data volume increases.

22. Cli interface

  • Early development: Computers, controls with gears, knobs, plugboards, switches, will be more difficult to accept and operate.

  • For example, enter PWD: to print the working directory, hostname: to list the computer name on the network, and ls: to list the contents of the directory

23. Screen &2D graphics display

  • Cathode ray tube: CRT vector mode

    • How it works: Electrons are fired at a phosphorescent coated screen and glow for a fraction of a second when they hit the coating. Since electrons are charged particles, the path can be controlled using a magnetic field. Inside the screen, boards or coils guide electrons to desired positions, up, down, left, and right.

    • With this control, there are two ways to draw a graph:

      • Guiding the electron beam to trace the shape is called vector scanning. Because the glow only lasts for a moment, if you repeat it fast enough, you can get a clear image.

      • Take a fixed path, line by line. Top to bottom, left to right, repeat. The electron beam is turned on only at certain points to draw the graph. This is called raster scanning. In this way, graphics and even text can be drawn with many small line segments.

  • Liquid crystal display

    • As technology developed, it was finally possible to display sharp dots, called pixels, on a screen. Liquid crystal display, or LCD for short.

    • LCDS also use raster scans, updating the red, green and blue colors of the pixels multiple times per second.

    • When computers first developed they didn’t have pixel values, not because they couldn’t do it, but symbols because they took up too much memory.

  • Character generator:

    • To save memory, there’s no way to draw any shapes.

    • Characters are read from memory and converted into raster images so they can be displayed on the screen.

  • Drawing board

The Cold War and consumerism

  • The military and technological competition between the United States and the former Soviet Union caused the United States to pour huge resources into the computer field, resulting in the birth of many technologies.

    • Government money, such as that invested by the United States during the Cold War, fueled the early development of computers.

  • Consumers drive the computer business

The personal computer revolution

  • The birth of a tiny computer

    • Single-chip CPU: powerful + small + cheap

    • Advances in integrated circuits also provide low-cost solid-state memory, which can be used with ROM and RAM and can fit an entire computer onto a single circuit board

    • Inexpensive and reliable storage media such as magnetic tape and floppy disks

    • Low cost display

26. Graphical user interface

  • The mouse

  • GUI programs: event-driven programming

  • User interface: The code is linked to events and is triggered each time a button is clicked.

27.3 D graphics

28. Computer networks

The development history

Facilitating the exchange of information within a company, faster and more reliable than sending paper cards or tapes to another building, is the Sneaker network. Sharing resources, these parts of the network were interlinked, making up the early local area networks.

In the local area network (LAN) a computer is how to communicate, they through the optical fiber, two hexadecimal signals, header information contains the MAC address, of the journey to the MAC address of each computer is unique, so the computer receives signals under the same network, parsing header information, see the MAC address of the receiver, You can decide whether to accept the message or not. This is convenient, but as there are more and more computers in the same network, there are more and more computers to send messages and more and more computers to receive messages. It is very likely that signals will be sent at the same time, hence the following gateway.

A piece of computer is divided into a region with frequent interaction, and each region is connected with an exchange. When information in its own region does not need to be switched on, even computers in another region are also sending information in the same region and will not be affected unless they want to communicate across regions.

Of course it can’t solve every problem, and a very important index in the network communication retreat mechanism, that is to say when a few computer wants to send signals, check to see if the network has been signaled in occupancy, if any, just wait for a period of time again to send, such as 1 second, again hair, then to detect the network being used again, if you are waiting for a period of time, After 2 seconds, check whether the network is occupied. If the network is occupied, wait 4 seconds. In this way, the exponential waiting time can avoid network conflict to a great extent. The starting time of 1 second is not fixed, it is a random number, for example, if everyone’s starting time is 1 second, it will still conflict.

The router

In real life, network connections are not point-to-point, which is often expensive, but node connections, which may take several network paths and nodes to get from one city to another. Of course, when the message is sent, it contains the information of the target to go to, and then a node (router) will allocate a shorter and less crowded path to arrive according to the target.

When the content of a message is too large to send all at once, the data is broken up into subpackages, which are tagged and sent to the same destination, assembled and parsed in the destination network protocol.

In the early days of networks, networks were not mysterious, they were pipes that connected computers, and those pipes might break, they would be disconnected from the computers at the other end of the pipe, but the computers at the other end of the pipe could still communicate with each other.

29. The Internet

The network connection

LAN: Local Area Network

Computers are first connected to a local area network.

The WIFI router connects all the devices to a local area network (LAN).

WAN: Wide Area Network

The LAN connects to the WAN. Half of the routers in the WAN belong to Internet service providers, or ISPs.

Comcast, AT&T and Zion.

In a wan, you connect to a local router that might cover a city block,

It is then connected to a larger WAN, possibly covering the entire city.

Maybe a few more hops, but eventually we’ll reach the backbone of the Internet.

The backbone of the Internet consists of a group of super-large, super-bandwidth routers.

To transmit data

For example, to obtain the video from YouTube, the data packet must first go to the Internet trunk and then arrive at the YouTube server with the corresponding video file along the trunk.

The packet jumps from your computer to your YouTube server, maybe 10 times.

For example, run the traceroute command to jump to Baidu from the local computer

traceroute www.baidu.com traceroute: Warning: www.baidu.com has multiple addresses; Using 14.215.177.38 traceroute to www.a.shifen.com (14.215.177.38), 64 hops Max, 52 Byte packets 1 171.11.56.1 (171.11.56.1) 2.996 ms 2.658 ms 2.933 ms 2 * * * 3 211.95.4.153 (211.95.4.153) 38.653 ms 3.760ms 3.479 ms 4 139.226.210.109 (139.226.210.109) 4.518 ms 4.461 ms 139.226.213.233 (139.226.213.233) 29.087 ms 5 139.226.225.137 (139.226.225.137) 5.915 ms 139.226.210.61 (139.226.210.61) 8.987 ms 139.226.225.137 (139.226.225.137) 4.781 ms 6 219.158.6.214 (219.158.6.214) 30.717 ms 33.009 ms 31.772 ms 7 * 219.158.24.18 (219.158.24.18) 42.654 ms 40.014 ms 8 * * * 9 202.97.95.101 (202.97.95.101) 59.009 ms * * 10 113.96.5.134 (113.96.5.134) 32.778 ms * * 11 86.96.135.219.broad.fs.gd.dynamic.163data.com.cn (219.135.96.86) 62.037 ms 113.96.4.205 (113.96.4.205) 33.260 ms 86.96.135.219.broad.fs.gd.dynamic.163data.com.cn (219.135.96.86) 33.472 ms 12 14.29.121.186 (14.29.121.186) 34.641 ms 86.96.135.219.broad.fs.gd.dynamic.163data.com.cn (219.135.96.86) 33.889 ms 14.29.121.178 (14.29.121.178) 35.248 ms 13 14.215.32.110 (14.215.32.110) 34.939 ms * *Copy the code

IP protocol – Internet Protocol

If the data is large, it is broken up into smaller packets rather than being sent as a whole file.

Packets are sent over the Internet and comply with the Internet Protocol standard, or IP.

IP is a low-level protocol. The header of a packet contains only the target address, and the header stores data about the data, also called metadata.

You don’t know which program to hand in at this layer.

UDP protocol – User datagram protocol

The UDP header precedes the data and contains useful information. For example, each program that wants to access the network must apply for a port number from the operating system.

When a packet arrives, the receiver’s operating system reads the UDP header, reads the port number inside it, and then goes to the corresponding program.

IP is responsible for sending packets to the right computer, UDP is responsible for sending packets to the right program.

UDP does not provide a mechanism for data repair or retransmission.

When the receiver learns that the data is corrupted, it usually just throws it away. And UDP has no way of knowing if the packet has arrived.

Scenarios such as video calls. Not applicable: text transfer.

Check and – Checksum

There is checksum inside the head, used to check whether the data is correct, check the way is to sum the data to compare, will receive the data together, and the head checksum comparison, if consistent, it means normal, inconsistent that there is a problem with the data. UDP does not provide a data repair duplication mechanism.

TCP – Transmission control protocol

Three handshakes: I’m going to send you the data you’re ready (1), ok, I’m ready (2), ok, I know you’re ready (3). ···· Start sending data.

Four waves: The client sends a FIN segment with its current serial number k. that it wants the recipient to see. It also contains an ACK to confirm the latest data sent by the other party. (1), the server will add K value plus 1 as the ACK serial number value, indicating that the last packet has been received. The upper application is notified that the other end initiated a shutdown, which usually causes the application to initiate its own shutdown. (2), the server initiates its own FIN segment, ACK=K+1, Seq=L (3), and the client confirms. ACK = L + 1 (4).

DNS- Domain name system

Because IP address is not easy to remember and cannot display the name and nature of the address organization, people design a domain name, we just need to remember the domain name of the web page to visit, the network will visit the domain name through THE DNS table, get the CORRESPONDING IP address of the domain name, and then access the real IP address.

OSI- Reference model for development system Intercommunication

Physical layer (fiber optic computer), data link layer (binary electrical signal optical signal), network layer (IP protocol), transport layer (UDP,TCP), session layer.

30. The world wide web

Early discovery

Early search engines how to display web pages you want, by storing key word in the dictionary, I search for the cats, for example, it is stored in the cat this dictionary will be returned to the inside of the url, who first who last, see this site inside the cat, the number of occurrences of the word, obviously there are a lot of defects, there are a lot of garbage sites, will be the word cat infinite copy, It’s full of web content, and then it’s going to rank way up in the cat dictionary, but it’s not really worth anything. It’s just a collection of cats with no meaning to read. Google has been able to avoid this approach to search engine success, using associative storage, directional storage and so on.

HTML

HyperText Markup Language (HTML) is a standard Markup Language for creating web pages. You can build your own WEB site using HTML, which runs on a browser and is parsed by the browser.

The World Wide Web

The World Wide Web and the Internet are two different things. The Internet is a conduit for transmitting data. All kinds of programs use it. The most basic unit of the World Wide Web is a single page with links to other pages, called hyperlinks. These hyperlinks form a vast Internet.

31. Computer security

Identity check

Identity, access to what

Permission to check

If you can’t read up, you can’t read up from the lower level, which prevents non-core people from stealing secrets. If you can’t write down, you can’t write down from the lower level, which prevents core people from getting their core content into the lower level.

32. Hackers & Attacks

attack

DROP TABLE users; DROP TABLE users; DROP TABLE users; DROP TABLE users; DROP TABLE users; DROP TABLE users; If the server is not protected, the data table is cleared after user name verification.

SQL injection problem.

Buffer overflow, the login screen to enter the user name and password, behind the scenes, the system buffer to store the input value, let’s say the buffer size is 10, before and after other data, if the 10 limit is exceeded, the data will overwrite the data. The system may crash. You can also change the value of is_admin to true to bypass login and hijack the entire system. You can leave some unused space behind the buffer and track the value to see if it changes.

33. Encryption

A digital signature

  • Digital signature is simply a way to verify one’s identity by providing identifiable digital information.

  • A set of digital signatures typically defines two complementary operations, one for signing and one for verification. The sender holds the private key that can represent his own identity (private key cannot be disclosed), and the receiver holds the public key corresponding to the private key, which can be used to verify his identity when receiving the information of the sender.

Encryption and decryption terms

  • Encryption: The basic process of data encryption, that is, the original plaintext file or data is processed according to a certain algorithm to make it into an unreadable code, usually called “ciphertext”. Through such a way, to achieve the protection of data is not stolen by the unlegal person, the purpose of reading.

  • Decryption: The reverse process of encryption is decryption, that is, the process of converting the encoded information into its original data.

  • Symmetric and asymmetric encryption

    • The encryption key of symmetric encryption algorithm is the same as that of decryption key, and the encryption key of asymmetric encryption algorithm is different from that of decryption key. In addition, there is a class of hash algorithm that does not need the key.

    • Common symmetric encryption algorithms mainly include DES, 3DES, AES, etc.

    • Common asymmetric algorithms include RSA, DSA, etc.

    • Hash algorithms include SHA-1 and MD5.

    • Symmetric encryption algorithm is used earlier encryption algorithm, also known as shared key encryption algorithm. In symmetric encryption algorithms, only one key is used, and both sender and receiver use this key to encrypt and decrypt data. This requires that both encryption and decryption parties must know the encryption key beforehand.

    • Asymmetric encryption algorithm, also known as public key encryption algorithm. It requires two keys, one is called a public key, which is the public key, and the other is called a private key, which is the private key. Because encryption and decryption use two different keys, this algorithm is called an asymmetric encryption algorithm.

DES

  • DES is called Data Encryption Standard

  • DES algorithm to 64 bit plaintext input block into 64 bit ciphertext output block, it uses the key is also 64 bits (actually used 56 bits, 8, 16, 24, 32, 40, 48, 56, 64 bits are parity bits, so that each key has an odd number of 1)

  • It is a symmetric algorithm based on DES. It encrypts a piece of data three times with three different keys, with higher intensity.

AES

  • Advanced Encryption Standard (AES)

  • AES encryption algorithm is the advanced encryption standard in cryptography. The encryption algorithm adopts the symmetric block cipher system, and the key length can be at least 128 bits, 192 bits, 256 bits, and the packet length is 128 bits. The algorithm should be easy to be implemented by various hardware and software. This encryption algorithm is the block encryption standard adopted by the US federal government.

  • AES itself is designed to replace DES, with better security, efficiency and flexibility.

RSA algorithm

  • RSA encryption algorithm is the most influential public key encryption algorithm and is generally regarded as one of the best public key schemes at present. RSA is the first algorithm that can be used for both encryption and digital signature. It is resistant to all cryptographic attacks known to date and has been recommended by ISO as the standard for public key data encryption.

  • The RSA encryption algorithm is based on a very simple number theory fact: it is easy to multiply two large prime numbers, but extremely difficult to factor their product, so the product can be exposed as an encryption key.

MD5

  • MD5Using aThe hash functionIts typical application is to generate a piece of informationThe information in this paper,In order toPrevent tampering. Strictly speaking,MD5Is not aThe encryption algorithmbutThe algorithm. No matter how long the input is,MD5The output length is128bitsA string of (usually used16 Into the systemRepresented as a32Characters).

SHA1 algorithm

  • SHA1 is a message digest algorithm as popular as MD5, but SHA1 is more secure than MD5. For messages less than 2 ^ 64 bits in length, SHA1 produces a 160-bit message digest. MD5, SHA1-based information digest features and irreversibility (generally speaking) can be used to check file integrity and digital signatures.

Comparison of symmetric encryption algorithms

The name of the

The key name

The running speed

security

Resource consumption

DES

56

faster

low

In the

3DES

112 bits or 168 bits

slow

In the

high

AES

128, 192, 256 bits

fast

high

low

Comparison of asymmetric encryption algorithms

The name of the

maturity

security

speed

Resource consumption

RSA

high

high

In the

In the

ECC

high

high

slow

high

Machine learning & Artificial Intelligence

  • Classifier: An algorithm for classifying.

    • Characteristics are values used to aid classification.

    • Need constant training

    • For more difficult to distinguish, can add a new condition, namely decision boundary.

    • Maximizes correct classification + minimizes incorrect classification.

  • The decision tree

    • What features need to be selected for classification.

    • What values are used for each feature.

  • Techniques such as decision trees and support vector machines originated in statistics.

  • Deep learning

Computer vision

  • The image is a grid of pixels, each pixel’s color defined by three primary colors: red, green, and blue. Any color, also called RGB value, can be obtained by combining the intensity of the three colors.

  • Color tracking algorithm is a pixel by pixel search.

  • The edge of an object is made up of multiple pixels. To identify these features, the algorithm processes them pixel by pixel,

36. Natural language processing: NLP

  • Nouns, pronouns, articles, verbs, adjectives, adverbs, prepositions, conjunctions, interjections.

  • Using phrase structure rules for computers, sentences can consist of a noun phrase and a verb phrase, a set of rules can be assigned to a language, and from these rules, an analysis tree can be made. How to pick up the sound, the signal comes from the frequency at which the diaphragm inside the microphone vibrates, and on the horizontal axis is time, and on the vertical axis is how much the diaphragm moves. Let’s switch to a different graph, where the horizontal axis is time again, and the vertical axis is the amplitude of different frequencies, and the brighter the color, the louder the frequency

37. The robot

  • The mechanical paw

  • Artificial intelligence (ai)

    • unmanned

    • Humanoid robot

38. Computer Psychology

  • Computers are just tools to understand human psychology and make better computers.

  • Design your program for ease of use.

  • Intuitive features: make menu options easy to find and remember.

  • Give the computer the emotional intelligence to respond appropriately to the user’s state.

  • Calculation model

39. Educational technology

  • Expand learning channels

  • MOOC

  • Intelligent tutoring system

  • Virtual reality and augmented reality

Singularity, Skynet, The Future of computing

  • Will ARTIFICIAL Intelligence surpass human intelligence? Big discussion

  • The runaway development of intelligent technology is called singularity.

  • The impact of the development of computers on human beings: great challenges, such as the replacement of jobs.

  • New technologies: wearables, 3D printing, cryptocurrencies, and more

Refer to the article

Blog.csdn.net/weixin_4418…

Baidu Encyclopedia and other content