📄 http:^^cs-www.bu.edu^students^grads^dm^cs305^f95^cs305.html
字号:
Date: Wed, 20 Nov 1996 21:43:46 GMTServer: NCSA/1.5Content-type: text/html<HTML><HEAD><LINK REV="made" HREF="mailto:dm@cs.bu.edu"><TITLE>Computer Science 305 -- Fall 1995 ( 3-Nov-1995)</TITLE><!-- Changed by: David Martin, 3-Nov-1995 --></HEAD><BODY><H1><!WA0><IMG SRC="http://cs-www.bu.edu/lib/pics/bu-logo.gif"><BR><!WA1><IMG SRC="http://cs-www.bu.edu/lib/pics/bu-label.gif"><EM>Computer Science 305<BR>Automata and Formal Languages</EM></H1><H3>Fall 1995 Syllabus</H3><HR><!WA2><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw6.ps">Click here for a postscript version of Homework 6.</A>(Due Thursday, December 16---NO LATE HOMEWORKS ACCEPTED)<BR><!WA3><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw5.ps">Click here for a postscript version of Homework 5.</A> (Due Tuesday, November 21)<BR><!WA4><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw4.ps">Click here for a postscript version of Homework 4.</A> (Due Tuesday, November 14)<BR><!WA5><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw3.ps">Click here for a postscript version of Homework 3.</A><BR><!WA6><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw2.ps">Click here for a postscript version of Homework 2.</A><BR><!WA7><A HREF="http://cs-www.bu.edu/students/grads/dm/cs305/f95/hw1.ps">Click here for a postscript version of Homework 1.</A><H2>Instructor</H2><B>David Martin</B><BR>MCS 209 (second floor, in Graduate Student Lane)<BR>353-3326 (my office)<BR>353-8919 (department office; messages only)<BR>Click here to send mail to <!WA8><A HREF="mailto:dm@cs.bu.edu">dm@cs.bu.edu</A>.<H2>Office Hours</H2>Monday, 2:00pm - 3:00pm<BR>Tuesday, 2:00pm - 3:00pm<BR>Thursday, 2:00pm - 3:00pm<BR>Watch for additional or altered hours as the semester progresses.<H2>Classroom and Meeting Times</H2>Classes meet Tuesday and Thursday, 12:30pm - 2:00pm(i.e., 12:30pm - 1:50pm, according to standard BU conventions)in MCS B23, the basement of 111 Cummington St.<H2>Required Textbook</H2><EM>Automata and Formal Languages: An Introduction,</EM>Dean Kelley, Prentice Hall, 1995 <P><H3>Other Useful Books</H3><UL><LI> <EM>Elements of the Theory of Computation,</EM>Lewis & Papadimitriou, Prentice Hall, 1981<LI> <EM>Introduction to Automata Theory, Languages, and Computation,</EM>Hopcroft & Ullman, Addison-Wesley, 1979</UL><H2>Prerequisites</H2>To enroll in this course, you must have satisified the following courserequirements. If you haven't done so but still want to remain in thecourse, please see me.<UL><LI> MA 293 (Discrete Mathematics 1).<LI> CS 112 or CS 113 (Programming & Data Structures in C).</UL><H2>Topics</H2>This course is a core requirement in undergraduate computer sciencecurriculums at most colleges. Its purpose is threefold; first, toencourage you to investigate the nature of computation; second, to furtherdevelop your formal reasoning and writing skills; and third, to add newtechniques to your programming bag of tricks. <P>Accordingly, we will develop several formal models of computation, eachmore powerful than the last. At each stage we will prove some of what ourintuition suggests (and sometimes, what it denies) about these models. Wewill also see how most models admit two very different characterizations:one of machines that are able to recognize certain events, and another ofgrammars that are able to generate exactly what these machines recognize. <P>In particular, we will study regular languages, regular expressions, finitedeterministic and nondeterministic automata, context-free grammars,pushdown automata, turing machines --- and more, if time allows. <P><H2>Grading</H2><PRE>6 Homeworks 60%Midterm 20% Thursday, October 19Final 20% Saturday, December 16, 12:30-2:30pm</PRE>Note that each test is worth 2 homeworks. The tests will be much simplerthan the homeworks. <P><H2>Homework Assignments</H2>When writing up your homework, there are two goals you must keep in mind:first, to give evidence that you have put real thought into the problem,and second, to convince the reader that your solution is correct <EM>andthat you know why</EM>. As a programmer, you have some experience withthis sort of writing: an effective program must be written for both acompiler and a human reader. Similarly, solutions to your problems must becorrect in the sense of solving the stated problem, but they must also becomprehensible to the grader. <P>As with any writing, the first draft of a problem solution is usuallyunpresentable. All of the pieces may be there, but they tend to bechaotically assembled. <EM>The single most important thing you can do</EM>to make your solutions presentable is to rewrite them after you havediscovered why they are correct, and then to throw away (or at least tuckaway) your initial draft. Remember, scratch paper is cheap. <P>Be careful to realize that this emphasis on presentation has nothing to dowith whether English is your native language or whether you prefer to writeyour solutions with pencil, pen, quill, or word processor. A well-written solution starts by stating assumptions and thenworks towards a clearly defined goal, emphasizing the overall direction andomitting the superfluous. <P><H2>Late Policy</H2>In general, you will have at least one week to work on a homeworkassignment and at least three opportunities to attend my office hoursbefore that assignment is due. <P>Assignments turned in late for any reason will be marked late and will bescored at 60% of their face value. Assignments turned in more than a weekafter they were due will be scored at 0% of their face value --- that is, wewill still attempt to evaluate them, but they will not count towards yourgrade. For "excused" lateness, such as illness and family emergency, seethe "Grading Appeals" section below. <P><H2>Collaboration and Plagiarism</H2><PRE>col.lab.o.rate \k*-'lab-*-.ra-t\ \-.lab-*-'ra--sh*n\ \-'lab-*-.ra-t-iv\ \-.ra-t-*r\ vi [LL collaboratus, pp. of collaborare to labor together, fr. L com- + laborare to labor] 1: to work jointly with others esp. in an intellectual endeavor 2: to cooperate with or assist usu. willingly an enemy of one's country and esp. an occupying force 3: to cooperate with an agency or instrumentality with which one is not immediately connected - col.lab.o.ra.tion n</PRE>Collaboration is encouraged (primarily in the first and third senses) whenworking on homework problems and preparing for exams. None of the problemsin this class are intended to have secret solutions; the more resourcefulyou are at discovering solutions, the more time you will have to write themwell. Indeed, if you are stuck on a problem, I will be happy to talk withyou about it during office hours. However, the solutions you turn in mustbe your original writing. Copying a prepared solution is not collaborationat all; it is plagiarism. <P><PRE>pla.gia.rize \'pla--j*-.ri-z also -je--*-\ vt : to steal and pass off as one's own (the ideas or words of another) to present as one's own an idea or product derived from an existing source - pla.gia.riz.er n</PRE>Plagiarizing another's words is not tolerated at Boston University. It isso disdained that there are specific procedures for accusing and punishingthose who plagiarize. Do not copy another person's work and present it asyour own. <P>(The above definitions were snatched from the Webster server at BU.) <P><H2>Grading Appeals</H2><EM>Simple clerical errors</EM> will be corrected as soon as theyare brought to my attention. <P>Perhaps you will disagree about the grading of a particular problemor feel that an instance of lateness was justified. In order to bring thisto my attention, you must prepare a written appeal with supportingdocuments and give it to me during the last week of class. I willcarefully consider these appeals and make reasonable adjustments to yourbenefit when preparing the final grades. <P>This is <EM>only</EM> a mechanism for dealing with my gradebook in a fairmanner. <EM>You are always welcome to approach me with yourconcerns.</EM><P> If you don't know whether or how to write an appeal,use this as a guideline: I am likely to look more kindly upon "That wasjust a really bad week for me" than "My homework was always late becauseI... uh... had a headache." <P> <H2>Attendance</H2>Attendance is not an official part of the course grade, but it is yourresponsibility to stay informed. Some announcements will be made only inclass. <P><H2>Mailing List</H2>Other announcements will be made only by email. To add yourself to thecourse mailing list, log on to a CS cluster computer (such as csa) and type <P><PRE> csmail -a cs305</PRE><!WA9><IMG SRC=http://ei.cs.vt.edu/~history/ABC.GIF> <P>The <!WA10><A HREF="http://www.cs.iastate.edu/cgi-bin/hit-count?jva/jva-archive.html">Atanasoff-Berry Computer (ABC)</A> of 1939, claimed to be the first electronic digital computer. Photocourtesy of the <!WA11><A HREF="http://ei.cs.vt.edu/~history/">History of Computing Page</A> atVirginia Tech. <HR>Prepared by <!WA12><AHREF="http://cs-www.bu.edu/students/grads/dm/Home.html">David Martin</A>. Click<!WA13><A HREF="http://cs-www.bu.edu/courses/Home.html"> here</A> for information on other courses.</BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -