Python定制 | CS2110 Lecture 41 Dec. 9

CS2110 Lecture 41 Dec. 9, 2019
• HW 10 due Sunday, Dec. 15
• HW grading comments:
– Math game: some people problem-uniqueness check
but didn’t test (clear bugs that would have been
revealed by testing)
– HW9: too much collaboration among a few groups
• Today
– Current scores / grade levels
– HW 10 todo
– Some more CS theory
– Intro to Python regular expressions
Letter grade ranges:
A: 82+%
B: 70+%
C: 50+%
D: 40+%
Guarantee as of today: the percentages needed
for each grade won’t increase. Might decrease
Total course points:250
Posted already pts: 192
Remaining unsubmitted pts: 58
Remaining work:
HW 10: 3
Final: 55
Most people will have 1-2 additional points
based on promise of one free 3/3 HW and 1
point for HW9 API key On Wednesday, will give details including +/- grade
ranges and two different scales: one for if you take
final exam, one for if choose not to take final
1. Complete HW9. Do not do anything beyond this step until it is complete and working! Email me/TA when you can’t figure
things out!
2. Do the “enabling steps” – get Twitter account, credentials, “install” Oauth related modules. Make sure
functions work for you. (HW10 page will provide easy way to install the necessary Oauth-related modules.)
3. add new Entry for search term (don’t add a new button for this! Original button should now read both entries, execute
Twitter search, and retrieve and show map)
4. good practice: rename readEntryAndDisplayMap to, for example, readEntriesSearchTwitterAndDisplayMap?
5. Before trying to actually display tweets on GUI and markers for tweets on map, test basic integration of twitter search. Upon
button press, the readEntriesSearchTwitterAndDisplayMap callback function (command) should now read both Entry
widgets, and initially just:
– print tweet information the python shell
– Maybe initially print whole tweet dictionary, but next extract just needed parts – text, name, screen_name and print those
– Show the basic map, disregarding tweet information for now.
6. Once basic twitter integration has been checked, work on displaying tweet information in GUI and enabling “stepping
through” tweets:
– Save the retrieved tweets in a property of Globals. E.g. Globals.tweets
– set a value to indicate which is the “current tweet”. E.g. use another property such as Globals.currentTweetIndex. Set it to 0 when you first
retrieve the tweets.
– add widget(s) to GUI where tweet information can be displayed. Could be Label(s) but Text widget might be better (more on this later).
– Implement a function displayTweet that updates relevant GUI widget(s) with information from ’current tweet”
– Thus, readEntriesSearchTwitterAndDisplayMap should now read two Entries, call search Twitter, set some Globals properties, and call
displayTweet and displayMap
7. Add GUI widget(s) to change ”current tweet”. If prior things are done well, this should be easy. Much like zoom buttons.
Might have ‘Next tweet’, ‘Prev tweet” buttons that simply change Globals.currentTweetIndex, and then call ???
8. Make sure to constrain tweet search by location. Pass the lat/lng of the specified location in your call to searchTwitter. Experiment with “radius” argument. Default radius is 2km. Large and very small radii don’t seem to work well.
9. Add additional GUI widget(s) to display more tweet information, including the URLs within a tweet. This adds another layer
of complication. Tweets can contain multiple URLs and you should be able to step through these as well. So, in addition to
Globals.currentTweetIndex, you’ll probably want another property such as Globals.currentTweetURLIndex, along with
widgets to change this
10. Add code to allow opening of current tweet URL:
– E.g. a button and callback/command function that simply executes relevant URL). Note: your code will need to import
webbrowser module
11. Add markers (pins) for tweets.
HW10 Todo list
• recommendation: use Text widget rather than Label for displaying
– in GUI initialization
tweetText = tkinter.Text(width=…, height = …)
– in code to display tweet:
tweetText.delete(1.0, tkinter.END)
• Few tweets have non-null ‘coordinates’ field, so many of your
markers will likely be in the middle of the maps. That’s okay.
• recommendation: to get more tweets with non-null coordinates field, it seems
to help to use small search radius – e.g. 2km rather than 5 or 10.
• Search in popular location of, say, large city. E.g. “Times Square” and “party”
• Handling Unicode characters in tweets:
– Printing ”raw” text of some tweets in Python shell will cause errors
– see ”printable” function in for “hacky” approach to
eliminating unprintable characters
Introduction to Computing Using Python
Some additional theory tidbits
§ Turing machines: important
theoretical “universal
§ memory: infinitely long
“tape” of cells that can be
blank or contain 0 or 1
§ program: a set of “states”
and one fundamental
if state == q and tape cell
== x, set cell to y, state to
q’, move
This simple computer can
compute anything that is
§ A simulator
§ A “real” one J
Regular expressions can be
”recognized” by machines simpler than
Turing machines
• ”finite state machines” or “finite automata”:
• An easy-to-read introduction:
• An interactive simulator:
• Quick demo of Python re, re.match
The Halting Problem
§ it’s important to know what we can and can’t compute
§ It turns out that we cannot create program that can
check all other programs for infinite loops
§ see, e.g.,
§ First: demonstrate that we can write programs that
create and execute new programs/functions.
§ Informal proof that we can’t write doesItHalt
§ why can’t we create fully correct doesItHalt function?
§ To see why, consider function test in
Halting Problem
§ Imagine we could write program
doesItHalt(programString, dataString)
programString is the representation of a program as a string
(e.g. “def foo(n): \n\treturn(n+1)”),
and dataString represents input to that program
such that doesItHalt returns
“Yes” if the program (represented by programString) world halt on the
specified input, and
“No” if the program would not halt (i.e. would go into an infinite loop)
Note: It is not obvious that such a program can’t be written. But it should be clear
that doesItHalt can’t simply execute the specified program on the specified
input.(Why?) Instead, doesItHalt would need to rely on more sophisticated
HOWEVER, we can prove that doesItHalt cannot exist
doesItHalt does not exist
Informal proof:
Suppose doesItHalt exists (i.e. correctly
determines/prints, for any possible program and
input, whether or not the program halts on that
Consider function test. What happens
when you execute test( “def test …”)?
def test(programString):
result = doesItHalt(programString, programString)
if result == “No”:
print(“I’m done (hey, in fact, I halt)”)
loopFinished = False
while(not loopFinished):
print (“I’m gonna live forever …”)
doesItHalt does not exist
Informal proof:
1. Suppose doesItHalt exists (i.e. correctly states, for any possible
program and input, whether or not program halts on that input)
2. Create test function of previous slide. This is real Python code that
3. Consider test(“def test …”)
a. test(“def test …”) first executes doesItHalt(“def test ..”, “def test ..”), saving
returned value in variable result
b. if result was “No” test(“def test ..”) clearly halts and returns.
c. If result was “Yes” test(“def test ..”) clearly loops forever.
d. BUT NOTICE! result would be “No” if doesItHalt determined that test(“def
test …”) would not halt! And would be “Yes” if doesItHalt determined that
test(“def test …”) would halt!
e. THUS, test(“def test …”) halts if and only if test(def test …”) does not halt!!
4. This is a contradiction, so we must conclude that the
original assumption, that doesItHalt exists, is false.
Depiction of this on next slide might be easier to follow
dataString Yes
I’m done!
When does test(‘def test …’) print ‘I’m done’ (i.e. when does it halt)?
It halts when doesItHalt(‘def test …’, ‘def test …’) returns No
But, by assumption, doesItHalt(‘def test …’, ‘def test …’) returns No if and only
if it determines that function test would not halt given ‘def test …’ as input.
Thus, test(‘def test …’) halts if and only if test(‘def test…’) does not halt.
When does test(‘def test …’) loop infinitely? (i.e. when does it not halt)?
It loops infinitely when doestItHalt(‘def test …’, ‘def test …’) returns Yes
But, by assumption, doesItHalt(‘def test …’, ‘def test …’) returns Yes if and only
if function test would halt given ‘def test …’ as input.
Thus, test(‘def test …’) does not halt if and only if test(‘def test …’) halts.
Next time
• Quick intro to machine learning