Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
tpsApril11/moreParking.tex
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
executable file
293 lines (270 sloc)
15.5 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\section{Discussion} | |
\subsection{Importance} | |
Importance goes here, rather than in analysis\\ | |
Programmers/developers who produce and/or verify software that is used in safety critical applications, such as medical equipment, self-driving cars, and defense-related equipment should be able to know that their software functions correctly. | |
Programmers/developers who produce and/or verify software that is expected to perform work, such as search, efficiently, should be able to know that their algorithms are efficient. | |
Computer science is the expected background preparation for people working in these careers. | |
Proof is the method that is used to ascertain, and to convince, that these goals have been achieved. | |
\subsection{Interpretation of Results} | |
As in mathematics, some students learn as procedure that which we would prefer that they understand. | |
Some procedural learning is insufficiently accompanied by an understanding as to which contexts to which it applies, and has become in some cases what Whitehead calls "inert knowledge". | |
\section{Previously Published Work} | |
\section{Categories of Experience of Entering Students} | |
Undergraduate students beginning study of the computing disciplines present | |
a various degrees of preparedness.\cite{reilly2014examination} Some interview participants enjoyed | |
a modified Moore method\cite{cohen1982modified} geometry class in middle school, and relished | |
opportunities to create proofs (not yet published). Other students are not so | |
well prepared. | |
After publishing this paper, more information relating to its topic has been | |
encountered. For example, consistent with the work of Almstrum \cite{almstrum1996investigating}, we have | |
found that, about implications, some students, who do know that any statement | |
must and can, be either true or false, think implications must be true. | |
\section{ Representation/Symbolization in Pumping Lemmas} | |
Some of our results to date are consistent with the framework described by | |
Harel and Sowder in 1998\cite{harel1998students}. We have found students holding conceptualizations | |
that Harel and Sowder's 1998 model\cite{harel1998students} calls symbolization: We have found | |
that some students may lack facility in notation. For example, in the application | |
of the pumping lemma, students are expected to understand the role of $i$, | |
in the context that a string $s$, having component substrings $x$, $y$ and $z$, can be | |
used to generate other strings, of the form $xy^iz$, where $i$ gives the number of | |
copies of the substring $y$. Moreover, students are expected to understand that | |
the subdivision of a string of length $p$, expressed as $\sigma_1^a\sigma_2^{p-a}$, where $a \in \{0,1,\ldots,p\}$ | |
uses $a$ as a parameter, a free variable, not one necessarily bound to a single instance | |
of a natural number, but a representation of a domain. We have seen this | |
lack of understanding in a situation in which it was proposed as evidence that | |
a single example, namely $\sigma_1^a\sigma_2^{p-a}$, formed a proof for a universally quantified | |
statement. An excerpt of the errors found on tests is shown in Table . | |
Table : Some example errors\\ | |
Let x be empty\\ | |
$|xy| \leq p, so xy = 0^p$\\ | |
$|xy| \leq p; let x = 0^{p+r}, y = 0^{p+r}, 0 < r < p$\\ | |
Let's choose $|xy| = p$\\ | |
$0^{p+1}0^b1^p \neq 0^{p+1}1^p \therefore xy^2z \not\in \mathcal{L}$\\ | |
where $\mathcal{L} = \{0^i1^j, i \neq j\}$\\ | |
we choose $s = 0^{p+1}1^p$ within $|xy|$\\ | |
thus $\neq 0^p1^{p+1}$\\ | |
Let $x = 0^a, y = 0^b1^a$\\ | |
$x = 0^{p-h}, y = 0^h$\\ | |
$x = 0^i, y = 0^i, z = 0^i1^j$ | |
Figure: Some categories / conceptualizations found among students of | |
introduction to the theory of computing, and published at FIE. | |
Harel and Sowder identified a category of conceptualization that correctly | |
applied transformation and axiomatic arguments. Some students expressed | |
enthusiasm for the power that inheres to building arguments with carefully | |
specified component ideas, in particular how the absence of ambiguity permitted | |
arguments to extend to great length while remaining valid. Not all of the | |
students had developed axiomatic conceptualizations of proof. About definitions, | |
we have collected preliminary data on students' conceptualizations of | |
definitions used in proofs. Some students think definitions are boring. Some | |
students think that they can infer definitions from a few examples. Concerning | |
executive function, we have found that some students do not state the | |
premises clearly, and some students do not keep track of their goal. About | |
rules of inference, we have found that some students apply invalid approaches | |
to inference. | |
\section{ Abstract Model for Proof by Mathematical Induction and Recursion} | |
Interviews with students revealed that some students see generation of a proof | |
by mathematic induction as a procedure to be followed, in which they produce | |
a base case, and prove it, and produce an induction step, and prove that. Some | |
of the students interviewed did not know why this procedure generated a | |
convincing argument. Moore, as reported in Polya[] noted that some students | |
of mathematics formed the same conceptualization, that there is a procedure, | |
but it does not necessarily produce a convincing argument. Polya[] wrote | |
a problem involving all girls being blue-eyed; a similar problem appears in | |
Sipser\cite{sipser2012introduction} about all horses being the same color. The purpose of this exercise is | |
to make students aware that the truth of the inductive step must apply when | |
the base case appears as the premise. In some cases, this point was not clear to | |
the students. | |
Students' conceptualizations of proof by mathematical induction can support | |
their choosing to apply recursive algorithms. One student reported success at | |
both mathematical induction and recursive algorithm application without ever | |
noticing any connection. This student opined that having learned recursion | |
with figures, and proof by mathematical induction without figures, that no | |
occasion for the information to spontaneously connect occurred. Students reporting | |
ability to implement assigned problems recursively, but not the ability | |
to understand proof by mathematical induction also reported that ability to | |
write recursive programs did not result in recognition of when recursive solutions | |
might be applicable in general. Students reporting ability to implement | |
assigned problems recursively, and also the ability to prove using mathematical | |
induction also reported preferring to implement recursive solutions in | |
problems as they arose. | |
Our work on students' choices of algorithmic approaches is consistent with | |
work by other researchers in computer science education\cite{} on conceptualizations | |
of algorithms. Our work served to unify that of mathematician educators | |
with that of computer science educators, by providing a plausible explanation why | |
the conceptualizations of recursive algorithms that were found, might exist. | |
Figure 4.0.2: Conceptualizations of proof by induction and recursion, published | |
in Koli Calling | |
Index Element of Model | |
\begin{enumerate} | |
\item Some students begin learning proof by mathematical induction as if it were | |
a procedure. | |
\item Some students learn two parts of this proof technique without seeing any | |
connection between the two. | |
\item Some students do not find the procedure to be a convincing argument. | |
\item Some students would not employ proof by mathematical induction to explore | |
whether a recursive algorithm would apply to a given problem. | |
\item Some students understand both proof by mathematical induction and also | |
recursion and had never noticed any similarity. | |
\end{enumerate} | |
\section{Results of Combined Investigations} | |
There are some categories that are shared among the several contexts. | |
\section{Categories} | |
Categories found in one or more investigations | |
Categories\\ | |
Definition of proof as convincing (to mathematicians) argument is not | |
always understood\\ | |
Definitions in general are not always recognized as significant building | |
blocks in arguments\\ | |
The idea of a false statement sometimes becomes troublesome when | |
negation is being learned.\\ | |
In particular, accepting that an implication may be false, can be troublesome. | |
Notation is sometimes difficult.\\ | |
Ideas presented relying on notation are not always connected with | |
ideas presented relying on figures.\\ | |
Warrants are not always recognized.\\ | |
Students do not always traverse levels of abstraction effectively.\\ | |
The applicability of valid argument forms to contexts of interest is not | |
always appreciated. | |
\section{ Critical Factors} | |
To determine critical factors, we can convert negative categories into achievement | |
levels. | |
\begin{tabular}{p{3cm}p{3cm}} | |
Categories & Achievement Levels\\ | |
The idea of a false statement | |
sometimes becomes troublesome | |
when negation is being | |
learned.&\\ | |
&True and false make sense, and | |
we can make arguments using | |
them.\\ | |
Definition of proof as convincing | |
argument is not always understood&\\ | |
Warrants are not always recognized.&\\ | |
&Proof can sometimes be obtained | |
through a series of warranted assertions.\\ | |
Definitions in general are not always | |
recognized as significant | |
building blocks in arguments&\\ | |
&Using agreed definitions and | |
valid rules of inference we can | |
sometimes explore the consequences | |
of definitions.\\ | |
Notation is sometimes difficult.&\\ | |
&Notation helps.\\ | |
Ideas presented relying on notation | |
are not always connected | |
with ideas presented relying on | |
figures.&\\ | |
&We might wish to help students | |
traverse multiple rendering of | |
ideas.\\ | |
Students do not always traverse | |
levels of abstraction effectively.&\\ | |
&We might wish to help students | |
traverse multiple levels of abstraction.\\ | |
The applicability of valid argument | |
forms to contexts of interest | |
is not always appreciated.&\\ | |
&We might wish to give exercise | |
with authentic (career related) | |
examples\\ | |
\end{tabular} | |
Using the achievement levels we can infer critical factors. | |
\begin{tabular}{p{3cm}p{3cm}} | |
Achievement Levels& Critical Factors\\ | |
True and false make sense, and | |
we can make arguments using | |
them.&\\ | |
& True and false apply to assertions.\\ | |
Proof can sometimes be obtained | |
through a series of warranted assertions. | |
& Proof is exploration and discovery.\\ | |
Using agreed definitions and | |
valid rules of inference we can | |
sometimes explore the consequences | |
of definitions.&\\ | |
& Efficiency but also abstraction | |
are aided by notation.\\ | |
Notation helps.&\\ | |
& Notation is one representation | |
and there are others. Ideas appear | |
in multiple guises.\\ | |
We might wish to help students | |
traverse multiple rendering of | |
ideas.&\\ | |
& When notation allows for multiple | |
interpretations, abstraction | |
above those multiple interpretations | |
has been achieved.\\ | |
We might wish to help students | |
traverse multiple levels of abstraction.&\\ | |
&Multiple levels of abstraction are | |
relevant at the same time.\\ | |
We might wish to give exercise | |
with authentic (career related) | |
examples.&\\ | |
& Authentic applications show the | |
use of this knowledge.\\ | |
\end{tabular} | |
\subsection{Abstraction} | |
Literature reports \cite{} students of CS have trouble with abstraction. | |
Taking abstraction to be the ability to select some details to ignore, | |
and thereby find a simpler model of an entity, we can transform the ideal | |
knowledge transfer experience into on disabled by a lack of ability to see this dimension. | |
The multiple-inheritance hierarchy that could be used to organize | |
definitions and relationships of ideas is less able. More entities will be | |
grouped together than effective use of the multiple inheritance hierarchy | |
would consider equivalent. | |
Another useful concept that students have been seen to underappreciate is the significance of careful definitions. | |
Abstraction hierarchies allow for efficiency in definitions. | |
A new entity can be defined as a specialization of an existing entity, and its differences | |
make up the new definition material. | |
In the absence of this multiple inheritance hierarchy, every definition in its full length | |
is attached to its entity. | |
Tie in with Mazur. For students holding the same granularity of refinement of | |
concepts, conversations would be easier, because there would be fewer disconnects as one participant expressed a thought on one degree of refinement far from that of another student. | |
If the ideas implying the refinement of the definition inheritance graph, being different from one | |
discussant to the next, are rare, and/or the meaning of the sentence does not depend upon it, these exchanges are not too disruptive or distressing. | |
On the other hand when two sets of refinement are very different, | |
and the meaning of the exchange depends upon the refinement in the speaker, that the hearer does not have, | |
then some degree of failure of communication will ensue. | |
Absence of abstraction converts tree of topics into sequence of topics. | |
Tree of proof examples (say of application of proof technique) into sequence of examples. | |
Might detract from recognizing what is a related example. | |
Would detract from plausible inference technique of ``related problem seen before''. | |
We have a goal for student programming that they should strive for segments of programs | |
(e.g., method implementations) to be small. One way of accomplishing this is to use abstraction, | |
such as combining instructions into a method, and calling the method. | |
If students have difficulty with abstraction, they might | |
have difficulty with choosing groups of instructions to represent a method. | |
Correspondingly, if they practice grouping instruction into methods, and using those methods, they would | |
be gaining practice relevant to using abstraction. | |
One way to cultivate abstraction is to pose a question of which one of several examples is different. | |
When several things are examples of one abstract idea and one is not, identifying the one that is different involves noticing the abstraction. | |
These questions could be instantiated using blocks of code. | |
\subsection{Definitions} | |
Without abstraction the burdensomeness of definition is increased. This could contribute to the reluctance of students to embrace definitions. | |
\subsection{Symbolization} | |
Use of symbols is a kind of abstraction. | |
Symbolization is the syntax for simple, clear definitions as Gries\cite[p.205]{gries2012science}(Science of Programming) recommends for construction of programs. | |
Students will be hindered at this program derivation/development style if symbolization is a not-yet-acquired skill. | |
Program development/derivation should begin with a formulation of the requirements. | |
Students may arrive with some programming experience that is of a more intuitive, less | |
mathematically disciplined sort. | |
We have to ask how we desire to cultivate the abilities of such students. | |
Vygotsky discussed language acquisition by children, in which some children will have begun to invent | |
some terms for items in their environment, and will need to be guided to abandon neologisms for the naming generally agreed in their environment. | |
Kuhn discussed the reluctance of scientists who have been rewarded for operating in one | |
perspective on nature to adopt a different perspective. | |
Instructor may encounter a similar reluctance on the part of students | |
to adapt a scientifically/mathematically disciplined approach to programming, | |
especially if the students have experienced some success in their earlier work. | |
To win over such students, | |
demonstration of superior outcomes on problems, especially on problems that seem insoluble otherwise, | |
are more frequently convincing. | |
Happily, Professor Gries has provided such examples. | |
By showing superior relative efficacy of these approaches in an activity the students recognize as | |
desirable, instructors could motivate the students to learn symbolization. | |
\subsection{Structure} | |
sequence vs. sequence that has come about from combining parts. Refer to Leslie Lamport's structure for proofs. Combine with Gries' proofs for deriving code. The purpose for getting through Goguen and Malcolm is that it applies to imperative programs. | |
%\chapter{Data} |