Notes de cours
Python notes unit 1 to 5
- Cours
- Établissement
In this document there is python notes of unit 1 to 5 theorys.
[Montrer plus]
Vendeur
S'abonner
laacheeeducation
Aperçu du contenu
CHAPTER - 11.Introduction
Computer Science
Solving problems by use of computation is known as computer science.
Python
Python supports both procedural and object-orientedProgramming.
1.1 Essence of computational problem solving
To solve a problem computationally, two things are needed: i) a representation that captures all
the relevant aspects of the problem, ii) an algorithm that solves the problem by use of the
representation.Let’s consider a problem known as Man, Cabbage, Goat, Wolf problem (Figure
1.1).
Figure –1.1 Man, Cabbage, Goat, Wolf Problem
A man lives on eastern side of a river wishes to bring a cabbage, a goat, and a wolf to avillage on
west side of the river to sell. His boat is only big enough to hold himself,and either the cabbage,
goat, or wolf. Man cannot leave the goat alone with cabbage because goat will eat cabbage, and
he cannot leave the wolf alone with goat because the wolf will eat the goat. To solve this
gamethere is a simple algorithmic approach. Try all possible combinations of items that may be
rowed back and forth across the river. Trying all possible solutions to a given problem is referred
to as a bruteforce approach. A representation that leaves out details of what is being represented
is a form of abstraction.
Start state of the problem can be represented as follows.
man cabbage goat wolf
[W, E, W, E]
in which the symbol W indicates that the corresponding object is on the west side of the
river—inthis case, the man and goat. (The locations of the cabbage and wolf are left unchanged).
Second state is
man cabbage goat wolf
, [W, W, E, E]
Third state is
man cabbage goat wolf
[W, W, E, W]
and the final state is
man cabbage goat wolf
[W, W, W, W]
A solutionto this problem is a sequence of steps that converts the initial state,[E, E, E, E]in
which all objects are on the east side of the river, to the goal state ,[W, W, W, W]in which all
objects are on the west side of the river. Each step corresponds to the man rowing aparticular
object across the river (or the man rowing alone). Python programminglanguage provides an
easy means of representing sequences of values. Main task isto develop or find an existing
algorithm for computationally solving the problem.
1.2 Limits of Computational Problem Solving
Once an algorithm for solving a given problem is developed or found check “Cana solution to
the problem be found in a reasonable amount of time?”.If not, then the particular algorithm is of
limited practical use.
Figure-1.2 Traveling Salesman Problem.
The Traveling Salesman problem (Figure 1.2) is a classic computational problem in computer
science.The problem is to find the shortest route of travel for a salesman needing to visit a given
set of cities. In abrute force approach, the lengths of all possible routes would be calculated and
compared to find theshortest one. For ten cities, the number of possibleroutes is 10! (10
factorial), or over three and ahalf million (3,628,800). For twenty cities, thenumber of possible
routes is 20!, or over two anda half quintillion (2,432,902,008,176,640,000).
If we assume that a computer could compute thelengths of one million routes per second, it
wouldtake over 77,000 years to find the shortest routefor twenty cities by this approach. For 50
cities,the number of possible routes is over 10 64. In thiscase, it would take more time to solve
,than theage of the universe!For problems such as this and the Traveling Salesman problem in
which a brute-force approach is impractical to use, more efficient problem-solving methods must
be discovered that find either an exact or an approximate solution to the problem.
1.3 Computer Algorithms
1.3.1 What Is an Algorithm?
Analgorithmisdefinedasastepbystepprocedureto solveaproblem.
“An algorithmcanalsobe definedas a finite number of clearly described, unambiguous “doable”
steps.It can besystematically followed to produce a desired result for given input in a finite
amount of time (that is, it eventually terminates)”.
For eg,
Algorithms solve generalproblems (determining whether any given number is a prime number),
and not specific ones (determiningwhether 30753 is a prime number).
The word “algorithm” is derived from theninth-century Arab mathematician, Al-Khwarizmi,
who worked on “written processes toachieve some goal.” (The term “algebra” also derivesfrom
the term “al-jabr,” which he introduced.)
Computer algorithms are central to computerscience. They provide step-by-step methods of
computationthat a machine can carry out. Having high-speedmachines (computers) that can
consistently follow andexecute a given set of instructions provides a reliableand effective means
of realizing computation. However,the computation that a given computer performsis only as
good as the underlying algorithm used. Understanding what can be effectively programmedand
executed by computers, therefore, relies on theunderstanding of computer algorithms.
1.3.2 Algorithms and Computers: A Perfect Match
Most algorithms are not as simple or practical to apply manually. Most require the use of
computers either because they would require too much time for a person to apply, or involve so
much detail as to make human error likely. Because computers can execute instructions very
quickly and reliably without error, algorithms and computers are a perfect match!
1.3.3 Method for Developing anAlgorithm
(1) Define the problem: State the problem to be solved in clear and concisemanner.
(2) List the inputs and outputs
(3) Describe the steps needed to convert input tooutput
(4) Test the algorithm: Choose input data and verify that the algorithmworks.
1.4 Computer Hardware
, Computer hardware comprises the physical part of a computer system. It includes the
all-importantcomponents of the central processing unit (CPU) and main memory. It also includes
peripheralcomponents such as a keyboard, monitor, mouse, and printer.
1.4.1 Digital Computing: It’s All about Switches
Computer hardware must be reliable and error free. If the hardware gives incorrect results,then
any program run on that hardware is unreliable. A rare occurrence of a hardware error
wasdiscovered in 1994. ie.,Intel processor was found to give incorrect results only whencertain
numbers were divided, estimated as likely to occur once every 9 billion divisions. Still,
thediscovery of the error was very big news, and Intel promised to replace the processor for any
onethat requested it.The key to developing reliable systems is to keep the design as simple as
possible. In digitalcomputing, all information is represented as a series of digits. We are used to
representing numbersusing base 10 with digits 0–9. Consider if information were represented
within a computer systemthis way, as shown in Figure 1.3
Figure –1.3 Decimal Digitalization.
In current electronic computing, each digit is represented by a different voltage level. The more
voltagelevels (digits) that the hardware must utilize and distinguish, the more complex the
hardwaredesign becomes. This results in greater chance of hardware design errors. It is a fact of
informationtheory, however, that any information can be represented using only two symbols.
Because of this,all information within a computer system is represented by the use of only two
digits, 0 and 1, calledbinary representation as shown in figure 1.4.
Figure –1.4 Binary Digitalization
In this representation, each digit can be one of only two possible values, similar to a light
switchthat can be either on or off. Computer hardware, therefore, is based on the use of simple
electronic“on/off” switches called transistors that switch at very high speed. Integrated
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur laacheeeducation. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €8,39. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
77985 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans