Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Software Douchebags > SE3310 Final > Flashcards

SE3310 Final Flashcards

1
Q

What is a set?

A

An unordered collection of unique elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a language?

A

A set of strings

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is computation?

A

Finding answers to yes/no questions (such as, is s in L?)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the range of a function?

A

The set of all outputs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a Finite State Transducer?

A

A DFA with outputs defined (for each transition)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the domain of a function?

A

The set of all possible inputs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a regular language?

A

A language where there exists a finite automaton that recognized it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the 2 interpretations for how NFAs function?

A
  • Parallel computation (execute all paths concurrently)

- Lucky guess (Always picks the correct path)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

T/F: Every NFA has an equivalent DFA

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

T/F: Every DFA has an equivalent NFA?

A

T - a DFA is an NFA silly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

T/F: Regular languages are closed under kleene star

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

T/F: Regular languages are closed under complement

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are the 6 steps in the pumping lemma for regular languages proof?

A
  1. Assume L is regular
  2. Let p = pumping length
  3. Pick string s (s must be in L, and size of s >= p)
  4. Examine all cases for dividing s = xyz
  5. For each case, find value i such that s’=x y^i z
  6. Conclude that there is no way to divide s into 3 parts xyz such that y can be pumped. Therefore L is not regular.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

T/F: All context free languages are regular

A

F : regular languages are a subset of context free languages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

T/F: All DFA’s have an equivalent CFG

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the restrictions on the size of y in the pumping lemma for regular languages proof?

A

|y| > 0

|xy| <= p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a pushdown automaton?

A

Essentially an NFA with ability to read/write from a stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the components of a turing machine?

A
  • tape
  • head
  • control
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the requirements for an algorithm / effective method?

A
  1. Finite # steps
  2. Always produces results
  3. Result is always correct
  4. Could in principle be done by human
  5. Only needs to follow instruction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What does the church-turing thesis declare?

A

Every effectively calculable function is a computable function (i.e. A problem can only be solved by an algorithm if it can be solved by a TM)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is a recursive language?

A

A decidable language: M decides L if it halts and accepts all s in L AND halts and rejects for all s NOT in L

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is a recursively-enumerable languages?

A

A recognizable language: M recognizes L if it halts and accepts all s in L

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

T/F : All recognizable languages are decidable?

A

F: all decidable languages are recognizable

24
Q

What is required for a system to be Turing complete?

A

Must be able to simulate any turing machine

25
Q

What is required for a system to be capable of universal computation?

A
  • read/write from memory
  • if statements
  • go to statements
26
Q

What is the Halting problem?

A

HALT consists of all TM’s that always halt. If you could decide HALT, you could prevent ever entering into an infinite loop

27
Q

Why does the halting problem matter?

A
  1. Proves existence of undecidable problems
  2. Proves you cannot solve the entshiedungsproblems (decision problem)
  3. Invented notion of stored program computer
28
Q

T/F: Atm is recognizable

A

T

29
Q

T/F: Atm is decidable

A

F

30
Q

T/F: The complement of Atm is recognizable

A

F

31
Q

What is U?

A

The universal TM. I recognizes , the set of accepting TM/string combos (Atm)

32
Q

What is running time?

A

t(n) : The max number of steps that a TM takes on an n-character string

33
Q

What is DTIME?

A

The time complexity class of all languages decidable by a DTM (Deterministic TM)

34
Q

What is P?

A

The class of all problems solvable by a DTM in polynomial time

35
Q

What is NP?

A

The class of all problems solvable by a NTM in polynomial time

36
Q

What is the running time of a NTM?

A

Maximum number of steps M takes in every computational path on any n-character string

37
Q

Does NP=P?

A

Probably not

38
Q

What is NP-complete?

A

Sub-class of NP, problems are at least as hard as all others in NP

39
Q

How can you prove that a language is NP-complete?

A
  1. B e NP

2. For all A e NP, A <= B where B is NP-complete

40
Q

What does the Cook-Levin theorem propose?

A

Proved that SAT is NP-complete, so proving SAT <= B is enough to prove B is NP-Complete

41
Q

What is NP-Hard?

A

Class of problems that are as hard or harder than any NP problem

42
Q

How do you prove a problem is NP-Hard?

A

Prove X <= B , where X is NP-Hard

43
Q

What class of problems contains optimization problems?

A

NP-Hard

44
Q

What is a probabilistic turing machine?

A

A PTM uses random bits to pick exactly one path to follow at each branch

45
Q

What is BPP?

A

Bounded-Error probabilistic polynomial-time: Class of problems solvable by a PTM in polynomial time with error probability <= 1/3

46
Q

T/F: P = BPP

A

Maybe

47
Q

What is BQP?

A

BQP (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3

48
Q

T/F: All context-free languages are recursive

A

T

49
Q

T/F: All recursively enumerable languages are recursive?

A

F

50
Q

T/F: All regular languages are decidable?

A

T

51
Q

T/F: All problems in P are also in BPP

A

T

52
Q

T/F: All problems in NP are in NP-Hard

A

F

53
Q

T/F: All NP-complete problems are also in NP

A

T

54
Q

Can a turing machine contain just one state?

A

No: must contain at least 2 distinct states: accept and reject

55
Q

Can the tape alphabet of a TM be the same as the input alphabet?

A

No - tape alphabet must contain the empty symbol |_| while the input alphabet cannot contain it

56
Q

Can a Turing machine’s head ever be in the same location in two successive steps?

A

Yes - if the TM attempts to move its head off the left-hand end of the tape, it remains in the same tape cell

Software Douchebags (15 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions