1.(10 points) design a turing machine that performs the addition of two nonnegative unary numbers that are on the tape separated by a single blank cell. you need to show the machine's instructions and state diagram(note: the nonnegative unary numbers 0,1,2 and 3 are represented as 1,11,111and 1111 respectively.) 2.(10 points)write a complete c++ program to read in two integers and then write out the greatest common divider of those two numbers.(hint: the input and output instructions of c++ are cin an cout,respectively) 3.(10 points)a tennis tournament has n players,where n>1. a single match involves two players. the winner of a match will play the winner of a match in the next round,where losers are eliminated from the tournament.the two players who have won all previous rounds play the final game,and the winner wins the tournament.whtat is the total number of matches needed to determine the winner?write a c++ function,named int numberofmatches(int numberofplyers) ,to perform this task 4.(10 points) the following four requests could come into an opertating system as it is running on a computer system;a.the clock inside the computer has just "ticked,"and we need to update the seconds counter.b.the program running on processor k is trying to perform an illegal operation code.c.someone pulled the plug on the power supply,and the system will run out of power in the 50 msecd.the disk has just read the character that passed under the read/write head, and it wants to store it in memory before the next one arrives,in what order should the operating system handle these requests? 5.(10 points)insert the keys,in the order given as follows,to build them into an AVL tree:AZBYCX(note: show the procedure step-by-step.) 6.(10 points)construct a context-free grammar over(a,b)whose language contains precisely the strings with the same number of a's and b's. 7.(15 points)state the church-turing thesis. why is this called a thesis, instead of a theorem?give two reasons to support the church-turing thesis. 8.(10 points)what is a perceptron? describe its algorithm.what problems can a perceptron solve? what problems cannot be solved by a perceptron?suggest a modification to the perceptron so that the originally unsolved problems become solvable. 9.(15 point)the bin-packing problem follows:given an unlimited number of bins of volume 1 unit,and given n objects,all of volume between 0.0 and 1.0,find the minimum number of bins needed to store the n objects.describe a brute-force algorithm,an approximation algoritm and an optimal algorithm to solve the problem.give an example to demonstrate your algorithms.what are their time complexities? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.58.22.74