Decisison Problem, Deep Learning Computer Vision

Question 1

Decision problem

Answer 1

Is there any combination of outputs such that z = 1

This type of a decision problem is called satisfiability

Question 2

Satifiable

Answer 2

A circuit is satifiable if there are any combinations of A,B,C, such that Z= 1

Question 3

Satisfying assignment

Answer 3

When the circuit letters are all given a value that would make Z = 1

Question 4

Certificate

Answer 4

Decision problems are answered yes or no, but they require proof. This proof is called a certificate it allows anyone to verify the correctness of the answer

Question 5

Complexity class

Answer 5

Computational problems can be organized into complexity classes to characterize their difficulty

Question 6

P (polynomial time)

Answer 6

Decision problem that can be answered with a polynomial number of operations

• isSorted
• uvPath
• weightProblem

Question 7

NP (nondeterministic polynomial time)

Answer 7

Decision problem for which a yes answer with a certificate can be verified in polynomial time

• SAT
• Partition
• Dominating set

Question 8

Turing table

Answer 8

Some problems like choosing the best chess move on an arbitrary large board are not NP, but can be solved by a computer

-nxn Chess

Question 9

Non-Turing decidable

Answer 9

Some problems are proven to be undefinable by Turing machine

• Halting problem
• posts correspondence problem

Question 10

Using data

Answer 10

• learn the limitations of your data
• understand how data is acquired
• identify where the mathematical elegance becomes impractical
• domain knowledge

Question 11

Computer vision and deep learning used in

Answer 11

• computer graphics
• astronomy
• biomedical imaging

Question 12

Active data acquisition

Answer 12

Beyond passive machine learning
Learn from data hot to collect data
Be active when making decisions