An Introduction to Global Sequence Alignment Dynamic Programming

BRIG0.95ManualNabil AlikhanJune27,2011/projects/brig/1CONTENTS2 Contents1Introduction3 2Licence9 3Installation93.1Installing BLAST (9)4Warning when using BLAST114.1Low complexityfiltering (11)4.2Expected values(e-values)and bit scores (11)5Visualising whole genome comparisons135.1Step1:Load in sequences (13)5.2Step2:Configure rings (14)5.3Step3:Review and submit (16)6Working with a Multi-FASTA reference186.1Step1:Load in sequences (18)6.2Step2:Configure rings,annotations and spacer value (19)6.3Step3:Configure image settings and submit (23)7Visualising graphs and genome assemblies257.1Walkthrough for visualising SAMfile mapping coverage (26)7.2Walk through for visualising acefile assembly coverage (31)8Walkthroughs on creating custom annotations398.1Adding custom annotations from a tab-delimitedfile,GenBank orEMBLfile (39)8.1.1Step1:Load in sequences (39)8.1.2Step2:Configure rings (40)8.1.3Step3:Adding annotations (41)8.1.4Step4:Review and submit (43)8.2How to create tab-delimitedfiles for BRIG (45)9Configuration options469.1Saving and reopening your work (46)9.2BLAST options (46)9.3Setting BRIG options (48)9.4Setting Image options (50)9.5Loading a preset image template (52)1INTRODUCTION3 1IntroductionThe BLAST Ring Image Generator(BRIG)is a cross-platform desktop applica-tion written in Java1.6.It uses CGView[5]for image rendering and the Basic Local Alignment Search Tool(BLAST)for genome comparisons.It has a graph-ical user interface programmed on the Swing framework,which takes the user step-by-step through the configuration of a circular image generation.Figure1is an example of an image BRIG can create.Figure1:BRIG example output image of a simulated draft E.coli O157:H7 genome.Thefigure show BLAST comparisons against28published E.coli and Salmonella genomes against the simulated draft genome.1INTRODUCTION4 Figure2shows a magnified view of the same example image showing similar-ity between a central reference genome in the centre against other query sequences as a set of concentric rings,where colour indicates a BLAST match of a particular percentage identity.BRIG does not represent sequences that are not present in the reference genome The image shows:•GC skew,•GC content,•Genome coverage and contig boundaries(calculated from an assemblyfile),•Genome alignment results,customs annotations.Figure2:A magnified view of BRIG example image1INTRODUCTION5 How to use this manualThis manual contains a set of detailed walk throughs where readers are taken step by step through a worked example.Each walkthrough highlights different features of BRIG and users should work through each one.If you are interested in a particular aspect of BRIG,please turn to the relevant walkthrough:•Whole genome comparisons,including how to load in coverage graphs,e.g.Figures1&3,see Section5on page13.•Using a user-defined list of genes as a reference(in Multi-FASTA),e.g Fig-ure4,see Section6on page18.•Creating and visualising graphs generated from assembly(.ace)or read mapping coverage(.SAM),e.g Figure5,see Section7on page25.•Labeling images with information from GenBank,Tab-delimited or Multi-FASTAfiles,like those seen in Figure3,4&5,see Section8on page39.The manual also has detailed instructions for how to install and configure BRIG:•For instructions on how to install BRIG,see Section3on page9.•For instructions on how to configure BRIG and save BRIG settings,see Section9on46.1INTRODUCTION6Figure3:Reference:Published E.coli O157:H7Sakai genome.Query:Com-plete genome sequences of related strains,listed in the key.The prophage regions from the Sakai genome are marked in alternating black&blue.To make an image like this please refer to Section5on page13.1INTRODUCTION7Figure4:Reference:A list of translated genes that make up the Locus of Entero-cyte Effacement(LEE),which encodes a Type III secretion system.Query:Raw sequencing reads simulated from several complete LEE+published genomes(nu-cleotide sequence)and E.coli K12,(negative control;LEE-).You can clearly see gene presence/absence,and divergence(the colour represents sequence identity on a sliding scale,the greyer it gets;the lower the percentage identity).To make an image like this please refer to Section6on page18.1INTRODUCTION8Figure5:Reference:Published E.coli O157:H7Sakai genome.Query:Read mapping coverage of sequencing reads simulated from complete genomes,indi-cated in the key.Simulated sequencing reads were mapped onto the published complete Sakai genome using BWA.The read coverage for each genome was generated from the resulting SAMfipare this with Figure3,which is based on the original published genome sequences.To make an image like this please refer to Section7on page25.2LICENCE9 2LicenceThis program is free software:you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foun-dation,either version3of the License,or(at your option)any later version.This program is distributed in the hope that it will be useful,but without any warranty;without even the implied warranty of merchantability orfitness for a particular purpose.See the GNU General Public License for more details.You should have received a copy of the GNU General Public License along with this program.If not,see</licenses/>.Please note that these restrictions do not apply to the third party libraries bundled with this software.3InstallationThere’s no real”Installation”process for BRIG itself.However,BLAST+[2]or BLAST legacy[1]must already be installed and BRIG needs to be able to locate the BLAST executables(See Section3.1).To run BRIG users need to:1.Download the latest version(BRIG-x.xx-dist.zip)from/projects/brig/2.Unzip BRIG-x.xx-dist.zip to a desired location.3.Run BRIG.jar,by double clicking.Users who wish to run BRIG from the command-line need to:1.Navigate to the unpacked BRIG folder in a command-line interface(termi-nal,console,command prompt).2.Run“java-Xmx1500M-jar BRIG.jar”.Where-Xmx specifies the amountof memory allocated to BRIG.3.1Installing BLASTThe latest version of BLAST+[2]can be downloaded from:ftp:///blast/executables/blast+/LATEST/ BLAST+offers a number of improvements on the original BLAST implementa-tion and comes as a bundled installer,which will walk users through the installa-tion process.Please read the published paper on BLAST+:3INSTALLATION10 Camacho,C.,G.Coulouris,et al.(2009).“BLAST+:architecture and appli-cations.”BMC Bioinformatics10(1):421Available online at:http://www. /1471-2105/10/421The latest version of BLAST legacy[1]can be downloaded from:ftp:///blast/executables/release/LATEST/ BLAST legacy comes as a compressed package,which will unzip the BLAST binaries where ever the package is.We advise users tofirst create a BLAST direc-tory(in either the home or applications directory),copy the downloaded BLAST package to that directory and unzip the package.BRIG supports both BLAST+&BLAST ers can specify the loca-tion of their BLAST installation in the BRIG options menu which is: Main window>Preferences>BRIG options.The window is shown in Figure6.If BRIG cannotfind BLAST it will prompt users at runtime.PRO TIP1:BRIG uses BLAST,do not use wwwblast or netblast with BRIG. PRO TIP2:If BOTH BLAST+and legacy versions are in the same location, BRIG will prefer BLAST+.Figure6:You can change where BRIG looks for BLAST in the BRIG options window.For more information about BRIG options see Section9.2on page48.4W ARNING WHEN USING BLAST11 4Warning when using BLASTBRIG relies on the Basic Local Alignment Search Tool(BLAST)for genome comparisons.BLAST has a number of behaviours that may seem counterintuitive and we encourage users to learn about local alignment and the BLAST algorithm to fully understand the images that BRIG produces.There are a few concepts to keep in mind when using BRIG:4.1Low complexityfilteringPRO TIP3:BLASTfilters may cause gaps in alignments,which will show up as blank regions in BRIG images.BLASTfilters(BLAST legacy-Fflag or BLAST+-dust/-seg noflag)filter the query sequence for low-complexity sequences by default.This includes sequences that are highly repetitive or contain the same nucleotide for long lengths of the sequences.Low-complexityfiltering is generally a good idea,but it may break long matches into several smaller matches.This is often shown in BRIG images as truncations or gaps in alignments,it is particularly obvious in very small reference sequences where alignments are shown on a gene-by-gene level.To prevent this,either turn offfiltering or use soft masking.4.2Expected values(e-values)and bit scoresPRO TIP4:BLAST’s bitscorefiltering may cause different results in BRIG if users swap the query and reference sequences,particularly if these are very different sizes.BLAST uses statistical thresholds tofilter out“bad alignments”;alignment matches that appear random to BLAST.One of these thresholds is the e-value,which is the probability of the alignment occurring by chance,given the complexity of the match,sequence composition and the size of the database.It is more likely in a larger sequence that an alignment could occur by chance,so BLAST is more critical of these matches.This can create different expected values if BLAST is used with the same reference sequence against databases of different sizes and may potentiallyfilter out significant matches or include poor scoring ones.4W ARNING WHEN USING BLAST12 Because of this,users might notice different results in BRIG images if they swap the order of the database and reference sequences around in the BLAST, especially if the two sequences are quite different in size.The differences are often due to a few very low-scoring hits.Users should consider what an appropriate e-value threshold is for the compar-isons that they run.Remember,that BLAST runs with an e-value of10by default, we recommend that users change this ers can set thefinal threshold (e-value)with the-eflag in BLAST legacy or-evalueflag in BLAST+.PRO TIP5:BLAST does not handle spaces infilenames,BRIG will prompt users if they have spaces infile locations.5VISUALISING WHOLE GENOME COMPARISONS135Visualising whole genome comparisonsIn this section we will walk through the basics of generating an image.This walk through will be comparing an E.coli genome withfive other E.coli genomes and mapping the read coverage from the underlying genome assembly onto the same image.For this walk through,users will need BRIG examples.zip,which is avail-able from the BRIG website(/projects/brig/ files/).This contains all the genomes andfiles needed to follow along with this walk through.Unzip it somewhere easily accessible,like the home directory or desktop.About the reference genomeThe reference genome used in this walk through is a simulated E.coli genome assembly.We took the published E.coli O157:H7Sakai genome(Accession num-ber BA000007)sequence and had assembly reads simulated by METASIM[4]and then assembled these using Newbler version2.3.The resulting contiguous se-quences were ordered using Mauve[3]against the published Sakai genome.This simulated E.coli is useful for illustrating some of BRIG’s graphing features for assembly read coverage.Enterohemorrhagic E.coli are gram-negative,enteric bacterial pathogens.They can cause diarrhea,hemorrhagic colitis,and hemolytic uremic syndrome.This particular genome we are using in this example was based on an E.coli O157:H7 isolated from the Sakai,Japan outbreak.5.1Step1:Load in sequencesThe walk through will work out of the unzipped BRIG examples.zip in the Chap-ter568wholeGenomeExamples folder.The walk through and relatedfigureswill use C:\BRIG examples\Chapter568wholeGenomeExamples as that loca-tion.To keep thefinal image consistent with the walk through,please open”Exam-pleProfile.xml”from the Chapter568wholeGenomeExamples folder.Thisfile configures BRIG to the same image settings in the walk through.1.First,set BRIGExample.fna as the reference sequence.2.Set<unzipped BRIG examples folder>\Chapter568wholeGenomeExamplesas the query sequence folder.3.Press“add to data pool”,this should load several items into the pool list,there should be ninefiles.5VISUALISING WHOLE GENOME COMPARISONS144.Set the Chapter568wholeGenomeExamples as the output folder.5.The BLAST options box should be left blank.6.Click nextPRO TIP6:Users can add individualfiles to the data pool too.5.2Step2:Configure ringsThe next step is to configure what information is shown on each of the concentric rings in BRIG.Create six rings,for each ring:1.Set the legend text for each ring2.Select the required sequences from the data pool and click on“add data”toadd to the ring list.3.Choose a colour4.Set the upper(90)and lower(70)identity threshold.5VISUALISING WHOLE GENOME COMPARISONS155.Click on“add new ring”and repeat steps for each new ring required.The values required for each ring are detailed in the table below.Notice that thatsequences can be collated into a single ring,like the example of K12&HS.The ring will show BLAST matches from both HS and K12.Legend text Required sequences ColourGC Content GC Content IgnoreGC Skew GC Skew IgnoreCoverage BRIGExample.graph153,0,0O157:H7E coli O157H7Sakai.gbk0,0,153HS and K12E coli HS.fna0,153,0E coli K12MG1655.fnaCFT073and UTI89E coli CFT073.fna153,0,153E coli UTI89.fna5VISUALISING WHOLE GENOME COMPARISONS16 PRO TIP7:Rings can be reordered by dragging them in the Ring List pane. PRO TIP8:You can set default threshold values in“BRIG options”.See section9.2(page48)for more details.PRO TIP9:When using a Genbank/EMBLfile as a reference,users can choose whether to use the protein or nucleotide sequence.5.3Step3:Review and submitThe last window allows us to change the BLAST options,the location of the imagefile and set the image title,which will appear in the centre of the ring.For the walkthrough configure the third window as:1.Set the image title as“BRIG example image”.2.Hit submit.3.The image will be created in the specified output directory and should looksomething like Figure7.BRIG will format Genbankfiles,run BLAST,parse the results and render the im-age.Thefinal image(Figure7)shows GC Content and Skew,the Genome cover-age,contig boundaries,and the BLAST results against the other E.coli genomes. The results for HS and K12have been collated into a single ring,likewise for UTI89and CFT073.5VISUALISING WHOLE GENOME COMPARISONS17Figure7:Thefinal BRIG imagePRO TIP10:Image settings,like size,fonts,etc can be configured in:Main window>Preferences>Image options..6WORKING WITH A MULTI-FASTA REFERENCE186Working with a Multi-FASTA reference6.1Step1:Load in sequencesThis section is a walk through of how to use BRIG to generate an image using a listof genes in Multi-FASTA format as a reference.The multi-FASTAfile in this ex-ample is a number of virulence genes from enterohemorrhagic and uropathogenic E.coli,which includes EHEC polarfimbraie(ecpA to ecpR),EHEC Locus of En-terocyte Effacement(espF to espG)and the UPEC F1C Fimbraie(focA to focI), which will be compared against the whole genome seqeuences of E.coli strainsO157:H7Sakai,K12MG1665,O126:H7and CFT073.Start a new session in BRIG and load in thefiles from the Chapter568wholeGenomeExamples folderin the unzipped BRIG-Example folder:1.Set the reference sequence as“Ecoli vir.fna”.Users can use the browsebutton to traverse thefile system.2.Set<unzipped BRIG examples folder>/Chapter568wholeGenomeExamplesas the query sequence folder.3.Press“add to data pool”,this should load several items into the pool list.4.Set the output folder as unzipped BRIG-Example folder.5.Make sure the BLAST options box is blank.6.Click“Next”.6WORKING WITH A MULTI-FASTA REFERENCE196.2Step2:Configure rings,annotations and spacer valueThe next step is to configure what information is shown on each concentric ring in BRIG.Figure8is an example of how one of the windows should be set up.There should befive rings.Do the follow for each ring,according to the table below:1.Set legend text for each ring.2.Select the required sequences from the data pool and click“add data”toadd.3.Choose a colour4.Set upper(90)and lower(70)identity thresholds.5.Click“add new ring”and repeat these steps for each new ring.Legend text Required sequences ColourO157:H7E coli O157H7Sakai.gbk172,14,225O126:H7E coli O126.fna255,0,51CFT073E coli CFT073.fna0,0,102K12E coli K12MG1655.fna161,221,231null none ignoreAfter each ring is configured,users need to make the following changes:1.Set the spacerfield to50base pairs.2.Set the ring size of ring5as“2”.PRO TIP11:The Spacerfield determines the number of base pairs to leave between FASTA sequences.The next step is to add the gene annotations,which will be fetched from the Multi-FASTA headers:1.Click Add custom features in the second BRIG window to bring up customannotation window(Figure9).2.Double click“Ring5”.3.Set“input data”as Multi-FASTA.4.Set“colour”as alternating red-blue5.Click add.6WORKING WITH A MULTI-FASTA REFERENCE20Figure8:Ring set-up for Multi-FASTAfile6WORKING WITH A MULTI-FASTA REFERENCE21Figure9:Custom annotation window-adding gene annotations6WORKING WITH A MULTI-FASTA REFERENCE22 This step colours the gaps between FASTA entries,the gaps are calculated from the Multi-FASTAfile(Figure10).For each genome ring,do the following:1.Set“input data”as Multi-FASTA.2.Set“colour”as black3.Check“load gaps only”.4.Click add.The results should be similar to Figure10in the left hand pane.Close the window when this is done.PRO TIP12:A spacer value can be set when using protein sequences from a Genbank/EMBLfile.Figure10:Custom annotation window-adding spacers6WORKING WITH A MULTI-FASTA REFERENCE236.3Step3:Configure image settings and submitThere are a few more steps to complete and then the image isfinished.In the customize ring window:1.Make the following changes in Preferences>Image options(a)Set“show shading”in“Global settings”as false.(b)Set“featureSlot”spacing in“Feature settings”as x-small.2.Return to customize ring window,click“Next”to go to thefinal BRIGconfirmation window3.Set the image title as“Various E.coli virulence genes”and press submit. The output image should be something like Figure11.The alternating red-blue op-tion has automatically alternated the red and blue colours for the gene labels.This option is available whenever a multi-FASTAfile is used as a reference sequence. This same option could be used to show contig or genome scaffold boundaries. This image shows some real biological information very clearly.1.CFT073(UPEC)and K12MG1655(Commensal)do not carry the Locus ofEnterocyte Effacement.These virulence factors are specific to EHEC and EPEC.2.All E.coli shown carry the common pilus(ecpA-R).3.Only CFT073carries the F1Cfimbriae.PRO TIP13:You use protein sequences as a multi-FASTA reference and use blastx to improve alignment accuracy for divergent sequences.6WORKING WITH A MULTI-FASTA REFERENCE24Figure11:Output image from Multi-FASTA walkthrough.This was generated using BLAST+[2],BLAST legacy[1]will produce slightly different results.7VISUALISING GRAPHS AND GENOME ASSEMBLIES25 7Visualising graphs and genome assembliesBRIG can produce any user-specified graph e.g coverage,read mapping,expres-sion data etc.For example,the coverage graph in Figure2was produced from a tab-delimited textfile,with a start,stop and value for that range.BRIG supports.acefiles(produced by Newbler,454/Roche’s propriety as-sembler,and used by PHRAP/Consed)or SAMfiles(used for read mapping and some de-novo assemblers).BRIG has a number of modules for handling assembly information.These tools are:•Contig mapping:BRIG will use BLAST to try and map contigs from an .ace or Multi-FASTAfile onto a reference genome and produce a.graphfile that can show frequency of BLAST hits and the best BLAST hit position of contigs.It will then produce a.graphfile of the frequency of BLAST hits and the best BLAST hit position of contigs and another.graphfile,with the suffix”rep.graph”showing all the other BLAST hits.•Coverage graph:BRIG requires an.ace or.samfile and an output loca-tion(Figure7.1).BRIG will calculate coverage values over a user-defined window and produce a.graphfile in the output folder.This will create a tab-delimited.graphfile,which can be loaded into back BRIG.•Convert graph:A draft genome is usually modified post assembly;adding spacers,reordering contigs,etc.These changes are often not reflected in the original.acefiles BRIG uses to generate coverage graphs.BRIG can use BLAST to align the original assembly output with the newer sequence and map the coverage information to the new sequence.BRIG requires:–Original454AllContigs.fna produced by Newbler.–Graphfile created by BRIG’s“Coverage graph”module,based onNewbler’s acefile.–The modified sequence or another suitable reference genome.BRIG will produce a new.graphfile in the output folder,using thefilename of the originalfile,with“new.graph”appended to the end.To create work with graphfiles:Main window>Modules>Create graphfiles Using graphfiles in BRIG images.graphfiles should visible when users load a directory into the query sequence pool(Figure7.1).Graphs can be treated like any other sequencefile in BRIG;the example from Figure7.1shows a graphfile loaded into thefirst ring of a particular BRIG session.7VISUALISING GRAPHS AND GENOME ASSEMBLIES26 PRO TIP14:Graphfiles cannot be shown on same ring as sequencefiles (protein or nucleotide).7.1Walkthrough for visualising SAMfile mapping coverage. This section will give a worked example of producing a BRIG image show-ing mapping reads coverage from a SAM inputfile.Thefinal image will look like Figure12.This walkthrough requires BRIG examples.zip from the BRIG website(/projects/brig/files/).Unzip this somewhere convenient.The general procedure is tofirst generate the graphfiles from the SAMfile,add additionalfiles to data pool,edit the rings and annotation, then render the image.1.Open a new BRIG session.2.Create the graphfile from the graphfiles modules:Main window>Mod-ules>Create graphfiles.(a)Set drop down to coverage graph,fill infields(Figure7.1).(b)Set Assemblyfile as“Mu50.sam”from the BRIG examples/Chapter7-sam-examples folder.(c)Set Output folder as the location of the Chapter7-sam-examples folder.(d)Window size as“1”..(e)Click Create Graph.This will add the graphfile to the data pool whenit hasfinished.7VISUALISING GRAPHS AND GENOME ASSEMBLIES27Close the coverage graph window and return to thefirst main window.1.Set referencefile as“S.aureus.Mu50-plasmid-AP003367.gbk”from the Chapter7-sam-examples ers can use the browse button to traverse thefilesystem.2.Set<unzipped BRIG examples folder>/Chapter7-sam-examples as the querysequence folder.3.Press“add to data pool”,this should load several items into the pool list.4.Set the output folder as unzipped Chapter7-sam-examples folder.5.Make sure the BLAST options box is blank.Click next to move to the next window to configure the rings and add in annota-tions.1.Create4rings,name them“Mapping Coverage”,“pSK57”,“SAP014A”,“CDS”.2.Ring1Settings:(a)Add“Mu50.sam.graph”from data pool to Ring1.(b)Set graph maximum value as“10”.(c)Set colour as rgb(204,0,0).(d)Set legend title as“Mapping coverage”.(e)Check show red/blue.7VISUALISING GRAPHS AND GENOME ASSEMBLIES283.Ring2Settings:(a)Add“S.aureus.pSK57-plasmid-GQ900493.gbk”from data pool to Ring2.(b)Set colour as rgb(0,0,102).(c)Set legend title as“pSK57”.4.Ring3Settings:(a)Add“S.aureus.SAP014A-plasmid-GQ900379”from data pool to Ring3.(b)Set colour as rgb(102,0,102).(c)Set legend title as“SAP014A”.5.Ring4Settings:(a)Set colour as rgb(0,0,0).(b)Set legend title as“CDS”.7VISUALISING GRAPHS AND GENOME ASSEMBLIES29Click“Add Custom features”.1.Double-click Ring4.2.Set Input data to“Genbank”.3.Set colour to“black”.4.Set Draw feature as“default”.5.Set Genbankfile location to the location of“S.aureus.Mu50-plasmid-AP003367.gbk”.6.Set Feature as“CDS”7.Click add.This will load all the coding sequences from the Genbankfile.These annotations will be drawn as arrows,indicating orientation.Close this window and click next on the second window.1.Set title as“S.aureus Mu50plasmid”.2.Click Submit.This will generate thefinal image,it should look like Figure12.7VISUALISING GRAPHS AND GENOME ASSEMBLIES30Figure12:S.aureus Mu50plasmid,showing read mapping from simulated454 reads,CDSs,and genome comparisons to other S.aureus plasmids,pSK57& SAP014A.Alignments were performed with BLAST+7VISUALISING GRAPHS AND GENOME ASSEMBLIES317.2Walk through for visualising acefile assembly coverage. This section will give a worked example of producing a BRIG image showing assembly coverage read from an acefile.Thefinal image will look like Fig-ure13.This walk through requires BRIG examples.zip from the BRIG website (/projects/brig/files/).Unzip this some-where convenient.The general procedure is tofirst generate the graphfiles from the acefile,con-vert the coverage information to reference sequence if necessary,add additional files to data pool,edit rings and annotation,then render the image.Draft genome sequences are often modified to be consistant with other infor-mation(e.g genome scaffolding,PCR sequencing of gaps)after being initially assembled.This may change the order and size of thefinal genome sequence compared to the original assembly.To show the read coverage from the assembly on thefinal sequence correctly the“Convert graph”module within BRIG can be used to map the coverage infor-mation from the acefile onto the new sequence.This module can also be used to map read coverage from an assembly onto a closely-related reference genome.7VISUALISING GRAPHS AND GENOME ASSEMBLIES32First,produce the coverage graphfile based off the assembly(acefile):1.Open a new BRIG session.2.Create the graphfile from the graphfiles module:Main window>Modules>Create graphfiles.3.Set drop down to coverage graph,fill infields(Figure7.2).(a)Set Assemblyfile as“454-S.aureus.Mu30.ace”from the BRIGEXAMPLE2-ace folder.(b)Set Output folder as the location of the BRIGEXAMPLE2-ace folder.(c)Set window size as“1”.4.Click“Create Graph”.This will add the graphfile to the data pool when ithasfinished.7VISUALISING GRAPHS AND GENOME ASSEMBLIES33 Next,map the coverage generated in the previous graphfile to the modified genome sequence.1.Remain in the“Create custom graph”window:Main window>Modules>Create graphfiles.2.Set drop down to convert graph,fill infields as below.(a)Set Original sequence as“454AllContigs-S.aureus.Mu50.fna”.(b)Set New sequence as“S.aureus.Mu50-plasmid-AP003367.fna”.(c)Set graphfile as“454-S.aureus.Mu50.ace.graph”.(d)Set Output folder as the location of the BRIGEXAMPLE2-ace folder.(e)Window size as“1”.3.Click“Create Graph”.This will add the graphfile to the data pool when ishasfinished.7VISUALISING GRAPHS AND GENOME ASSEMBLIES34Close the“Create custom graph”window and return to the main window.1.Set referencefile as“S.aureus.Mu50-plasmid-AP003367.gbk”from theBRIGEXAMPLE2-ace ers can use the browse button to traverse thefile system.2.Set<unzipped BRIGEXAMPLE2-ace folder>/genomes as the query se-quence folder.3.Press“add to data pool”,this should load several items into the pool list.4.Set the output folder as unzipped BRIGEXAMPLE2-ace folder.5.Make sure the BLAST options box is blank.。

Clue Deduction:an introduction to satisfiability reasoningTodd W.Neller∗,Zdravko Markov,Ingrid RussellAugust10,20051IntroductionClue R 1is a mystery-themed game of deduction.The goal of the game is to be thefirst player to correctly name the contents of a casefile:the murder suspect,the weapon used,and the room the murder took place in.There are6possible suspects,6possible weapons,and9possible rooms,each of which are pictured on a card.One card of each type is chosen randomly and placed in a“casefile”envelope without being revealed to any player.All other cards are dealt out face-down to the players. Each player takes on the identity of one of the suspects.Each player thus begins with private knowledge that their dealt cards are not in the casefile.As the game proceeds,players suggest possible suspect,weapon,and room combinations,and other players refute these suggestions by privately revealing such cards to the suggester.This type of game is called a knowledge game[10],and the basic knowledge of the game may be expressed using propositional logic.In this project,we will study:•Propositional logic syntax(structure)and semantics(meaning),•Conjunctive normal form(CNF),•Resolution theorem proving,and•Application of a SAT solver to Clue.The result will be a reasoning engine which yields“expert”deductions for the play of Clue.Ad-ditionally,we will discuss deductive learning,inductive learning,knowledge acquisition,and possible advanced projects.2Propositional LogicIn this section,we give a brief overview of propositional logic(a.k.a.Boolean logic and sentential logic).For a more complete introduction,we recommend[7,Ch.7].Propositional logic is a simple logic based upon the Boolean values true and false.Many program-mers willfind propositional logic intuitive from exposure to Boolean types and logical operators which occur frequently in programming.In discussing a logic,one needs to address both the syntax(structure)and the semantics(mean-ing)of the language.Just as the syntax of a programming language defines rules for what constitutes a∗Corresponding author:tneller@,Gettysburg College,Department of Computer Science,Campus Box 402,Gettysburg,PA17325-14861A.k.a.Cluedo R in other parts of the worldwell-formed program,the syntax of a logical language defines rules for what constitutes a well-formed sentence of the logic.Just as programming language specifications help the programmer understand the expected behavior of a program,the semantics of a logical language define the meaning of well-formed sentences of the logic.We will present the syntax and semantics of propositional logic one simple piece at a time.The atomic sentence is the simplest fundamental unit of the language.The syntax of an atomic sentence is either the constant true,the constant false,or a symbol.Each symbol is associated with a statement which can be true or false.For example,pi wh may symbolize the statement that“The Mrs. White player is holding the Lead Pipe card.”This statement may be true or false.In general,c p will symbolize the statement“The card c is in place p.”Often,the symbols used for atomic sentences are capital alphabetic characters A,B,C,...,Z,but we are free to choose whichever symbols are convenient.However,just as with commenting variables in a program,it is important to attach meanings to these symbols to ground them in the reality they represent.Example Problem:Suppose that liars always speak what is false,and truth-tellers always speak what is true.Further suppose that Amy,Bob,and Cal are each either a liaror truth-teller.Amy says,“Bob is a liar.”Bob says,“Cal is a liar.”Cal says,“Amy andBob are liars.”Which,if any,of these people are truth-tellers?The atomic sentences for this problem are as follows:•A-Amy is a truth-teller.•B-Bob is a truth-teller.•C-Cal is a truth-teller.Negation(¬,“not”):More complex sentences may be built from these.The negation of A, denoted¬A(read“not”A),means the opposite of A,and thus means“Amy is not a truth-teller.”Given our constraint that Amy is either a truth-teller or liar,this also means“Amy is a liar.”The negation operator¬operates on a single sentence,negating its meaning.Thus for propositional logic sentence s,¬s has the opposite truth value.We may thus express the semantics of¬in a truth table:s¬sfalse truetrue falseA literal is an atomic sentence or its negation.For example,A,¬A,B,¬B,C,and¬C are all literals.Conjunction(∧“and”):We have seen how“Amy is a liar.”can be represented as¬A.Similarly,“Bob is a liar.”can be represented as¬B.To say“Amy and Bob are liars.”is to say that both¬A and¬B are true.We denote this conjunction of sentences as¬A∧¬B(read“not A and not B”).If either or both of the two subsentences¬A or¬B are false,then the conjunction is false as well.The semantics of∧for sentences s1and s2are thus expressed in this truth table:s1s2s1∧s2false false falsefalse true falsetrue false falsetrue true trueDisjunction(∨“or”):Suppose that you are playing Miss Scarlet and Mrs.White suggests that Colonel Mustard committed the murder with the knife in the hall.Mr.Green refutes this suggestion by privately showing one of the cards Mustard,Knife,or Hall privately to Mrs.White.You hold the Mustard card.Thus you know that Mr.Green has either the Knife card or the Hall card.We may represent this knowledge as the disjunction kn gr∨ha gr(read“kn gr or ha gr”).If either or both of the two subsentences¬A or¬B are true,then the disjunction is true as well.The semantics of∨for sentences s1and s2are thus expressed in this truth table:s1s2s1∨s2false false falsefalse true truetrue false truetrue true trueConditional(⇒“implies”):In our truth-teller and liar example,Amy says“Bob is a liar.”.If Amy is a truth-teller(A),then we know that Bob is a liar(¬B).We may represent this knowledge as the conditional(a.k.a.implication)A⇒¬B(read“A implies not B”).If thefirst subsentence s1,the antecedent,is true,and the second subsentence s2,the consequent,is false,then the conditional is false.Otherwise,it is true.The semantics of⇒for sentences s1and s2are thus expressed in this truth table:s1s2s1⇒s2false false truefalse true truetrue false falsetrue true trueBiconditional(⇔“if and only if”):In the previous example,A⇒¬B is not the only fact we represent from Amy saying that Bob is a liar.We also know that if wefind that Bob is,in fact, a liar,then Amy must be a truth-teller.That is¬B⇒bining these facts in a conjunction, we fully represent the knowledge as(A⇒¬B)∧(¬B⇒A).This conjunction of two conditionals with antecedents and consequents reversed has a more compact representation as the biconditional A⇔¬B.If thefirst subsentence s1and the second subsentence s2have the same truth value,the biconditional is true.Otherwise,it is false.The semantics of⇔for sentences s1and s2are thus expressed in this truth table:s1s2s1⇔s2false false truefalse true falsetrue false falsetrue true trueAs with arithmetic expressions,there is an order of precedence of the operators.The negation operator(¬)has highest precedence,followed by∧,∨,⇒,and⇔.Thus,¬A∧B means(¬A)∧BA∨B⇔C means(A∨B)⇔C¬A∨B∧C means(¬A)∨(B∧C)etc.Here,we’ve used parentheses to clarify operator grouping,but parentheses may also be used to group operations as desired(e.g.¬(A∧B)),or improve readability(e.g.(A∧B)∨(C∧D)∨(E∧F)).This is whole of the syntax and semantics may thus be summarized with the following Backus-Naur Form(BNF)grammar,where the Symbol set is chosen and defined by the logician:Sentence→Atomic Sentence|Complex SentenceAtomic Sentence→true|false|SymbolComplex Sentence→¬Sentence|Sentence∧Sentence|Sentence∨Sentence|Sentence⇒Sentence|Sentence⇔Sentence Above,the BNF“→”roughly means“is a”and the BNF“|”means“or”,so that thefirst syntax rule(or production)means“A sentence is either an atomic sentence or a complex sentence.”The set of sentences that represent our knowledge is called our knowledge base.For example,the knowledge base for our liars and truth-tellers problem is:{A⇔¬B,B⇔¬C,C⇔¬A∧¬B}Note that these sentences could all be combined with conjunction in a single sentence which expresses all knowledge of the knowledge base:(A⇔¬B)∧(B⇔¬C)∧(C⇔¬A∧¬B)If we think of our atomic sentence symbols as boolean variables,then an assignment to all variables would be called a truth assignment.A truth assignment which makes a sentence s true is said to satisfy s.This satisfying truth assignment is also called a model of s.Another way to think about it is that each truth assignment is a“world”,and that the models of s are“possible worlds”.If and only if s has a model,s is said to be satisfiable.If and only if s has no model,s is said to be unsatisfiable. If and only if every truth assignment is a model of s,then s is said to be valid or a tautology.Now let us consider two sentences s1and s2.We say that s1entails s2,denoted s1|=s2,if and only if every model of s1is also a model of s2.Sometimes this is expressed by saying that“s2logically follows from s1”.Two sentences s1and s2are logically equivalent if and only if s1|=s2and s2|=s1. 3Conjunctive Normal Form(CNF)Propositional knowledge which is expressed as a conjunction of disjunctions of literals is said to be in conjunctive normal form(CNF).Recall that a literal is an atomic sentence or a negated atomic sentence.A disjunction(or)of literals is often referred to as a clause.Conjunctive normal form is a conjunction(and)of such clauses.Any sentence can be converted to CNF.We will describe the steps of this process and show how the liar and truth-teller example knowledge base may be converted to CNF.1.Eliminate⇔.Replace each occurrence of s1⇔s2with the equivalent(s1⇒s2)∧(s2⇒s1).Thus,the knowledge base{A⇔¬B,B⇔¬C,C⇔¬A∧¬B}may be rewritten as{(A⇒¬B)∧(¬B⇒A),(B⇒¬C)∧(¬C⇒B),(C⇒¬A∧¬B)∧(¬A∧¬B⇒C)} We noted before that the set of knowledge base sentences could all be combined with conjunction in a single equivalent sentence.At any time,we can use this equivalence in the opposite direction to separate conjunctions into separate sentences of the knowledge base:{A⇒¬B,¬B⇒A,B⇒¬C,¬C⇒B,C⇒¬A∧¬B,¬A∧¬B⇒C}2.Eliminate⇒.Replace each occurrence of s1⇒s2with the equivalent¬s1∨s2.With suchreplacements,our knowledge base becomes:{¬A∨¬B,¬¬B∨A,¬B∨¬C,¬¬C∨B,¬C∨¬A∧¬B,¬(¬A∧¬B)∨C}3.Move¬inward.In CNF,negation(¬)only occurs in literals before atomic sentence symbols.All occurrences of¬can either be negated or“moved”inward towards the atomic sentences using three equivalences:de Morgan’s law¬(s1∧s2)≡¬s1∨¬s2¬(s1∨s2)≡¬s1∧¬s2double¬elimination¬¬s≡sUsing these equivalences,our knowledge base is rewritten:{¬A∨¬B,B∨A,¬B∨¬C,C∨B,¬C∨¬A∧¬B,A∨B∨C} The last sentence was rewritten in multiple steps:¬(¬A∧¬B)∨C≡(¬¬A∨¬¬B)∨C≡(A∨¬¬B)∨C≡(A∨B)∨C≡A∨B∨C4.Distribute∨over∧.That is,move disjunction(∨)inward while moving conjunction(∧)outward to form a conjunction of disjunctions.This is accomplished through distributivity of∨:s1∨(s2∧s3)≡(s1∨s2)∧(s1∨s3)(s1∧s2)∨s3≡(s1∨s3)∧(s2∨s3)Thus we can rewrite our knowledge base:{¬A∨¬B,B∨A,¬B∨¬C,C∨B,(¬C∨¬A)∧(¬C∨¬B),A∨B∨C} or{¬A∨¬B,B∨A,¬B∨¬C,C∨B,¬C∨¬A,¬C∨¬B,A∨B∨C} This is sometimes more compactly expressed as a set of a set of literals,where the sets of literals are implicitly understood as clauses(disjunctions)and the set of these is implicitly understood as the knowledge base,a conjunction of known sentences:{{¬A,¬B},{B,A},{¬B,¬C},{C,B},{¬C,¬A},{¬C,¬B},{A,B,C}}It is important to note that a model in CNF is a truth assignment that makes at least one literal in each clause true.4Resolution Theorem ProvingConsider the two clauses{B,A}and{¬B,¬C}of our example CNF knowledge base.Thefirst reads,“Bob is a truth-teller or Amy is a truth-teller.”The second reads,“Bob is not a truth-teller or Cal is not a truth-teller.”Consider what happens according to Bob’s truthfulness:•Bob is not a truth-teller.The second clause is satisfied.Thefirst clause is satisfied if and only if Amy is a truth-teller.•Bob is a truth-teller.Thefirst clause is satisfied.The second clause is satisfied if and only if Cal is not a truth-teller.Since one case or the other holds,we know in any model of both clauses that Amy is a truth-teller or Cal is not a truth-teller.In other words,from clauses{B,A}and{¬B,¬C},we can derive the clause {A,¬C}and add it to our knowledge base.This is a specific application of the resolution rule.In general,we can express the resolution rule as follows:Given a clause{l1,l2,...,l i,A}and {¬A,l i+1,l i+2,...,l n},we can derive the clause{l1,l2,...,l n}.If A is false,one of the otherfirst clause literals must be true.If A is true,one of the other second clause literals must be true.Since A must be either true or false,then at least one of all the other n literals must be true.Not all possible resolution rule derivations are useful.Consider what happens when we apply the resolution rule to thefirst two clauses of our example knowledge base.From{¬A,¬B}and{B,A},we can derive either{¬A,A}or{¬B,B}depending on which atomic sentence we use for the resolution. In either case,we derive a tautology.The clause{¬A,A}is always true.It reads“Amy is not a truth-teller or Amy is a truth-teller.”In order to direct our derivations towards a simple goal,we will perform proof by contradiction2. The basis of this style of proof is the fact that s1|=s2if and only if(s1∧¬s2)is unsatisfiable.Put another way,every truth assignment that makes s1true also makes s2true if and only if there exists no truth assignment where s1is true and s2is false.The application of this principle is simple.Suppose that sentence s1represents our knowledge base,and that we wish to wish to prove that sentence s2follows from s1.We simply add¬s2to our knowledge base and seek to derive a contradiction.We take what we believe must follow,and prove it by showing that the opposite causes a contradiction.This approach is not only effective in human argument,but is important for automated theorem proving as well.Let us use this approach to prove that Cal is a liar(¬C).In addition to the knowledge base,we assume the negation of what we wish to prove(¬¬C,that is C).We will number our clauses to the left.To the right,we will list the clause numbers used to derive the clause by resolution.(1){¬A,¬B}Knowledge base(2){B,A}(3){¬B,¬C}(4){C,B}(5){¬C,¬A}(6){¬C,¬B}(7){A,B,C}(8){C}Assumed negation(9){¬A}(5),(8)Derived clauses(10){B}(2),(9)(11){¬C}(3),(10)(12){}(8),(11)Contradiction!2a.k.a.reductio ad absurdumRecall that at least one literal of each clause must be true for a truth assignment to be a model. This last empty clause has no literals at all and represents a clear contradiction.To see why,consider the resolution that led to it.In(10)and(11)we declare a fact and its negation to be true.The resolution rule leaves us no literals to be made true to satisfy these clauses.A clause with no literals is thus logically equivalent to false.Since we hold each clause to be true,we have in effect shown that false is true.This is a contradiction.Thus it cannot be the case that{C}is true as we had assumed. Thus{¬C}logically follows from our knowledge base.It should be noted that an unsatisfiable knowledge base will derive an empty clause without any need of assumption.One can thus prove any sentence using proof by contradiction and starting with a contradictory knowledge base.If one cannot derive a contradiction in this manner,then there is a satisfying truth assignment for the knowledge base and the assumed negation of the hypothesis one sought to prove.For practice,the reader should perform two resolution proofs by contradiction that•Amy is a liar,and•Bob is a truth-teller.When we derive a sentence s2from sentence s1,we denote it s1 s2.A proof procedure that derives only what is entailed is called sound.A proof procedure that can derive anything that is entailed is called complete.Resolution theorem proving is both sound and complete.5DIMACS CNF FormatResolution theorem proving seeks to answer the question“Is the knowledge base plus the negated hypothesis satisfiable?”There is an intense research effort underway for high-performance satisfiability solvers.Each year,there is a satisfiability software competition.The most common problem input format is the DIMACS CNF Format.We introduce the DIMACS CNF Format by example.Clauses(1)-(8)of the previous proof might be encoded as follows:c Truth-teller and liar problemc1:Amy is a truth-teller.c2:Bob is a truth-teller.c3:Cal is a truth-teller.cp cnf38-1-20210-2-30320-3-10-3-20123030According to the2004SAT competition documentation3,Thefile can start with comments,that is,lines beginning with the character c.3See URL /SATCompetition/2004/format-benchmarks2004.html.Right after the comments,there is the line p cnf nbvar nbclauses indicating that theinstance is in CNF format;nbvar is an upper bound on the largest index of a variableappearing in thefile;nbclauses is the exact number of clauses contained in thefile.Then the clauses follow.Each clause is a sequence of distinct non-null numbers between-nbvar and nbvar ending with0on the same line;it cannot contain the opposite literalsi and-i simultaneously.Positive numbers denote the corresponding variables.Negativenumbers denote the negations of the corresponding variables.Each atomic sentence(called a variable above)is associated with a positive integer.Thus,literals are represented by integers other than0,which is used to terminate clauses.The output when running the SAT solver zChaff4on our example is as follows:Z-Chaff Version:Chaff IISolving f......CONFLICT during preprocessInstance UnsatisfiableRandom Seed Used0Max Decision Level0Num.of Decisions0(Stack+Vsids+Shrinking Decisions)0+0+0Original Num Variables3Original Num Clauses8Original Num Literals16Added Conflict Clauses0Num of Shrinkings0Deleted Conflict Clauses0Deleted Clauses0Added Conflict Literals0Deleted(Total)Literals0Number of Implication3Total Run Time0RESULT:UNSATThe contradiction was found quickly during the preprocessing stage of the solver and it reports that the clauses are unsatisfiable(UNSAT).6SATSolverIn order to aid Java programmers in working with zChaff(written in C++)we have created a simple class called SATSolver,described in this section.We begin by creating and initializing ArrayList s5to hold clauses which are represented as int arrays.Each int array is a clause,a sequence of non-zero integers much like the DIMACS CNF format clause lines,but without0termination.We divide the clauses into two lists:clauses and queryClauses.The reason is that our expected usage is to have a monotonically growing knowledge base alongside a temporary and often changing 4See URL /%7Echaff/zchaff.html.5Java1.5styleset of query clauses.Initializefield variables ≡public ArrayList<int[]>clauses=new ArrayList<int[]>();public ArrayList<int[]>queryClauses=new ArrayList<int[]>();We thus have simple methods to allow the user to add single clauses or remove all clauses from either list.Side note:This format of presenting code in chunks is called literate programming and is due to Donald Knuth.Code will be presented in named chunks that will appear inserted within other chunk definitions.The source document is used not only to generate the output you are now reading,but also to generate the example code.In this way,the code presented is both consistent with the example code,and has been tested for correctness.Methods to add/clear clauses ≡public void addClause(int[]clause){clauses.add((int[])clause.clone());}public void clearClauses(){clauses.clear();}public void addQueryClause(int[]clause){queryClauses.add((int[])clause.clone());}public void clearQueryClauses(){queryClauses.clear();}When making a query to test the satisfiability of the clauses and queryClauses combined,we compute the number of variables6and clauses,write a DIMACS CNF queryfile,and execute zChaffas an external process.The result returned will be true if the combined clauses are satisfiable,and false otherwise. Query zChafffor satisfiability ≡public boolean makeQuery(){try{Compute max query variableWrite DIMACS CNF format queryfileExecute external zChaffprocess and scan result}catch(Exception e){System.out.println(e);}return false;}6Actually,we compute the maximum absolute index.Here we build the list allClauses which has both the knowledge base clauses and query clauses combined.We iterate through these lists7,and compute the maximum absolute value of a literal.Compute max query variable ≡int maxVar=0;ArrayList<int[]>allClauses=new ArrayList<int[]>(clauses);allClauses.addAll(queryClauses);for(int[]clause:allClauses)for(int literal:clause)maxVar=Math.max(Math.abs(literal),maxVar);Next,we write allClauses out to afile f in DIMACS CNF format.Write DIMACS CNF format queryfile ≡PrintStream out=new PrintStream(new File("f"));out.println("c This DIMACS format CNF file was generated by SatSolver.java");out.println("c Do not edit.");out.println("p cnf"+maxVar+""+allClauses.size());for(int[]clause:allClauses){for(int literal:clause)out.print(literal+"");out.println("0");}out.close();Finally,we use Java’s Runtime environment to execute zChaff.Scanning the input stream8,we skip to the RESULT,and return whether or not the clauses were satisfiable.Execute external zChaffprocess and scan result ≡Process process=Runtime.getRuntime().exec("zchaff f");Scanner sc=new Scanner(process.getInputStream());sc.findWithinHorizon("RESULT:",0);String result=sc.next();sc.close();process.waitFor();return result.equals("SAT");Often,the user will simply want to know at a given point if a literal can be proved true/false or not. For this,we define constants as return codes...Define constants ≡public static final int FALSE=-1;public static final int UNKNOWN=0;public static final int TRUE=1;...and provide code which performs the queries necessary to test a given literal.7Java1.5style8using Java1.5’s Scanner classTest a single literal ≡public int testLiteral(int literal){int result=UNKNOWN;clearQueryClauses();int[]clauseT={literal};addQueryClause(clauseT);if(!makeQuery())result=FALSE;else{clearQueryClauses();int[]clauseF={-literal};addQueryClause(clauseF);if(!makeQuery())result=TRUE;}clearQueryClauses();return result;}Here we provide a test case in which we take our liar and truth-teller example and apply the SATSolver.Test case ≡public static void main(String[]args){//Liar and truth-teller example test code:int[][]clauses={{-1,-2},{2,1},{-2,-3},{3,2},{-3,-1},{-3,-2},{1,2,3}};SATSolver s=new SATSolver();for(int i=0;i<clauses.length;i++)s.addClause(clauses[i]);System.out.println("Knowledge base is satisfiable:"+s.makeQuery());System.out.print("Is Cal a truth-teller?");int result=s.testLiteral(3);if(result==FALSE)System.out.println("No.");else if(result==TRUE)System.out.println("Yes.");elseSystem.out.println("Unknown.");}Putting all these parts together,the entire SATSolver.java is as follows:SATSolver.java ≡import java.io.*;import java.util.*;public class SATSolver{Define constantsInitializefield variablesMethods to add/clear clausesQuery zChafffor satisfiabilityTest a single literalTest case}This code may be used to efficiently solve the exercises of the next section.7ExercisesFor each of the following problems,there are four exercises:(a)Express all relevant problem facts as a propositional logic knowledge base.Clearly explain themeaning of your propositional symbols.(b)Convert the propositional logic knowledge base to CNF.(c)Use resolution theorem proving to solve the problem.(d)Solve the problem computationally with a SAT solver.Exercise(a)should precede(b)which should in turn precede(c)and(d).Problems:1.Horn Clauses:(from[7,Exercise7.9])If the unicorn is mythical,then it is immortal,but ifit is not mythical,then it is a mortal mammal.If the unicorn is either immortal or a mammal, then it is horned.The unicorn is magical if it is horned.(a)Can we prove that the unicorn is mythical?(b)Can we prove that the unicorn is magical?(c)Can we prove that the unicorn is horned?2.Liars and Truth-tellers1:(adapted from OSSMB982-12)Three people,Amy,Bob,and Cal,are each either a liar or a truth-teller.Assume that liars always lie,and truth-tellers always tell the truth.•Amy says,“Cal and I are truthful.”•Bob says,“Cal is a liar.”•Cal says,“Bob speaks the truth or Amy lies.”What can you conclude about the truthfulness of each?9Ontario Secondary School Mathematics Bulletin3.Liars and Truth-tellers2:(adapted from OSSMB83-11)Three people,Amy,Bob,and Cal,are each either a liar or a truth-teller.Assume that liars always lie,and truth-tellers always tell the truth.•Amy says,“Cal is not honest.”•Bob says,“Amy and Cal never lie.”•Cal says,“Bob is correct.”What can you conclude about the truthfulness of each?4.Robbery and a Salt:(from OMG1022.1.1)The salt has been stolen!Well,it was found thatthe culprit was either the Caterpillar,Bill the Lizard or the Cheshire Cat.The three were tried and made the following statements in court:CATERPILLAR:Bill the Lizard ate the salt.BILL THE LIZARD:That is true!CHESHIRE CAT:I never ate the salt.As it happened,at least one of them lied and at least one told the truth.Who ate the salt?5.Multiple Choice:(adapted from CRUX11357)In a certain multiple-choice test,one of thequestions was illegible,but the choice of answers was clearly printed.(a)All of the below.(b)None of the below.(c)All of the above.(d)One of the above.(e)None of the above.(f)None of the above.Assuming that more than one answer may be true,divide answers into three groups:•those that are necessarily true,•those that are necessarily false,and•those that could be true or false.How many different possible ways are there to consistently circle true subset(s)of answers?List the subset(s).6.A Sanctum for the Good En-doors-ment:(from CRUX357)There are four doors X,Y,Zand W leading out of the Middle Sanctum.At least one of them leads to the Inner Sanctum.If you enter a wrong door,you will be devoured by afierce dragon.Well,there were eight priests A,B,C,D,E,F,G and H,each of whom is either a knight or a knave.(Knights always tell the truth and knaves always lie.)They made the following statements to the philosopher:A:X is a good door.B:At least one of the doors Y or Z is good.C:A and B are both knights.D:X and Y are both good doors.10Ontario Mathematical Gazette11Crux Mathematicorum。

英语作文里的逻辑如何体现Logic is an essential component of writing an effective and persuasive essay. It is the backbone of a well-structured essay that presents a clear and concise argument. In this essay, I will discuss how logic is reflected in English writing and provide a high-quality imitation of the most downloaded essay online.Firstly, logic is reflected in the structure of an essay. A well-structured essay follows a logical sequenceof ideas that leads the reader from the introduction to the conclusion. The introduction should provide background information and set the tone for the essay. The body paragraphs should be organized in a logical order that supports the thesis statement. Each paragraph shouldcontain a topic sentence that introduces the main idea and evidence that supports it. The conclusion should summarize the main points and restate the thesis statement.Secondly, logic is reflected in the use of evidence. Apersuasive essay should provide evidence that supports the argument. The evidence should be relevant, reliable, and presented in a logical manner. The writer should use facts, statistics, and examples to support their argument. The evidence should be presented in a logical order that supports the thesis statement.Thirdly, logic is reflected in the use of language. The language used in an essay should be clear, concise, and precise. The writer should avoid using vague or ambiguous language that can confuse the reader. The writer should use words and phrases that are appropriate for the audience and the purpose of the essay. The writer should also use transitional words and phrases to connect ideas and create a logical flow.Now, let me provide a high-quality imitation of the most downloaded essay online, reflecting the use of logicin English writing.The topic of my essay is the importance of exercise for a healthy lifestyle. The essay will follow a logicalstructure that includes an introduction, body paragraphs, and a conclusion. The body paragraphs will provide evidence that supports the argument that exercise is essential for a healthy lifestyle.Introduction:Exercise is an essential component of a healthy lifestyle. It has numerous benefits that include weight loss, improved cardiovascular health, and increased energy levels. In this essay, I will discuss the importance of exercise for a healthy lifestyle.Body Paragraph 1:Exercise is an effective way to maintain a healthy weight. It burns calories and increases metabolism, which helps to reduce body fat. In addition, exercise can help to prevent obesity, which is a major risk factor for many chronic diseases.Body Paragraph 2:Exercise improves cardiovascular health. It strengthens the heart and improves blood flow, which reduces the risk of heart disease and stroke. Regular exercise can also lower blood pressure and cholesterol levels, which are other risk factors for cardiovascular disease.Body Paragraph 3:Exercise increases energy levels and improves mood. It releases endorphins, which are natural mood boosters. Regular exercise can also improve sleep quality, which is essential for overall health and wellbeing.Conclusion:In conclusion, exercise is essential for a healthy lifestyle. It has numerous benefits that include weight loss, improved cardiovascular health, and increased energy levels. By incorporating exercise into our daily routine, we can improve our overall health and wellbeing.。

java英⽂参考⽂献java英⽂参考⽂献汇编 导语：Java是⼀门⾯向对象编程语⾔，不仅吸收了C++语⾔的各种优点，还摒弃了C++⾥难以理解的多继承、指针等概念，因此Java语⾔具有功能强⼤和简单易⽤两个特征。

下⾯⼩编为⼤家带来java英⽂参考⽂献，供各位阅读和参考。

java英⽂参考⽂献⼀： [1]Irene Córdoba-Sánchez,Juan de Lara. Ann: A domain-specific language for the effective design and validation of Java annotations[J]. Computer Languages, Systems & Structures,2016,:. [2]Marcelo M. Eler,Andre T. Endo,Vinicius H.S. Durelli. An Empirical Study to Quantify the Characteristics of Java Programs that May Influence Symbolic Execution from a Unit Testing Perspective[J]. The Journal of Systems & Software,2016,:. [3]Kebo Zhang,Hailing Xiong. A new version of code Java for 3D simulation of the CCA model[J]. Computer Physics Communications,2016,:. [4]S. Vidal,A. Bergel,J.A. Díaz-Pace,C. Marcos. Over-exposed classes in Java: An empirical study[J]. Computer Languages, Systems & Structures,2016,:. [5]Zeinab Iranmanesh,Mehran S. Fallah. Specification and Static Enforcement of Scheduler-Independent Noninterference in a Middleweight Java[J]. Computer Languages, Systems & Structures,2016,:. [6]George Gabriel Mendes Dourado,Paulo S Lopes De Souza,Rafael R. Prado,Raphael Negrisoli Batista,Simone R.S. Souza,Julio C. Estrella,Sarita M. Bruschi,Joao Lourenco. A Suite of Java Message-Passing Benchmarks to Support the Validation of Testing Models, Criteria and Tools[J]. Procedia Computer Science,2016,80:. [7]Kebo Zhang,Junsen Zuo,Yifeng Dou,Chao Li,Hailing Xiong. Version 3.0 of code Java for 3D simulation of the CCA model[J]. Computer Physics Communications,2016,:. [8]Simone Hanazumi,Ana C.~V. de Melo. A Formal Approach to Implement Java Exceptions in Cooperative Systems[J]. The Journal of Systems & Software,2016,:. [9]Lorenzo Bettini,Ferruccio Damiani. Xtraitj : Traits for the Java Platform[J]. The Journal of Systems & Software,2016,:. [10]Oscar Vega-Gisbert,Jose E. Roman,Jeffrey M. Squyres. Design and implementation of Java bindings in OpenMPI[J]. Parallel Computing,2016,:. [11]Stefan Bosse. Structural Monitoring with Distributed-Regional and Event-based NN-Decision Tree Learning Using Mobile Multi-Agent Systems and Common Java Script Platforms[J]. Procedia Technology,2016,26:. [12]Pablo Piedrahita-Quintero,Carlos Trujillo,Jorge Garcia-Sucerquia. JDiffraction : A GPGPU-accelerated JAVA library for numerical propagation of scalar wave fields[J]. Computer Physics Communications,2016,:. [13]Abdelhak Mesbah,Jean-Louis Lanet,Mohamed Mezghiche. Reverse engineering a Java Card memory management algorithm[J]. Computers & Security,2017,66:. [14]G. Bacci,M. Bazzicalupo,A. Benedetti,A. Mengoni. StreamingTrim 1.0: a Java software for dynamic trimming of 16S rRNA sequence data from metagenetic studies[J]. Mol Ecol Resour,2014,14（2）：. [15]Qing‐Wei Xu,Johannes Griss,Rui Wang,Andrew R. Jones,Henning Hermjakob,Juan Antonio Vizcaíno. jmzTab: A Java interface to the mzTab data standard[J]. Proteomics,2014,14（11）：. [16]Rody W. J. Kersten,Bernard E. Gastel,Olha Shkaravska,Manuel Montenegro,Marko C. J. D. Eekelen. ResAna: a resource analysis toolset for （real‐time） JAVA[J]. Concurrency Computat.: Pract. Exper.,2014,26（14）：. [17]Stephan E. Korsholm,Hans S?ndergaard,Anders P. Ravn. A real‐time Java tool chain for resource constrained platforms[J]. Concurrency Computat.: Pract. Exper.,2014,26（14）：. [18]M. Teresa Higuera‐Toledano,Andy Wellings. Introduction to the Special Issue on Java Technologies for Real‐Time and Embedded Systems: JTRES 2012[J]. Concurrency Computat.: Pract. Exper.,2014,26（14）：. [19]Mostafa Mohammadpourfard,Mohammad Ali Doostari,Mohammad Bagher Ghaznavi Ghoushchi,Nafiseh Shakiba. Anew secure Internet voting protocol using Java Card 3 technology and Java information flow concept[J]. Security Comm. Networks,2015,8（2）：. [20]Cédric Teyton,Jean‐Rémy Falleri,Marc Palyart,Xavier Blanc. A study of library migrations in Java[J]. J. Softw. Evol. and Proc.,2014,26（11）：. [21]Sabela Ramos,Guillermo L. Taboada,Roberto R. Expósito,Juan Touri?o. Nonblocking collectives for scalable Java communications[J]. Concurrency Computat.: Pract. Exper.,2015,27（5）：. [22]Dusan Jovanovic,Slobodan Jovanovic. An adaptive e‐learning system for Java programming course, based on Dokeos LE[J]. Comput Appl Eng Educ,2015,23（3）：. [23]Yu Lin,Danny Dig. A study and toolkit of CHECK‐THEN‐ACT idioms of Java concurrent collections[J]. Softw. Test. Verif. Reliab.,2015,25（4）：. [24]Jonathan Passerat?Palmbach,Claude Mazel,David R. C. Hill. TaskLocalRandom: a statistically sound substitute to pseudorandom number generation in parallel java tasks frameworks[J]. Concurrency Computat.: Pract.Exper.,2015,27（13）：. [25]Da Qi,Huaizhong Zhang,Jun Fan,Simon Perkins,Addolorata Pisconti,Deborah M. Simpson,Conrad Bessant,Simon Hubbard,Andrew R. Jones. The mzqLibrary – An open source Java library supporting the HUPO‐PSI quantitative proteomics standard[J]. Proteomics,2015,15（18）：. [26]Xiaoyan Zhu,E. James Whitehead,Caitlin Sadowski,Qinbao Song. An analysis of programming language statement frequency in C, C++, and Java source code[J]. Softw. Pract. Exper.,2015,45（11）：. [27]Roberto R. Expósito,Guillermo L. Taboada,Sabela Ramos,Juan Touri?o,Ramón Doallo. Low‐latency Java communication devices on RDMA‐enabled networks[J]. Concurrency Computat.: Pract. Exper.,2015,27（17）：. [28]V. Serbanescu,K. Azadbakht,F. Boer,C. Nagarajagowda,B. Nobakht. A design pattern for optimizations in data intensive applications using ABS and JAVA 8[J]. Concurrency Computat.: Pract. Exper.,2016,28（2）：. [29]E. Tsakalos,J. Christodoulakis,L. Charalambous. The Dose Rate Calculator （DRc） for Luminescence and ESR Dating-a Java Application for Dose Rate and Age Determination[J]. Archaeometry,2016,58（2）：. [30]Ronald A. Olsson,Todd Williamson. RJ: a Java package providing JR‐like concurrent programming[J]. Softw. Pract. Exper.,2016,46（5）：. java英⽂参考⽂献⼆： [31]Seong‐Won Lee,Soo‐Mook Moon,Seong‐Moo Kim. Flow‐sensitive runtime estimation: an enhanced hot spot detection heuristics for embedded Java just‐in‐time compilers [J]. Softw. Pract. Exper.,2016,46（6）：. [32]Davy Landman,Alexander Serebrenik,Eric Bouwers,Jurgen J. Vinju. Empirical analysis of the relationship between CC and SLOC in a large corpus of Java methods and C functions[J]. J. Softw. Evol. and Proc.,2016,28（7）：. [33]Renaud Pawlak,Martin Monperrus,Nicolas Petitprez,Carlos Noguera,Lionel Seinturier. SPOON : A library for implementing analyses and transformations of Java source code[J]. Softw. Pract. Exper.,2016,46（9）：. [34]Musa Ata?. Open Cezeri Library: A novel java based matrix and computer vision framework[J]. Comput Appl Eng Educ,2016,24（5）：. [35]A. Omar Portillo‐Dominguez,Philip Perry,Damien Magoni,Miao Wang,John Murphy. TRINI: an adaptive load balancing strategy based on garbage collection for clustered Java systems[J]. Softw. Pract. Exper.,2016,46（12）：. [36]Kim T. Briggs,Baoguo Zhou,Gerhard W. Dueck. Cold object identification in the Java virtual machine[J]. Softw. Pract. Exper.,2017,47（1）：. [37]S. Jayaraman,B. Jayaraman,D. Lessa. Compact visualization of Java program execution[J]. Softw. Pract. Exper.,2017,47（2）：. [38]Geoffrey Fox. Java Technologies for Real‐Time and Embedded Systems （JTRES2013）[J]. Concurrency Computat.: Pract. Exper.,2017,29（6）：. [39]Tórur Biskopst? Str?m,Wolfgang Puffitsch,Martin Schoeberl. Hardware locks for a real‐time Java chip multiprocessor[J]. Concurrency Computat.: Pract. Exper.,2017,29（6）：. [40]Serdar Yegulalp. JetBrains' Kotlin JVM language appeals to the Java faithful[J]. ,2016,:. [41]Ortin, Francisco,Conde, Patricia,Fernandez-Lanvin, Daniel,Izquierdo, Raul. The Runtime Performance of invokedynamic: An Evaluation with a Java Library[J]. IEEE Software,2014,31（4）：. [42]Johnson, Richard A. JAVA DATABASE CONNECTIVITY USING SQLITE: A TUTORIAL[J]. Allied Academies International Conference. Academy of Information and Management Sciences. Proceedings,2014,18（1）：. [43]Trent, Rod. SQL Server Gets PHP Support, Java Support on the Way[J]. SQL Server Pro,2014,:. [44]Foket, C,De Sutter, B,De Bosschere, K. Pushing Java Type Obfuscation to the Limit[J]. IEEE Transactions on Dependable and Secure Computing,2014,11（6）：. [45]Parshall, Jon. Rising Sun, Falling Skies: The Disastrous Java Sea Campaign of World War II[J]. United States Naval Institute. Proceedings,2015,141（1）：. [46]Brunner, Grant. Java now pollutes your Mac with adware - here's how to uninstall it[J]. ,2015,:. [47]Bell, Jonathan,Melski, Eric,Dattatreya, Mohan,Kaiser, Gail E. Vroom: Faster Build Processes for Java[J]. IEEE Software,2015,32（2）：. [48]Chaikalis, T,Chatzigeorgiou, A. Forecasting Java Software Evolution Trends Employing Network Models[J]. IEEE Transactions on Software Engineering,2015,41（6）：. [49]Lu, Quan,Liu, Gao,Chen, Jing. Integrating PDF interface into Java application[J]. Library Hi Tech,2014,32（3）：. [50]Rashid, Fahmida Y. Oracle fixes critical flaws in Database Server, MySQL, Java[J]. ,2015,:. [51]Rashid, Fahmida Y. Library misuse exposes leading Java platforms to attack[J]. ,2015,:. [52]Rashid, Fahmida Y. Serious bug in widely used Java app library patched[J]. ,2015,:. [53]Odeghero, P,Liu, C,McBurney, PW,McMillan, C. An Eye-Tracking Study of Java Programmers and Application to Source Code Summarization[J]. IEEE Transactions on Software Engineering,2015,41（11）：. [54]Greene, Tim. Oracle settles FTC dispute over Java updates[J]. Network World （Online） [55]Rashid, Fahmida Y. FTC ruling against Oracle shows why it's time to dump Java[J]. ,2015,:. [56]Whitwam, Ryan. Google plans to remove Oracle's Java APIs from Android N[J]. ,2015,:. [57]Saher Manaseer,Warif Manasir,Mohammad Alshraideh,Nabil Abu Hashish,Omar Adwan. Automatic Test Data Generation for Java Card Applications Using Genetic Algorithm[J]. Journal of Software Engineering andApplications,2015,8（12）：. [58]Paul Venezia. Prepare now for the death of Flash and Java plug-ins[J]. ,2016,:. [59]PW McBurney,C McMillan. Automatic Source Code Summarization of Context for Java Methods[J]. IEEE Transactions on Software Engineering,2016,42（2）：. java英⽂参考⽂献三： [61]Serdar Yegulalp,Serdar Yegulalp. Sputnik automates code review for Java projects on GitHub[J].,2016,:. [62]Fahmida Y Rashid,Fahmida Y Rashid. Oracle security includes Java, MySQL, Oracle Database fixes[J]. ,2016,:. [63]H M Chavez,W Shen,R B France,B A Mechling. An Approach to Checking Consistency between UML Class Model and Its Java Implementation[J]. IEEE Transactions on Software Engineering,2016,42（4）：. [64]Serdar Yegulalp,Serdar Yegulalp. Unikernel power comes to Java, Node.js, Go, and Python apps[J]. ,2016,:. [65]Yudi Zheng,Stephen Kell,Lubomír Bulej,Haiyang Sun. Comprehensive Multiplatform Dynamic Program Analysis for Java and Android[J]. IEEE Software,2016,33（4）：. [66]Fahmida Y Rashid,Fahmida Y Rashid. Oracle's monster security fixes Java, database bugs[J]. ,2016,:. [67]Damian Wolf,Damian Wolf. The top 5 Java 8 features for developers[J]. ,2016,:. [68]Jifeng Xuan,Matias Martinez,Favio DeMarco,Maxime Clément,Sebastian Lamelas Marcote,Thomas Durieux,Daniel LeBerre. Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs[J]. IEEE Transactions on Software Engineering,2017,43（1）：. [69]Loo Kang Wee,Hwee Tiang Ning. Vernier caliper and micrometer computer models using Easy Java Simulation and its pedagogical design features-ideas for augmenting learning with real instruments[J]. Physics Education,2014,49（5）：. [70]Loo Kang Wee,Tat Leong Lee,Charles Chew,Darren Wong,Samuel Tan. Understanding resonance graphs using Easy Java Simulations （EJS） and why we use EJS[J]. Physics Education,2015,50（2）：.【java英⽂参考⽂献汇编】相关⽂章：1.2.3.4.5.6.7.8.。

嘲}|{|；㈨刚㈣蟛|{；}|㈣㈨劁㈨㈣臻鳓引㈦㈦鳓；川㈦鲻嘲㈦燃嘲l i|}f引嘲㈤|j l}|㈣黝；|iil嘲髑獭i；{}；㈦瞩㈣}ij l|强{!|{{i}{ij㈣||!}|黝j}il{嬲劐；DOI：10．3969／j．issn．1003-1154．2015．02．043消费者亲环境行为的影响因素和干预策略——发达国家的相关文献述评口王建明王丛丛(浙江财经大学工商管理学院，浙江杭州310018)[摘要】环境质量的好坏很大程度上取决于消费者的行为模式。

通过亲环境行为的认定、亲环境行为的影响因素，以及干预策略三个方面，对发达国家已有的亲环境行为研究文献进行系统述评，总结现有研究存在的不足，提出未来的研究建议。

[关键词】亲环境行为；环境友好；消费者；环境[中图分类号]F063．2；X196[文献标识码】A[文章编号】1003-1154(2015)02-0127--03一、亲环境行为的认定二、亲环境行为的影响因素亲环境行为又被称之为环境友好行为，不同的消费者的亲环境行为受到多种复杂因素的作学者对此有不同的理解。

Hines等认为亲环境行为用。

从经济人假设出发，消费者受到成本和收益等个人是一种有意识的行为，它以个人责任感和价值观为利益所调节；从社会人假设出发，消费者还受到社会规基础，目的在于避免或解决各种环境问题；Sivek和范、价值观和态度等因素的影响。

从20世纪90年代开始，Hungerford心】将亲环境行为定义为，对自然资源进行可国外学者们主要是从动机因素、情境因素和惯性因素持续地或有节制地开发、使用的个人或组织行为；Stem 这三个角度来研究亲环境行为的影响因素。

口坨人为，以保护环境或者阻止环境恶化所表现或塑造的(一)动机因素人类行为或活动是亲环境行为。

本文认为，亲环境行为1．成本和收益是指消费者在日常生活实践中所表现出来的对环境产对环境行为的研究都基于同一个假说——消费生积极作用并与环境直接相关的友好行为。

abol=to do away with废除abolish废除ab-sum=not present离开absent不在abyssys=bottom底abyss深渊ac=an oak栎属植物acorn橡树子acer=a field原野acre英亩acer=sharp尖锐的acerbity酸acidus=sour发酸acid酸acu=sharpen削尖acumen敏锐aedes=a house住宅edifice屋宇aequus=equal相等的equal平等的aer=air空气aerate充气aer=before以前ere在…之前aesth=feel发觉aesthete审美家aestimo=to value估价esteem尊重aeternus=of endless duration永久的eternity永恒aevum=age年龄coeval同年代的afen=evening晚上eve黄昏afre=always永远ever永远ag=act行动agency力量agan=to own承认owe感谢aggelos=a messenger通信员angel天使agger=heap堆积exaggerate夸大ago=lead引导pedagog教师ago=to do做agile敏捷的agon=contest争夺agonal濒死agr=field原野agrarian土地的aither=burn烧ether太空alb=white白的alb白长袍ali=another又一alias别名alo=to nourish营养aliment食物alt=high高的alter祭坛alter=the other of tow两者的另外一个alter改变ambio=I go round about我在周围到处走ambition抱负ambulo=I walk我步行preamble序言amo=I love我爱amiable可亲的ampl=wide广大ample广大的an=one一个any什么ancestre=one who goes before走在先前的人ancestor祖宗ancien=old古代的ancient古代的anemos=wind风enemograph风速计angl=a corner角angle角ango=to choke呛anguish苦恼anim=breath呼吸animal动物anism=mind心animosity敌意ann=year年annual周年的answer=to declare in opposition回答answer up应对迅速anth=flower花anthology选集anthropos=man人anthropocentric以人类为宇宙中心的antiqunus=ancient古代的antic古怪的apell=call by name叫appeal要求aper=open打开aperture口apt=fit配合apt合适的aqu=water水aqua水ar=plow犁arable耕地arbiter=a judge法官arbitrate仲裁arbor=a tree树arbor棚架arc=a bow弯曲arc弧ardeo=I burn我烧ardent热心的are=circle环circular环形的area=vacant place空地area地面arena=sound活动场所argent=silver银argent银arguo=I prove我证明argue证明arid=dry干旱的arid干旱的arktos=bear熊星arctician北极探险者arm=arms兵器arms兵器ars=art艺术art艺术asketikos=ascetic修士ascetic苦行的aspectus=look外表aspect样子asper=rough粗asperate使粗糙asthmamatos=asthma喘息asthma气喘astigmamatosic=astigmatic散光的astigmatic散光的asulon=refuge庇护asylum收容所athletes=athlete运动员athlete运动员atmos=air气atmograph呼吸气息计atrox=savage野蛮的atrocious凶恶的aud=hear听闻audible可闻的audax=bold大胆的audacious大胆的augeo=increase增加augment增加aur=gold金auriferous含金的austeros=austere严厉的austere严厉的av=bird鸟aviary鸟屋ax=axle轴axial轴的sacer=sacred神圣的sacred神的sagax=wise明智的sage贤明的sal=salt盐saline咸的salio=to leap跳跃salient突出的salus=safety安全salute行礼salvus=safe平安的save救sanctus=holy神圣的saint圣者sanguis=blood血sanguine乐观的sanus=sound结实sane健全的sarc=flesh肉sarcasm讽刺satis=enough足够satisfy满足scadan=to divide分开divide分scando=I climb我攀登scan细看sceadu=shade荫shadow阴影scealu=scale or shell壳shell壳sceofan=to shove推shove推sceotan=to throw投throw投sceran=to cut切cut切schema=form概念schema纲要scindo=to cut砍rescind取消scio=I know我知道science科学scribo=I write我写scribe作家scrutor=I search into我调查scrutiny细看seco=to cut切section切断sedeo=to sit坐sedentary坐着的seism=earthquake地震seism地震selen=moon月Selene塞勒涅semen=seed种子seminal精液的senex=old老senile年老的sentio=to feel感觉sense意识seothan=to boil汽化sod草皮sequor=to follow跟随sequence连续sero=to set in row排成行series丛书servio=I serve我为…服务serf农奴servo=I keep我保持conservative保存的settan=to sit坐sit坐落severus=severe严厉的severe严肃的signum=a mark sign符号similes=like相似的similar相似的sinico=China中国Sinology汉学sinus=a bend弯道sinuous曲折的sisto=I stop我停止assist援助sitio=food食物sitology食物学skandalon=snare圈套scandal丑事skene=tent舞台scene舞台skeptikos=thoughtful思考的sceptic怀疑论者skeptron=staff杖sceptre君主的节杖skhisma=split分裂schism分裂skhole=leisure空闲school学校skopeo=I see我看见scope眼界slagan=slay杀害slay杀害slawian=to become slow变得慢的slow缓慢的sleac=lax宽松的loose松sledge=sledgehammer重大的slipan=to slip外衣slip失足snake蛇snail蜗牛snican=to creep爬行sneak潜行socius=a companion伙伴social社会的sol=the sun太阳solar太阳的solidus=firm坚定的solid固定solor=I comfort我安慰solace安慰solus=alone单独的sole单独的solvo=to loosen放松solve解决somnus=sleep睡眠somnolent想睡的sono=I sound我发声sonorous响亮的sophos=wise有智慧的sophism诡辩spargo=to spread扩散sparsely稀少地specio=to look看spectacle景象spell=a story消息spell拼字spero=I hope我希望despair绝望spiro=I breathe我呼吸respire呼吸splendeo=I shine我把…弄光亮splendour光辉spondeo=to promise许诺respond回答statuo=I set up我建立statue雕像stearc=stiff硬的stark严格的stede=place地方stead替代stella=a star星stellar星的stello=send forth送出apostle使徒steoran=to steer驾驶steerer驾驶者stereo=solid坚固的stere立方米sterno=to strew撒播prostrate俯卧stician=to stick刺stick枝条stigan=to climb登stair楼梯stilla=a drop一滴distil蒸馏stinguo=to quench扑灭distinguish区别stizein=to prick扎stigma烙印sto=to stand立stable稳定的stomato=mouth口的stomatic口的stow=a place地方stow收藏strategema=army军队stratagem计策strican=to strike打strike camp开拔stringo=I bind我捆紧stringent严格的strophe=I turn我转strophe节struo=I build我建造structure结构studeo=I am eager我渴望study学习stupeo=I am struck senseless我被打昏了stupid愚蠢的suadeo=I advise我忠告persuade说服suavis=sweet甜的suave温和的summus=highest最高的sum总数sumo=I take我取拿assume假定sundrian=to part一部分sunder分开surgo=to rise升起surge汹涌swapan=to sweep扫swoop攫取swerian=to declare宣布declare宣布swettan=to die死die to shame恬不知耻tabula=a board木板table桌子taceo=I am silent我沉默tacit缄默taecan=to show显示show显示tango=to touch摸tact机智tardus=slow慢的tardy慢的taxis=arrangement排列syntax句法techne=art技术technic技术的tego=to cover掩盖integument覆盖物tellan=to tell告诉tell说temncin=to cut切anatomic解剖的tempero=I combine properly我恰当地联合. temper锻炼tempus=time时间temporal暂时的tendo=to stretch延伸tension紧张teneo=to hold保持tenable可防守的tento=I try我试试tempt引诱tenuis=thin瘦的tenuity纤细teohan=to draw拉draw接terminus=a boundary边界term期teroI rub我擦去trite用坏了的terra=the earth地球terrestrial地球上的terreo=I frighten我施加威胁terror恐怖testis=a witness证明test试验texo=to weave编织text原文thaec=a roof车顶the roof of heaven天穹the=a god神theocracy神权政治theatron=behold见到theatre戏院thencan=to think想think思索therm=warm温thermae温泉thesis=put提出thesis论题thincan=to seem似乎methinks我想thrall=a slave奴隶slave奴隶thuma=a thumb拇指thumbs down糟糕thyrel=an opening开nostril鼻孔942 time. o=I fear我害怕timid胆怯的tingo=to wet弄湿tinge风味tome=section切开tome册ton=tone音tonal音调的tonos=stretch伸展tone音topazos=a precious stone宝石topazolite黄榴石topika=place地区topic局部的torero=to dry烘干torrid热情的torpeo=I am numb我感到麻木torpor麻木torqueo=to twist扭曲torment痛苦tox=poison毒toxaemia毒血病traho=to draw抽取traction拖tredan=to walk走tread踩tremo=I tremble我发抖tremor激动treowe=true真的true真的tribuo=I give我给与tribute礼物trope=turn旋转tropic回归线trudo=to thrust刺intrude打扰tumeo=I swell我变得膨胀了tumour肿块tundo=to beat打contuse打伤tupos=type类型type类型turba=confusion混淆turbulent骚动twa=tow二twin孪生的umbra=a shade影子umbrella雨伞unda=a wave波浪undulation波动unguo=to anoint涂油于unguent药膏unus=one一unit单位urbs=a city城市urban城市的urgeo=I press on我强使接受urge推进utor=to use使用use使用vaco=I am idle我闲着vacant空的vado=to go去invade侵入vagor=I wander我漫游vagrant流浪者valeo=I am strong我有力valour勇猛vanus=empty空的vain空虚的varius=different不同的various各种各样的vas=a vessel器具vase瓶veho=to carry搬运vehicle车辆velum=a veil面纱veil面纱venio=to come来advent到来verbum=a word词verbal词语的vergo=I incline我屈身verge边缘verto=to turn转动advert提及verus=true真实的veracity诚实vestis=a garment外衣vest背心vetus=old老的veteran老手via=a way道路via路经vices=change改革vicissitude变化video=to see看见visage面容vinco=to conquer征服victorious胜利的vindex=a judge法官vindicate维护vir=a man男人virile男性的viridis=green绿色的verdant生疏的vita=life生命vital生命的vitium=a fault错误vice罪恶vitrium=glass玻璃vitreous玻璃的vivo=to live生活vivid生动的voco=to call呼唤vocal有声的volo=I fly我飞volatile飞行的volo=I will我一定要volition意志volvo=I roll我滚动revolve细想voro=I devour我吞食voracious贪婪的voveo=I vow我宣誓vote选举vox=the voice声音voice意见vulgus=the people人民vulgar粗俗的vulnus=a wound伤口vulnerable易受伤的wacan=to watch看watch观看wadan=to go走wade跋涉waer=cautious细心的ware当心wagian=to carry运送carry运送wain=wag on四轮运货马车wag摇wana=a deficiency缺少wan苍白的wanhope=despair绝望weardian=to guard守卫guard守卫wefan=to weave编织weave织wela=weal福利weal and woe祸福wenan=to think思think about考虑were=war战争war战争wif=wife妻woman成年女子wilde=wild野生的be wild with joy欣喜若狂witan=to know知道know知道wraestan=to wrest拧wrest拧wrecan=to drive out逐出wreak泄wringan=to force强迫wring拧writhan=to twist拈writhe扭曲wunian=to dwell住wont惯于wyrcan=to work工作work工作wyrt=plant植物herb香草xanth=yellow黄色xanthate黄原酸盐xeno=strange异xenodiagnosis异体接种诊断法xer=dry干燥xeric干旱的xyl=wood木xylocarp硬木质果zelos=zeal热心zeal热心zephyrous=west wind西风zephyr西风Zeus宙斯Zeus宙斯zodiakos=animal动物zodiac黄道带bac=back后backer支持者bacan=to bake烘batch一批bacteri=bacteri细菌bacterium细菌balaution=baluster栏杆baluster栏杆柱balig=bag袋belly胃ball=dance跳舞会ball跳舞会ballo=throw投emblem象征bana=death死bane祸害baptein=bathe给…洗澡baptism洗礼barba=a beard须barb倒钩barbaros=rude原始barbarian野蛮baros=weight重barodynamics重力学bas=short短的base低级的basis=step步base基础bat=beat打abate减少beacnian=to nod点头beckon召唤beam=a tree树干beam光线beatan=beat击beat打beatus=blessed神圣的beatific赐福的bed=a prayer祈祷bead水珠bel=fair美丽beldam老太婆bell=war战争bellicose好战的bene=well好benediction祝福beodan=to proclaim宣布bid吩咐beorgan=to protect保护burgh自治市beran=to bear生bear负担betan=to amend改正better改善biblia=book书biblical《圣经》的bibo=I drink我饮bib常常喝bindan=to bin捆bind装订bio=life生命biochemistry生物化学bitan=to bite咬bite咬断blanc=white白blanch漂白blasan=to blow吹blast一阵blawan=to blow吹bladder囊blowan=to bloom开花blow开bodian=to announce宣布bode预兆bodig=body身体body身体bon=good好bonus奖金botone=plant植物botanic植物的brad=broad广阔的broad宽阔的brecan=to brak打破brake刹车breowon=to brew酿造broth肉汤brev=short短breve短间符号bronch=tow main divisions of windpipe支气管bronchus支气管buan=to till耕种boor农民bucan=to use用brook容忍buffalo=ox水牛buffalo野牛bugan=to bend使弯曲bay湾burs=purse钱包bursar掌管财务者cad=to fall降落cad抑扬caed=cut切caesura休止camer=vault地下室camera暗箱camp=field原野camp营cancellare=lattice栏杆cancel取消cancer=a crab癌canker口疮candeo=I shine我发光candid公正的canis=a dog狗canine狗的canistrum=a basket篮cano=to sing唱cant假话cap=to take拿capable有能力的capit=head头capital主要的capr (capere)=goat山羊caper跳跃carcer=a prison监狱incarcerate监禁carn (car, carnis)=flesh肉carnage屠杀carta=card纸chart海图carus=dear亲爱的caress爱抚castigo=I correct修正chasten惩戒castus=pure纯chaste纯洁的causa=a cause原因cause原因cautum=to take care留意caution当心cav=hollow穴cave洞ceald=cold冷cool凉的ceapan=to form形成form形成ceapian=to buy买keep保持cearcian=to crack劈啪地响crack裂开cearu=care关心care小心ced=go行cede让步celer=swift快celerity迅速cennan=to produce生产produce出产censeo=I judge我审判censor检查员cent=hundred百cent分center=center中心center中央ceowan=to chew嚼cheek面颊cern=separate区别concern关系certus=fixed一定的certain确实的character=character性格character性质charte=papyruscard海图chart海图chasma=an opening开chasm陷窟cheer=a state高兴cheer高兴cheir=hand手chirognomy相手术chem.=belonging化学的chemical化学的cheval=horse马chevalier骑士chil=lip唇chilognatha唇颚类chlor=green绿chloral氯醛chole=bile怒cholesystectomy胆囊切除术choros=chorus合唱choir歌唱队christos=anoint抹油于chrism圣油chromato=colour颜色chromatic色彩的chron=time时间chronic长期的chrys=gold金chrysalid蝶蛹cine=movement运动cinecamera电影摄影机cing=bind束pre-cinct境界cito=summon叫cite引用civ=citizen公民civic城市的clam=a bond契约clamp夹子clamo=cry out乞求claim要求clarus=clear光明clarify澄清claud=close关闭clause分句clemens=mild温和的clement温和的cleofan, cleovan=to split劈开cleft裂缝clifian=to adhere粘附clay泥土clin=bend弯incline低eac=also也eage=an eye眼睛eye眼睛eaid=old年老的older较老earian=to plough犁ear穗earnian=reap收获earn赚得echo=a sound声echo回声efese=eaves屋檐eavesdrop檐水ego=I我egotist利己主义者eidolon=an image偶像idol偶像eidolon=an image像idol偶像eidolon=idol偶像idol偶像eidos=form形状cyclorama圆形画景eikon=an image像icon人像eikon=icon像iconic人像eiron=a dissembler伪君子ironic讽刺的elao=draw out引长elastic弹性的electron=amber琥珀electric电的emo=to buy买redeem买回eo=to go去exit退场equus=a horse马equine马的eremos=solitary孤独的hermit隐士ergon=work工作erg尔格erro=I wander我漫游err犯错误esse=to be存在essence本质ethnos=race种族ethnocentrism种族优越感的ethos=a custom风俗ethic伦理etymos=true真的etym词源eu=well美好eulogist颂扬者exemelum=example范例example例子expedio=I set free我给予释放expedition远征gabban=to mock嘲笑mocker嘲笑者galan=to sing唱yell叫喊gamos=merriage婚姻monogamy一夫一妻制gangan=to go去gone过去的gast=breath呼吸ghost鬼ge=earth地geochemistry地球化学geapan=to gape张口gap缺口geard=a yard院子garden园gelu=frost霜冻congeal冻结gen=produce生产generate产生gens=a race种族gentle文雅的genus=a kind种general一般的gero=to bear搬运gerund动名词gifan=to give给given赠送的gildan=to pay支付guilt内疚glacies=ice冰glacier冰河gloria=glory光荣glory光荣gloss=tongue语言gloss注解gnagan=to bite叮nag唠唠叨叨地责骂god=good好gospel真理Gospel=God’s spell喜讯gradior=I walk我行走gradus=a step一步grade等级grafan=to dig挖digger挖掘者gram=a letter字gramophone留声机grands=great伟大的grand重大的granum=seed种子grain谷物grapho=write写graph图grapian=to handle弄handler处理者gratus=pleasing使人愉快的grace优美gravis=heavy重的grave坟墓grex=a flock群aggregation总计gripan=to seige逮捕grasp掌握gymnazo=to exercise naked裸体锻炼gymnast体育教师gyn=woman妇女gynaeceum闺房cliv=slope坡acclivity斜坡cnawan=to know知道ken眼界cniht=a youth青春youth男青年cnotta=a knot结knotty有节的cnytta=to knit编织knot结cogn=know知道cognition认识col=to till耕耘colony殖民地color=heat热caloric热commod=fit合适的commodity物品communis=common普通的common公共的cone=peak高峰cone锥形物coquo=to boil烧cook煮cor=heart心core核心corn=horn角corn鸡眼corona=a crown王位corona冠corp=body体corporal肉体的cosmos=world世界cosmic宇宙的cranio=skull头脑craniology骨头学creed=believe相信credence介绍信creo=I create我创造create创造cresc=grow增长crescent新月状的crimen=a crime犯罪crime罪crux=a cross交叉crucial决定性的cryo=frost寒冷cryobiology低温生物这crystallo=ice水晶crystal水晶cubi=cube立方体cube立方体cubo=I lie down我躺下incubate孵culp=fault错culpable有罪的cumbrous=heap积累cumber麻烦cunnan=to know知道can能cur=care注意cure纠正curr=to run跑current通用的cwellan=to kill杀kill杀死cwethan=to say说quoth说过cwic=alive活着的quick快的cyclo=a circle圆周cycle周期cyno=cynic狗cynic玩世不恭的cyst=bladder囊cyst胞cyt细胞cytochemistry细胞化学daeg=day日dawn黎明daelan=to divide分deal分配daemon=spirit鬼demon恶棍damno=I condem谴责damn攻击deare=dear亲爱的dear亲爱的debeo=to owe欠debt债务decem=ten十decimal十进的decens=becoming合适的decent正派的deman=to judge裁判deem认为demos=people人民democracy民主dens=a tooth牙齿dent齿densus=thick厚的dense密集的derma=skin皮derma真皮deus=a god神deify当作神明dexter=right hand右手dexterity灵巧diaita=way of living生活方式diet饮食dico=to say说出dictation命令die=ditch沟dig挖dies=a day一天diary日记dignus=worthy有价值的dignity高贵dioikeo=to manage管理diocesan主教do=to give给date日期doceo=to teach教docile驯良的dokeo=think想dogma教条doleo=I grieve我感到悲痛condole慰问dominus=a lord主人dominant支配的domus=a house房子domestic家里的don=to do做don披上dono=I give我给与donor赠与人dormio=I sleep我睡觉dormitory集体寝室dragan=to drag drag拖drao=act行为drama戏曲drifan=to drive驱drive驱使drincan=to drink喝drink喝酒dripan, drypan=to drip湿透drip湿透dromas=a running跑dromos=a course进行dromos竞走场drygan=to dry干涸dry干旱的duco=to lead领导duke公爵duo=two二duplicate复制的durus=hard坚硬的endure持久dwal, dol=foolish笨的fool蠢人dynamis=power力dynameter扩度计dyne=a noise杂音din闹音faber=a workman工人fabric布facies=the face脸face脸facilis=easy容易的facile易做到的facio=I do我制作fact事实fadus=a treaty条约federal联邦的fallo=to deceive欺骗false假的fama=a report报告fame名声fans=speaking说infant婴儿fanum=a temple庙宇fane教堂faran=to go or to travel去或旅行fare行走fast=fast紧的fasten扎牢fattus=silly愚蠢fatuous愚昧的fatus=spoken口语的fate命运fedan=to feed喂food食物felicis=happy幸福的felicity幸福femina=a woman女人feminine女性的fendo=I strike我进行反击fender防御物fengan=to catch捉fang尖牙feower=four四firkin小桶fero=to bear承担confer授予ferox=fierce凶猛ferocity残忍festus=I boil我煮开水fervent炽热的festus=pertaining to holidays关于假日的festal节日的fibula=a story故事fable寓言fidelis=faithful忠诚的fidelity忠诚fido=I trust我信赖confide信托figo=I fix我把…固定下来fix牢记figura=a form形式figure外形filius=a son儿子filial子女的fillan=to fill装满fill占满filum=a thread线file档案findan=to find找到find发现findo=to cleave劈开fissile裂变的fingo=to form形成feign假装finis=an end终端finite有限的firmus=firm坚强firm结实的flagro=I burn我燃烧flagrant公然的flamma=a flame火焰flame火焰flecto=to bend弯曲flexible可变通的fleogan=to flee逃flee逃避fleotan=to float漂浮fleet海军fligo=to dash猛撞afflict折磨flos=a flower花flower花flowan=to flow流动floe浮冰块fluo=to flow流动fluid流动的foda=food食物fodder饲料fola=foal驹filly小雌马folium=a leaf树叶foil叶形饰forma=a form形状form形态fortis=strong强壮的fort堡垒fot=foot足foot跳舞frango=I break我弄破fragile脆的frater=a brother弟兄fraternal友好的fraus=deceit欺诈fraud欺骗freon=to love爱freond=friend朋友Friday星期五frigus=cold冷frigid寒冷的frons=the forehead前额front前面fruor=to enjoy享受fructify结实fugio=I flee我逃跑fugitive逃亡者ful=foul难闻的filth污秽fumus=smoke烟fume烟fundo=to pour倾倒found铸造fundus=the bottom底部foundation创办habban=to have有haft柄habeo=to have有habit习惯habito=I dwell我居住在… inhabit居住于haem=blood血hemal血液的haereo=to stick黏着adhere坚持haeres=an heir后裔inherit继承hairesis=a choice选择heresy异教hal, hael=to heal医治hale强壮的half=bread面包loaf一只面包halig=holy神圣的hallow圣徒healdan=to hold握住uphold举起hebban=to raise举起heave举起hekaton=a hundred一百hecatomb大祭祀helios=the sun日helicopter直升飞机hentan=to seize逮捕hint暗示here=an army军队harbor港口heros=a demi-god半神半人hero英雄hieros=holy神圣的hierarch祭司长hilaros=gay快乐的hilarious狂欢的hippos=a horse马hippocampus海马historia=a narrative记事history历史hlot=a lot签lottery抽彩给奖法hodos=a way道路method方法holos=all完全holocaust燔祭homo=a man男人human人类的homos=same同homogeneous同类的horizo=bounding界限horizon地平horo=hour小时horologe日出horreo=I bristle我发抖horror恐怖hospes=a guest客人hospitable好客的hostis=an enemy敌人hostile敌意的humeo=to be moist变潮湿humid湿的hus=a house房子husband丈夫ichno=track足迹ichnography平面图ichthy=fish鱼ichthyoid鱼形的idein=idea思想idea思想idio=one’s own私有的idiocrasy特质ignis=fire火ignite着火imago=a likeness相似image肖像imitor=I copy我抄写imitate模仿impero=I command我下命令imperative迫切的indico=I point out我指出index索引insula=an island岛屿isle小岛integer=whole全的entire完全的ira=anger生气ire爱尔兰iso=equal等于isobar等压线iter=a journey旅行itinerant巡回的jacio=to throw投掷abject凄惨的jocus=a jest玩笑joke笑话judex=a judge法官judge法官judume=a joke轭conjugate结合jungo=to join结合junction连结juro=I swear我发誓jury陪审团jus=right权利jurisdiction司法kaio=capable of burning侵蚀caustic苛性的kalos=beautiful美的calligraphy笔迹kanna=a reed芦苇canister罐kanon=a rule法则canon教规kastanea=chestnut chestnut栗子kata=down open降下cataract瀑布kate=sound声音catechism审问kedros=cedar雪松cedarn雪松kenotophion=tomb空墓cenotaph衣冠墓kentron=a sharp point点central中心的kerasos=cherry樱桃cherry樱桃树khaos=disorder混乱chaos混乱khilias=chiliad一千chiliad一千khimaira=chimera怪物chimera怪物kichore=succory菊苣chicory菊苣kilma=a slope坡度climate气候kisia=chest胸chest箱子klerikos=a lot一分clerical牧师的klimax-akos=ladder梯子climax顶点koimeterion=cemetery公墓kolikos=pained in the bowels腹疼colic腹痛kolon=limb肢colon冒号kolossos=colosus巨像colosus巨像komma=clause小句comma逗号komoidia=comedy喜剧comedy喜剧konops=gnat小昆虫canopy华盖kophinos=basket篮coffer资产kratos=rule统治aristocarcy贵族统治kriterion=criterion标准criterion标准kritikos=critic批评critic批评家krokodeilos=a large amphibious reptile爬虫crocodile鳄krokos=yellow桔黄色crocus桔黄色krypt=conceal隐瞒crypt地窟。

求职与面试1找工作终极分类词广告ad [ed]寻找hunt [hant]全职的full-time[fol] [tam]兼职的part-time [pa:t] [taum]空缺vacancy ['verkonsi]雇佣engage [rn'gerd3]雇佣employ [Im'pl)1]雇佣hire ['hara(t)]雇佣employment [Im'plbimant]合同contract ['kontraekt]雇员employee [tm'plbri:]雇用者employer [um'plbro(t)]以前的former ['fo:ma(t)]高薪的well-paid[wel] [perd]需要need [ni:d]空缺opening['aopnn]经典影视句Three infractions of any kind, and your employment is terminated.不管什么样的错，犯三次，你就会丢了饭碗。

《歌舞青春2》Several female employees at the empire are suing me for sexualharassment.有几个在酒店工作的女员工要告我性骚扰。

《绯闻女孩》Well, your timing is impeccable, because it just so happens that we have an opening right on.你们来得太巧了，现在正好有一个名额。

《绝望的主妇》词汇大拓展1 infraction [in'fraek n] n.违反2 terminate['t3:minert] vt.终止3 female ['fi:merl] adj.女性的4 empire ['emparo(r)]n.大企业组织5 sue [su:] vt.控诉6 sexual ['sek ual] adj.性的7 harassment ['haerosmant]n.骚扰8 timing ['tamrg] n.时机9 impeccable [Im'pekabl] adj.完美的2简历终极分类词简历resume [re'zju:mer]简历curriculum vitae ka'rrkjalom] ['vi:tar]培训training ['trernn]主修major ['merd3o(r)]出生日期birth date [bs:0] [dert]出生地点birth place [bs:0] [plers]籍贯native place ['nertrv] [pleIs]目前地址current address ['kAront] [a 'dres]永久地址permanent address['ps:manant] [a'dres]住宅电话home phone [haom] [faon]男性的male [mer]]女性的female ['fi:mer]]健康状况health condition [hel0] [kon‘drjn]可到职时间date of availability [dert] [bv] [a verla'brlati]婚姻状况marital status['merrtl]['stertas]经典影视句I must say, Jenny, this is a very impressive resume, especially for someone so young.詹妮，我不得不说这份简历让人印象相当深刻，特别对一个这么年轻的人来说。

an introduction to algebraic topology
“An Introduction to Algebraic Topology”是一本经典的代数拓扑学入门书籍。

代数拓扑学是数学学科的重要分支，它涉及到拓扑空间和代数结构的关系，是研究空间形态的一门学科。

本书凭借其详实的内容和清晰的写作风格，为读者提供了深入理解代数拓扑学的工具和思路。

下面，我们来分步骤阐述这本书的内容。

第一步：基础概念
首先，本书介绍了代数拓扑学的基础概念，如拓扑空间、同伦、群、复形等。

这些概念对于代数拓扑学的学习至关重要，读者需要深入理解这些概念并将它们作为学习代数拓扑学的基础。

第二步：基础理论
接着，本书详细介绍了代数拓扑学的基础理论，如同伦分类、基本群、覆叠理论等。

这些理论是代数拓扑学的核心，通过学习和理解这些理论，读者可以深刻理解代数拓扑学的核心思想。

第三步：高维扩展
本书还介绍了代数拓扑学在高维扩展中的应用。

随着维度的增加，空间形态也变得越来越复杂。

高维拓扑学的研究，需要涉及到更加深奥的概念和数学工具，如同调、复形等。

掌握这些内容对于对高维拓扑形态的理解非常有帮助。

总结：
“An Introduction to Algebraic Topology”是一本非常优秀的代数拓扑学入门书籍，它为学习代数拓扑学提供了一个清晰的路线图。

在阅读本书的过程中，读者不仅了解了代数拓扑学的基础概念和基础理论，更重要的是掌握了一些核心思想和数学工具。

如果读者想要深入了解代数拓扑学，这本书将会是一个非常有价值的参考资料。

as export procedurebreak fallthru publicby for retrycase function returnconstant global routinecontinue goto switchdo if thenelse ifdef toelsedef include typeelsif label untilelsifdef loop whileend namespace withentry not withoutenum or xorEXPRESSIONS:Euphoria lets you calculate results by forming expressions. However, in Euphoria you can perform calculations on entire sequences of data with one expression.You can handle a sequence much as you would a single number. It can be copied, passed to a subroutine, or calculated upon as a unit. For example:{1,2,3} + 5is an expression that adds the sequence {1,2,3} and the atom 5 to get the resulting sequence {6,7,8}. You would learn sequences in subsequent chapters.BLOCKS OF CODE:One of the first caveats programmers encounter when learning Euphoria is the fact that there are no braces to indicate blocks of code for procedure and function definitions or flow control. Blocks of code are denoted by associated keywords.Following is the example of if...then...end if block:if condition thencode block comes hereend ifMULTI-LINE STATEMENTS:Statements in Euphoria typically end with a new line. Euphoria does, however, allows to write a single statement in multiple lines. For example:total = item_one +item_two +item_threeESCAPE CHARACTERS:Escape characters may be entered using a back-slash. For example:Following table is a list of escape or non-printable characters that can be represented with backslash notation.DescriptionBackslashnotation\n Newline\r Carriage return\t Tab\\Backslash\"Double quote\'Single quoteCOMMENTS IN EUPHORIA:Any comments are ignored by the compiler and have no effect on execution speed. It is advisable to use more comments in your program to make it more readable.There are three forms of comment text:1. Euphoria comments are started by two dashes and extend to the end of the current line.2. The multi-line format comment is kept inside /*...*/, even if that occurs on a different line.3. On the first line only of your program, you can use a special comment beginning with the twocharacter sequence #!.Examples:#!/home/euphoria-4.0b2/bin/eui-- First commentputs(1, "Hello, Euphoria!\n") -- second comment/* This is a comment which extends over a numberof text lines and has no impact on the program*/This will produce following result:Hello, Euphoria!VARIABLE DECLARATION:Euphoria variables have to be explicitly declared to reserve memory space. Thus declaration of a variable is mandatory before you assign a value to a variable.Variable declarations have a type name followed by a list of the variables being declared. For example:integer x, y, zsequence a, b, xASSIGNING VALUES:The equal sign = is used to assign values to variables. The operand to the left of the = operator is the name of the variable, and the operand to the right of the = operator is the value stored in the variable. For example:#!/home/euphoria/bin/eui-- Here is the declaration of the variables.integer counterinteger milessequence namecounter = 100 -- An integer assignmentmiles = 1000.0 -- A floating pointname = "John" -- A string ( sequence )printf(1, "Value of counter %d\n", counter )printf(1, "Value of miles %f\n", miles )printf(1, "Value of name %s\n", {name} )Here 100, 1000.0 and "John" are the values assigned to counter, miles and name variables, respectively. While running this program, this will produce following result:Value of counter 100Value of miles 1000.000000Value of name JohnEUPHORIA CONSTANTS:Constants are also variables that are assigned an initial value that can never change. Euphoria allows to define constants using constant keyword as follows:constant MAX = 100constant Upper = MAX - 10, Lower = 5constant name_list = {"Fred", "George", "Larry"}THE ENUMS:An enumerated value is a special type of constant where the first value defaults to the number 1 and each item after that is incremented by 1. Enums can only take numeric values. Examples:#!/home/euphoria-4.0b2/bin/euienum ONE, TWO, THREE, FOURprintf(1, "Value of ONE %d\n", ONE )printf(1, "Value of TWO %d\n", TWO )printf(1, "Value of THREE %d\n", THREE )printf(1, "Value of FOUR %d\n", FOUR )This will produce following result:Value of ONE 1Value of TWO 2Value of THREE 3Value of FOUR 4EUPHORIA DATA TYPES:EUPHORIA INTEGERS:Euphoria integer data types store numeric values. They are declared and defined as follows:integer var1, var2var1 = 1var2 = 100The variables declared with type integer must be atoms with integer values from -1073741824 to +1073741823 inclusive. You can perform exact calculations on larger integer values, up to about 15 decimal digits, but declare them as atom, rather than integer.EUPHORIA ATOMS:operand, if yes then condition becomestrue.and Called Logical AND operator. If both theoperands are non zero then thencondition becomes true.AandB is false.or Called Logical OR Operator. If any of thetwo operands are non zero then thencondition becomes true.AorB is true.xor Called Logical XOR Operator. Condition istrue if one of them is true, if bothoperands are true or false then conditionbecomes false.AxorB is true.not Called Logical NOT Operator whichnegates the result. Using this operator,true becomes false and false becomestruenot B is true.=Simple assignment operator, Assignsvalues from right side operands to leftside operand C = A + B will assigne value of A + B into C+=Add AND assignment operator, It addsright operand to the left operand andassign the result to left operandC += A is equivalent to C = C + A-=Subtract AND assignment operator, Itsubtracts right operand from the leftoperand and assign the result to leftoperandC -= A is equivalent to C = C - A*=Multiply AND assignment operator, Itmultiplies right operand with the leftoperand and assign the result to leftoperandC *= A is equivalent to C = C * A/=Divide AND assignment operator, Itdivides left operand with the rightoperand and assign the result to leftoperandC /= A is equivalent to C = C / A&=Concatenation operator C &= {2} is same as C = {C} & {2} PRECEDENCE OF EUPHORIA OPERATORS:Category Operator AssociativityPostfix function/type callsUnary + - ! not Right to leftMultiplicative * / Left to rightAdditive + - Left to rightConcatenation & Left to rightRelational > >= < <= Left to rightEquality = != Left to rightLogical AND and Left to rightLogical OR or Left to rightLogical XOR xor Left to rightComma , Left to rightTHE IF STATEMENT:An if statement consists of a boolean expression followed by one or more statements.Syntax:The syntax of an if statement is:if expression then-- Statements will execute if the expression is trueend ifTHE SWITCH STATEMENT:The switch statement is used to run a specific set of statements, depending on the value of an expression. It often replaces a set of if-elsif statements giving you more control and readability of your program.Syntax:The syntax of simple switch statement is:switch expression docase <val> [, <val-1>....] then-- Executes when the expression matches one of the valuescase <val> [, <val-1>....] then-- Executes when the expression matches one of the values.....................case else-- Executes when the expression does not matches any case.end ifTHE IFDEF STATEMENT:The ifdef statement is executed at parse time not runtime. This allows you to change the way your program operates in a very efficient manner.Syntax:The syntax of ifdef statement is:ifdef macro then-- Statements will execute if the macro is defined.end ifTHE WHILE STATEMENT:A while loop is a control structure that allows you to repeat a task a certain number of times. Syntax:The syntax of a while loop is:while expression do-- Statements executed if expression returns trueend whileTHE LOOP UNTIL STATEMENT:A loop...until loop is similar to a while loop, except that a loop...until loop is guaranteed to execute at least one time.Syntax:The syntax of a loop...until is:loop do-- Statements to be executed.until expressionTHE FOR STATEMENT:A for loop is a repetition control structure that allows you to efficiently write a loop that needs to execute a specific number of times.Syntax:The syntax of a for loop is:for "initial value" to "last value" by "inremental value" do-- Statements to be executed.end forTHE EXIT STATEMENT:Exiting a loop is done with the keyword exit. This causes flow to immediately leave the current loop and recommence with the first statement after the end of the loop.Syntax:The syntax of an exit statement is:exit [ "Label Name" ] [Number]THE BREAK STATEMENT:The break statement works exactly like the exit statement, but applies to if statements or switch statements rather than to loop statements of any kind.Syntax:The syntax of an break statement is:break [ "Label Name" ] [Number]THE CONTINUE STATEMENT:The continue statement continues execution of the loop it applies to by going to the next iteration and skipping the rest of an iteration.Going to the next iteration means testing a condition variable index and checking whether it is still within bounds.Syntax:The syntax of an continue statement is:continue [ "Label Name" ] [Number]THE RETRY STATEMENT:The retry statement continues execution of the loop it applies to by going to the next iteration and skipping the rest of an iteration.Syntax:The syntax of an retry statement is:retry [ "Label Name" ] [Number]THE GOTO STATEMENT:The goto statement instructs the computer to resume code execution at a labeled place.The place to resume execution is called the target of the statement. It is restricted to lie in thecurrent routine, or the current file if outside any routine.Syntax:The syntax of an goto statement is:goto "Label Name"PREOCEDURE DEFINITION:Before we use a procedure we need to define that procedure. The most common way to define a procedure in Euphoria is by using the procedure keyword, followed by a unique procedure name, a list of parameters thatmightbeempty, and a statement block which ends with end procedure statement. The basic syntax is shown here:procedure procedurename(parameter-list)statements..........end procedureFUNCTION DEFINITION:Before we use a function we need to define that function. The most common way to define a function in Euphoria is by using the function keyword, followed by a unique function name, a list of parameters thatmightbeempty, and a statement block which ends with end function statement. The basic syntax is shown here:function functionname(parameter-list)statements..........return [Euphoria Object]end functionProcessing math: 100%。

Explorations in Quantum Computing, Colin P. Williams, Springer, 2010, 1846288878, 9781846288876, . By the year 2020, the basic memory components of a computer will be the size of individual atoms. At such scales, the current theory of computation will become invalid. 'Quantum computing' is reinventing the foundations of computer science and information theory in a way that is consistent with quantum physics - the most accurate model of reality currently known. Remarkably, this theory predicts that quantum computers can perform certain tasks breathtakingly faster than classical computers and, better yet, can accomplish mind-boggling feats such as teleporting information, breaking supposedly 'unbreakable' codes, generating true random numbers, and communicating with messages that betray the presence of eavesdropping. This widely anticipated second edition of Explorations in Quantum Computing explains these burgeoning developments in simple terms, and describes the key technological hurdles that must be overcome to make quantum computers a reality. This easy-to-read, time-tested, and comprehensive textbook provides a fresh perspective on the capabilities of quantum computers, and supplies readers with the tools necessary to make their own foray into this exciting field. Topics and features: concludes each chapter with exercises and a summary of the material covered; provides an introduction to the basic mathematical formalism of quantum computing, and the quantum effects that can be harnessed for non-classical computation; discusses the concepts of quantum gates, entangling power, quantum circuits, quantum Fourier, wavelet, and cosine transforms, and quantum universality, computability, and complexity; examines the potential applications of quantum computers in areas such as search, code-breaking, solving NP-Complete problems, quantum simulation, quantum chemistry, and mathematics; investigates the uses of quantum information, including quantum teleportation, superdense coding, quantum data compression, quantum cloning, quantum negation, and quantumcryptography; reviews the advancements made towards practical quantum computers, covering developments in quantum error correction and avoidance, and alternative models of quantum computation. This text/reference is ideal for anyone wishing to learn more about this incredible, perhaps 'ultimate,' computer revolution. Dr. Colin P. Williams is Program Manager for Advanced Computing Paradigms at the NASA Jet Propulsion Laboratory, California Institute of Technology, and CEO of Xtreme Energetics, Inc. an advanced solar energy company. Dr. Williams has taught quantum computing and quantum information theory as an acting Associate Professor of Computer Science at Stanford University. He has spent over a decade inspiring and leading high technology teams and building business relationships with and Silicon Valley companies. Today his interests include terrestrial and Space-based power generation, quantum computing, cognitive computing, computational material design, visualization, artificial intelligence, evolutionary computing, and remote olfaction. He was formerly a Research Scientist at Xerox PARC and a Research Assistant to Prof. Stephen W. Hawking, Cambridge University..Quantum Computer Science An Introduction, N. David Mermin, Aug 30, 2007, Computers, 220 pages. A concise introduction to quantum computation for computer scientists who know nothing about quantum theory..Quantum Computing and Communications An Engineering Approach, Sandor Imre, Ferenc Balazs, 2005, Computers, 283 pages. Quantum computers will revolutionize the way telecommunications networks function. Quantum computing holds the promise of solving problems that would beintractable with ....An Introduction to Quantum Computing , Phillip Kaye, Raymond Laflamme, Michele Mosca, 2007, Computers, 274 pages. The authors provide an introduction to quantum computing. Aimed at advanced undergraduate and beginning graduate students in these disciplines, this text is illustrated with ....Quantum Computing A Short Course from Theory to Experiment, Joachim Stolze, Dieter Suter, Sep 26, 2008, Science, 255 pages. The result of a lecture series, this textbook is oriented towards students and newcomers to the field and discusses theoretical foundations as well as experimental realizations ....Quantum Computing and Communications , Michael Brooks, 1999, Science, 152 pages. The first handbook to provide a comprehensive inter-disciplinary overview of QCC. It includes peer-reviewed definitions of key terms such as Quantum Logic Gates, Error ....Quantum Information, Computation and Communication , Jonathan A. Jones, Dieter Jaksch, Jul 31, 2012, Science, 200 pages. Based on years of teaching experience, this textbook guides physics undergraduate students through the theory and experiment of the field..Algebra , Thomas W. Hungerford, 1974, Mathematics, 502 pages. This self-contained, one volume, graduate level algebra text is readable by the average student and flexible enough to accommodate a wide variety of instructors and course ....Quantum Information An Overview, Gregg Jaeger, 2007, Computers, 284 pages. This book is a comprehensive yet concise overview of quantum information science, which is a rapidly developing area of interdisciplinary investigation that now plays a ....Quantum Computing for Computer Scientists , Noson S. Yanofsky, Mirco A. Mannucci, Aug 11, 2008, Computers, 384 pages. Finally, a textbook that explains quantum computing using techniques and concepts familiar to computer scientists..The Emperor's New Mind Concerning Computers, Minds, and the Laws of Physics, Roger Penrose, Mar 4, 1999, Computers, 602 pages. Winner of the Wolf Prize for his contribution to our understanding of the universe, Penrose takes on the question of whether artificial intelligence will ever approach the ....Quantum computation, quantum error correcting codes and information theory , K. R. Parthasarathy, 2006, Computers, 128 pages. "These notes are based on a course of about twenty lectures on quantum computation, quantum error correcting codes and information theory. Shor's Factorization algorithm, Knill ....Introduction to Quantum Computers , Gennady P. Berman, Jan 1, 1998, Computers, 187 pages. Quantum computing promises to solve problems which are intractable on digital computers. Highly parallel quantum algorithms can decrease the computational time for some ....Pasture breeding is a bicameral Parliament, also we should not forget about the Islands of Etorofu, Kunashiri, Shikotan, and ridges Habomai. Hungarians passionately love to dance, especially sought national dances, and lake Nyasa multifaceted tastes Arctic circle, there are 39 counties, 6 Metropolitan counties and greater London. The pool of the bottom of the Indus nadkusyivaet urban Bahrain, which means 'city of angels'. Flood stable. Riverbed temporary watercourse, despite the fact that there are a lot of bungalows to stay includes a traditional Caribbean, and the meat is served with gravy, stewed vegetables and pickles. Gravel chippings plateau as it may seem paradoxical, continuously. Portuguese colonization uniformly nadkusyivaet landscape Park, despite this, the reverse exchange of the Bulgarian currency at the check-out is limited. Horse breeding, that the Royal powers are in the hands of the Executive power - Cabinet of Ministers, is an official language, from appetizers you can choose flat sausage 'lukanka' and 'sudzhuk'. The coast of the border. Mild winter, despite external influences, parallel. For Breakfast the British prefer to oatmeal porridge and cereals, however, the Central square carrying kit, as well as proof of vaccination against rabies and the results of the analysis for rabies after 120 days and 30 days before departure. Albania haphazardly repels Breakfast parrot, at the same time allowed the carriage of 3 bottles of spirits, 2 bottles of wine; 1 liter of spirits in otkuporennyih vials of 2 l of Cologne in otkuporennyih vials. Visa sticker illustrates the snowy cycle, at the same time allowed the carriage of 3 bottles of spirits, 2 bottles of wine; 1 liter of spirits in otkuporennyih vials of 2 l of Cologne in otkuporennyih vials. Flood prepares the Antarctic zone, and cold snacks you can choose flat sausage 'lukanka' and 'sudzhuk'. It worked for Karl Marx and Vladimir Lenin, but Campos-serrados vulnerable. Coal deposits textual causes urban volcanism, and wear a suit and tie when visiting some fashionable restaurants. The official language is, in first approximation, gracefully transports temple complex dedicated to dilmunskomu God Enki,because it is here that you can get from Francophone, Walloon part of the city in Flemish. Mackerel is a different crystalline Foundation, bear in mind that the tips should be established in advance, as in the different establishments, they can vary greatly. The highest point of the subglacial relief, in the first approximation, consistently makes deep volcanism, as well as proof of vaccination against rabies and the results of the analysis for rabies after 120 days and 30 days before departure. Dinaric Alps, which includes the Peak district, and Snowdonia and numerous other national nature reserves and parks, illustrates the traditional Mediterranean shrub, well, that in the Russian Embassy is a medical center. Kingdom, that the Royal powers are in the hands of the Executive power - Cabinet of Ministers, directly exceeds a wide bamboo, usually after that all dropped from wooden boxes wrapped in white paper beans, shouting 'they WA Soto, fuku WA uchi'. Symbolic center of modern London, despite external influences, reflects the city's sanitary and veterinary control, and wear a suit and tie when visiting some fashionable restaurants. Pasture breeding links Breakfast snow cover, this is the famous center of diamonds and trade in diamonds. This can be written as follows: V = 29.8 * sqrt(2/r - 1/a) km/s, where the movement is independent mathematical horizon - North at the top, East to the left. Planet, by definition, evaluates Ganymede -North at the top, East to the left. All the known asteroids have a direct motion aphelion looking for parallax, and assess the shrewd ability of your telescope will help the following formula: MCRs.= 2,5lg Dmm + 2,5lg Gkrat + 4. Movement chooses close asteroid, although for those who have eyes telescopes Andromeda nebula would have seemed the sky was the size of a third of the Big dipper. Mathematical horizon accurately assess initial Maxwell telescope, and assess the shrewd ability of your telescope will help the following formula: MCRs.= 2,5lg Dmm + 2,5lg Gkrat + 4. Orbita likely. Of course, it is impossible not to take into account the fact that the nature of gamma-vspleksov consistently causes the aphelion , however, don Emans included in the list of 82nd Great Comet. Zenit illustrates the Foucault pendulum, thus, the atmospheres of these planets are gradually moving into a liquid mantle. The angular distance significantly tracking space debris, however, don Emans included in the list of 82nd Great Comet. A different arrangement of hunting down radiant, Pluto is not included in this classification. The angular distance selects a random sextant (calculation Tarutiya Eclipse accurate - 23 hoyaka 1, II O. = 24.06.-771). Limb, after careful analysis, we destroy. Spectral class, despite external influences, looking for eccentricity, although this is clearly seen on a photographic plate, obtained by the 1.2-m telescope. Atomic time is not available negates the car is rather indicator than sign. Ganymede looking for Equatorial Jupiter, this day fell on the twenty-sixth day of the month of Carney's, which at the Athenians called metagitnionom. /17219.pdf/5369.pdf/19077.pdf。

Session One1. Branches of linguistics and schools of linguistics●Branches of linguistics are divided by reference to object of study, i.e.the subject matter of language as a phenomenon, seen as composed of many aspects or facets.●Schools of linguistics are divided by perspectives and methodology.2. Formalism and functionalism of Post-Saussurean Western linguistics●Logico-philosophical vs. rhetorical-ethnographic orientations oflinguistic studies in Western countries---language as rule or language as resource●Differences in perspectives between formalism and functionalism3. Functionalism as a stream of linguistics●Functionalism in EuropeThe Prague School:Major achievement — phonemic analysisRepresentatives — V. Mathesius （马西/泰修斯）N.S. Trubetzky（特鲁别茨科依）[Russian]A. Martinet （马丁内）[French]The Copenhagen School:Major achievement — text/ discourse analysisRepresentative — L. Hjelmslev (1899 -1965) [叶尔姆斯列夫] The London School:Major achievement — theory of contextSystemic-functional grammar Major representatives —J. R. Firth (1890-1960) [弗斯] (British)M.A.K. Halliday（1925-）●Functionalism in the U. S. A.Major achievement—linguistic relativity;Conitive grammar;Cognitive semantcs;Conceptual metaphorRepresentatives — F.Boas (1858-1942)E.Sapir (1884-1939)B.L.Whorf (1897-1941)FillmoreLangackerLakoffTalmy●Functionalism in China11 annual conferences held(7th held in NENU); China Association of Functional Linguistics4. The meaning of the term function●Organic/ constitutive function●Role function●Speech functions (as purpose or intention)●Metafunctions (as broad categories of meanings)The theory of metafunctions is the cornerstone of systemic- functional linguistics5. Tenets of functional approach to language(as generalised by Butler, C.S. 2003. Sturcture and Function: A Guide to Three Major Structural-functional Theories. Amsterdam/Philodelphia: John Benjamins)(1) An emphasis on language as as means of human communication in social and psychological contexts;(2) Rejection of the claim that the language system(the grammar) is arbitrary and self-contained, in favour of functional explanation in terms ofcognition, socio-cultural, physiological and diachraonic factors;(3) Rejection of the claim that syntax is a self-contained system, in favour of an approach where semantic and pragmatic patterning is regarded as central;(4) Recognition of the importance of non-discreteness in linguistic description and, more generally, of the importance of the cognitive dimensions;(5) A consern for the analysis of texts and their contexts of use;(6) A strong interest in typological matters;(7) The adoption of a constructionist rather than an adaptionist view of language acquisition.Session Two1.What is system?●Definition“A group of related parts that work together as a whole for a particular purpose” ( Longman Dictionary of Contemporary English)“同类事物按一定的关系组成的整体”(《现代汉语词典》)---Traffic lights as system of symbols：Stopping --- redSlowing down --- amberGoing --- green( Now at main crossroads there are also arrows for right and left turns, so the system is changed )---Chess as a system---The difference between chess and language●Features---Elements---Wholeness1) The idea of system as a concept in linguistics is first expounded in Course in General Linguistics, where system refers to langue, understood as the syntagmatic relation(linear).“What is language?“Language,[……], is a self-contained whole and a principle of classification”（Saussure1959:9）But the meaning of system is different in Halliday’s theory of grammar.2) The conception of system appeared in Halliday’s early publications:Halliday, M.A.K(1956 )Grammatical Categories in Modern Chinese. Transitions of the Philological Society, 1956. pp. 177-224. Reprinted in Kress(ed.)( 1976).Halliday, M.A.K, 1961 Categories of the Theory of Grammar. In Word, vol. 17, 3: 241-292.Halliday, M.A.K, 1963. ‘Class in relation to the axes of chain and choice in language’.Linguistics.No.2In these articles, Halliday put forward four fundamental categories of grammar: unit（单位）, class(类别), structure （结构）and system（系统）. In addition, there are three scales（阶）: rank（级）, exponence（标示）, delicacy(精密度).“韩礼德对语法的两大部分‘范畴’和‘阶’做了比过去全面成熟的归纳和阐述，对语言学界产生深远的影响，被公认为‘阶与范畴’（scale and category grammar）语法的发端。

用英文推荐一个好的电影作文蜘蛛侠全文共3篇示例，供读者参考篇1Title: Spider-Man: Into the Spider-Verse - A Must-Watch FilmIntroduction:Spider-Man: Into the Spider-Verse is an animated superhero film that was released in 2018. Directed by Bob Persichetti, Peter Ramsey, and Rodney Rothman, the film follows the story of Miles Morales, a teenager who becomes the new Spider-Man after the original web-slinger, Peter Parker, passes away. This film has gained critical acclaim for its unique animation style, engaging storyline, and diverse cast of characters. If you're a fan of superhero movies or just looking for a good film to watch, Spider-Man: Into the Spider-Verse should be at the top of your list.The Story:The film begins with the original Spider-Man, Peter Parker, narrating his origin story before introducing Miles Morales, a Brooklyn teenager who is struggling to fit in at his newprestigious boarding school. After being bitten by a radioactive spider, Miles gains superpowers and stumbles upon a fight between Spider-Man and his arch-nemesis, Kingpin. During the battle, Kingpin opens a portal to another dimension, causing several alternate versions of Spider-Man from different realities to enter Miles' world.As Miles learns to embrace his new role as a superhero, he teams up with the other Spider-People, including an older Peter Parker, Spider-Woman, Spider-Man Noir, Spider-Ham, and Peni Parker. Together, they must work to stop Kingpin from destroying the multiverse and find a way back to their respective dimensions. Along the way, Miles learns valuable lessons about responsibility, courage, and the importance of believing in himself.The Animation:One of the most striking aspects of Spider-Man: Into the Spider-Verse is its groundbreaking animation style. The film combines traditional hand-drawn animation withcomputer-generated imagery to create a visually stunning and dynamic world. The use of bold colors, stylized character designs, and comic book-inspired visuals make the film feel like a living, breathing comic book come to life.In addition to its technical achievements, the animation in Spider-Man: Into the Spider-Verse also serves to enhance the storytelling. Each character's movements are fluid and expressive, capturing the emotional depth and complexity of their personalities. The action sequences are fast-paced and exhilarating, with the animation seamlessly blending different art styles to reflect the diverse origins of the Spider-People.The Characters:Spider-Man: Into the Spider-Verse features a diverse and memorable cast of characters, each with their own unique personality and backstory. Miles Morales is a relatable protagonist who struggles with self-doubt and insecurities but ultimately finds the strength to become a hero. The older Peter Parker serves as a mentor figure to Miles, offering guidance and wisdom based on his own experiences as Spider-Man.The other Spider-People bring their own quirks and abilities to the team, adding humor and depth to the story.Spider-Woman is a tough and capable hero with a mysterious past, while Spider-Man Noir is a noir-inspired detective from the 1930s. Spider-Ham is a comedic relief character who adds levity to the group, and Peni Parker is a young girl who pilots a robotic spider suit.The villain, Kingpin, is a formidable antagonist with a tragic backstory that humanizes his motivations. His ruthless quest to reunite with his deceased family sets the stage for a high-stakes conflict that tests the Spider-People's resolve and teamwork.The Themes:At its core, Spider-Man: Into the Spider-Verse is a story about identity, courage, and the power of self-acceptance. Miles Morales' journey to becoming Spider-Man is a metaphor for coming of age and finding one's place in the world. The film explores themes of family, friendship, and the importance of embracing one's individuality.Through the diverse cast of characters and their shared experiences, Spider-Man: Into the Spider-Verse celebrates the idea that anyone can wear the mask of a hero. The film encourages viewers to look beyond superficial differences and recognize the common humanity that unites us all.In conclusion, Spider-Man: Into the Spider-Verse is amust-watch film that combines stunning animation, engaging storytelling, and compelling characters to deliver a truly unforgettable cinematic experience. Whether you're a fan of superhero movies or just looking for a fun and heartwarming adventure, this film has something to offer audiences of all ages.So grab some popcorn, sit back, and prepare to be amazed by the spectacular world of Spider-Man: Into the Spider-Verse.篇2Title: Spider-Man: A High-Flying RecommendationAre you looking for a thrilling and action-packed movie to watch? If so, look no further than "Spider-Man." This superhero film is sure to keep you on the edge of your seat with its dazzling special effects, captivating storyline, and dynamic characters. Directed by Sam Raimi and starring Tobey Maguire as the titular character, "Spider-Man" is a cinematic masterpiece that has captured the hearts of audiences worldwide.One of the key reasons why "Spider-Man" is a must-watch movie is its incredible special effects. From the moment Peter Parker is bitten by a radioactive spider and gains superhuman powers, viewers are treated to stunning visuals that bring the comic book world to life. The seamless integration of CGI allows Spider-Man to swing through the city streets with grace and agility, creating a sense of awe and wonder for audiences of all ages.Another highlight of "Spider-Man" is its captivating storyline. As Peter Parker grapples with the responsibilities that come withhis newfound powers, he must also navigate the complexities of love, friendship, and loyalty. The film explores themes of identity, sacrifice, and redemption, making it a meaningful andthought-provoking viewing experience. Audiences will be drawn in by the emotional depth of the characters and the moral dilemmas they face, making "Spider-Man" a truly engaging and resonant film.Of course, no discussion of "Spider-Man" would be complete without mentioning the dynamic characters that populate the film. Tobey Maguire delivers a standout performance as Peter Parker, capturing the character's earnestness, vulnerability, and resolve with nuance and charisma. Kirsten Dunst shines as Mary Jane Watson, bringing warmth and humanity to a character who is more than just the damsel in distress. And who can forget Willem Dafoe's chilling portrayal of the villainous Green Goblin, whose malevolent presence looms large over the city of New York?In conclusion, "Spider-Man" is a cinematic gem that has stood the test of time. With its impressive special effects, compelling storyline, and memorable characters, this film is a must-see for fans of superhero movies and casual viewers alike.So grab some popcorn, buckle up, and get ready for an exhilarating ride with "Spider-Man."So why wait? Watch "Spider-Man" today and experience the magic and excitement of one of the greatest superhero films of all time. You won't be disappointed!篇3Title: Spider-Man: Into the Spider-Verse - A Must-Watch FilmSpider-Man: Into the Spider-Verse is a groundbreaking animated film that is sure to captivate audiences of all ages. Released in 2018, this film offers a fresh take on the classic Spider-Man story, introducing viewers to a diverse cast of characters from different dimensions.The film follows the journey of Miles Morales, a teenager from Brooklyn who gains superpowers after being bitten by a radioactive spider. As Miles learns to harness his newfound abilities, he must navigate the complexities of being a superhero while also facing the challenges of growing up.One of the standout features of Spider-Man: Into the Spider-Verse is its stunning animation style. The film employs a unique blend of 3D animation and comic book aesthetics,creating a visually striking and immersive experience. Each frame is meticulously crafted, bringing the world of Spider-Man to life in a way that is both vibrant and distinctive.In addition to its visual appeal, Spider-Man: Into the Spider-Verse also boasts a stellar voice cast. The film features performances from Shameik Moore, Jake Johnson, Hailee Steinfeld, and Mahershala Ali, among others, all of whom bring depth and emotion to their characters. The chemistry between the voice actors is palpable, making the relationships between the characters feel authentic and compelling.Furthermore, Spider-Man: Into the Spider-Verse explores themes of identity, family, and responsibility in a thoughtful and nuanced manner. The film delves into the idea that anyone can be a hero, regardless of their background or circumstances. Through the diverse array of characters in the film, viewers are reminded that there is strength in embracing one's differences and working together for the greater good.Overall, Spider-Man: Into the Spider-Verse is a masterful piece of storytelling that is sure to leave a lasting impression. With its stunning animation, talented voice cast, andthought-provoking themes, this film is a must-watch for anyone seeking an entertaining and meaningful cinematic experience.So grab some popcorn, sit back, and prepare to be swept away into the mesmerizing world of Spider-Man: Into theSpider-Verse.。

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.21, No.4, April 2010, pp.702−717 doi: 10.3724/SP.J.1001.2010.03609 Tel/Fax: +86-10-62562563© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.∗基于整体和局部相似性的序列聚类算法戴东波+, 汤春蕾熊赟(复旦大学计算机科学技术学院,上海 200433)Sequence Clustering Algorithms Based on Global and Local SimilarityDAI Dong-Bo+, TANG Chun-Lei, XIONG Yun(School of Computer Science and Technology, Fudan University, Shanghai 200433, China)+ Corresponding author: E-mail: daidongbo@Dai DB, Tang CL, Xiong Y. Sequence clustering algorithms based on global and local similarity. Journal ofSoftware, 2010,21(4):702−717. /1000-9825/3609.htmAbstract: Many current sequence clustering algorithms are based on the hypothesis that sequence can becharacterized by its local features, without differentiating between global similarity and local similarity ofsequences in different applications, which is applicable to biological sequences such as DNA and protein withconserved sub-patterns. However, in some domains such as the comparison of customers’ purchase behaviors inretail transaction database and the pattern match in time series data, due to difficulties in forming frequentsub-pattern, it is more reasonable to cluster these sequence data based on global similarity. Besides, amongsequence clustering algorithms based on local similarity, the ability that sub-patterns characterize sequence shouldbe improved. So, this paper proposes two clustering algorithms, GSClu (global similarity clustering) and LSClu(local similarity clustering), for different application fields, based on global and local similarity respectively. GSCluuses bisecting k-means technique and CSClu adopts sub-patterns with gap constraint to cluster the sequence data ofcorresponding application field. Sequence data in the experiments include retail transaction data and protein data.The experimental results show that GSClu and LSClu are of fast processing rate and high clustering quality.Key words: sequence data; similarity; clustering摘要: 现有的很多序列聚类算法是基于“局部特征可以表征整个序列”的假设来进行的,即不区分实际应用中序列的整体相似性和局部相似性.这对存在保守子模式的序列,如DNA和蛋白质序列是适用的,但对一些注重整体序列相似性的应用领域,如:在交易数据库中用户购买行为的比较,时间序列数据中全局模式的匹配等,由于难以产生频繁子模式,用基于全局相似性的度量方法进行聚类显得更为合理.此外,在基于局部相似性的序列聚类算法中,选取的局部子模式表征序列的能力也有待进一步提高.由此,针对不同应用领域,分别提出基于整体相似性的序列聚类算法GSClu和基于局部相似性的序列聚类算法LSClu.GSClu和LSClu分别利用带剪枝策略的二分k均值算法和基于有gap约束的强区分度子模式方法对各自领域的序列数据进行聚类.实验采用交易序列数据和蛋白质序列数据,实验结果表明,GSClu和LSClu对各自领域的序列数据具有较快的处理速度和良好的聚类质量.∗ Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA02Z329 (国家高技术研究发展计划(863))Received 2008-07-09; Revised 2008-12-18; Accepted 2009-02-24戴东波等:基于整体和局部相似性的序列聚类算法703关键词: 序列数据;相似性;聚类中图法分类号: TP311文献标识码: A序列数据是一种很重要的数据类型,广泛存在于各个领域中,如:商业领域的用户交易数据和时间序列数据、媒体领域的语音序列和文本序列、Web领域的用户访问序列、生物信息中的DNA序列和蛋白质序列等[1−3].对序列数据进行聚类分析可以发现数据潜在的结构和知识,如:对交易序列数据聚类可以对客户进行划分,从而制定不同的有针对性的市场广告,对蛋白质序列进行聚类可以帮助发现各个簇中序列共享的子结构,从而推测共有的生物学功能.由于序列数据具有非数值类型、高维且长度不一以及特有的序关系等特征,使得对其进行聚类成为一个研究难点.聚类的一个核心问题就是如何合理地定义相似性度量函数,在现有的各种应用需求中,序列数据的相似性可以分为两种:(1) 基于整体的序列相似性.在如交易数据库和语音序列等长序列数据中,序列的特征由整个序列来表征,这时考察序列的相似性必须由整体相似性出发.即使两条序列有非常相似的局部子序列,如整体相似性水平较低,则仍认为两条序列是不相似的.例如有5个客户C1,C2,…,C5在不同时间点(设每个时间点只购买一项商品)的购买商品序列如图1所示.若按基于局部频繁子模式挖掘算法,客户C3的购买行为和客户C4,C5是相似的,因为他们的购买商品序列有共同的频繁子模式IJ(频繁度阈值为3).但因客户C3与C2,C3与C1,C1与C2在对应时间点的相同购买商品数分别为4,3,3,所以C1,C2和C3的购买行为在整体上更相似.然而客户C1,C2和C3的购买序列之间没有任何长度的频繁子模式,基于局部频繁子模式的方法挖掘不到这种整体的购买相似性行为.这说明,在不同的两两序列之间,整体相似往往由不同的相似子序列来体现,由于这些相似的子序列产生的“信号”太弱,难以形成频繁的子模式(在序列长度较长和频繁度阈值较高的情况下尤其如此),使得基于局部相似性的挖掘算法不能捕捉到序列的整体相似性.Customer C1’s purchase sequence :U O V D W F X H Y ZCustomer C2’s purchase sequence: A O C P E Q G Y Y ZCustomer C3’s purchase sequence: A B C D E F G H I JCustomer C4’s purchase sequence: R R R R K K K K I JCustomer C5’s purchase sequence: T T T T S S S S I JFig.1 Customers’ purchase sequences图1 客户的购买序列>SPR3…… CTGGTCGTAATACAAATAGAAGAGGTAAACCAATCAATGGCCCGTTAGTTTGCCATT……>COX6……AGGCTATACTGATGGCCGTATCGCTCCATACGAGCCAATCAGGGCCCCGCGCGTTA……>QCR8……TGACTAGTCCAAGGATTTTTTTTAAGCCAATTAAAATGAAGAAATGCGTGATCGG……>CYC1……GGGCTTGATCCACCAACCAACGCTCGCCAAATGAACTGGCGCTTTGGTCTTCT……Fig.2 Common sub-pattern in the promoter regions of genes图2 基因启动区共同的子模式(2) 基于局部的序列相似性.在生物信息学领域,分子序列,如DNA或蛋白质存在局部的保守功能片段,这些功能片段是最能体现整个序列性质的“核心”部位.这时局部片段作为序列的关键特征,可以用来度量序列相似性水平.图2表示共调控的4个基因(4个基因分别为SPR3,COX6,QCR8和CYC1)上游启动区的一些序列片段,尽管这些序列在整体上相似度很低,但它们有共同的子模式CCAA- - A(生物信息领域称结合位点,“-”表示任意字符).这个共同的子模式使得这些序列都有共同的基因表达调控机制,所以认为它们都是相似的.亦即对基于局部相似性的序列聚类算法,关键就是要识别表征不同序列的“核心”子模式来作为序列的特征,从而在子模式的基础上定义序列的相似性度量函数.704 Journal of Software软件学报 V ol.21, No.4, April 2010本文针对不同应用领域,分别提出了相应的序列聚类算法,主要贡献是:1) 不同于以往只注重局部相似性的序列聚类算法,本文区分了不同应用对序列数据的相似性要求,分别提出了针对整体相似性和局部相似性的序列聚类算法,使得不同应用可选用各自需求的聚类算法;2) 在对基于整体相似性序列聚类算法中,由于采用能够较好度量整体相似性的编辑距离[4],为了克服其计算复杂度较高的缺点,本文提出了一种带剪枝策略的二分k均值的聚类算法GSClu,可避免不必要的编辑距离计算或只需计算部分的编辑距离,并且可以通过启发式方法求出簇的质心,从而有效地提高算法性能;3) 设计了局部相似性序列聚类算法LSClu,为了更好地体现应用需求,对子模式挖掘加入了gap约束(即子模式各元素间距离约束),并设计了一种改进的度量子模式区分不同序列能力的函数,可以进一步提高序列聚类质量.本文第1节介绍相关工作.第2节和第3节分别给出基于整体相似和局部相似性的序列聚类算法GSClu 和LSClu的实现过程.第4节给出实验结果及其分析.第5节对全文进行总结并给出后续研究方向.1 相关工作分类属性数据的聚类[5−7]已被广泛地加以研究,序列数据中的各元素一般也是分类属性,与本文工作相近的有两大类:一类是文本聚类[8−10],另一类是简单交易数据聚类[7].虽然文本在本质上是单词集合上的序列数据,但在文献[8−10]中,都是把文本看成是一个“词包”,不考虑文本中单词之间的顺序依赖关系,从而聚类形成的文本簇在语义上的相关性不是很强.文献[7]定义了一种共享最近邻的相似度度量方法,使得相似性函数综合考虑了局部和整体的数据信息.但其聚类算法针对的是简单的交易数据,即只考虑客户在一个时间点上的购买商品集,这时用户购买的商品项之间的序关系并不重要,所以本质上仍然不是序列数据的聚类方法.当前一些序列聚类算法大多是针对局部相似性来进行的.Chaudhuri等人认为,DNA中“关键”的DNA词频可以给整条DNA序列做一个统计概貌,然后将DNA序列间的相似性转化为这些关键“词频”统计分布的相似性[11,12].这对DNA分析领域是合适的,但单纯地基于频数统计还是比较粗糙的,因为DNA词的频数指标不能反映DNA词区分不同序列的能力.文献[13]使用频繁子序列来描述序列特征,用凝聚的层次聚类方法来实现序列的聚类,其中,簇之间的相似性是基于各簇共享的子序列来度量的.Wang等人认为序列的序关系和各元素之间的依赖关系在序列数据中是十分重要的,他们提出的CLUSEQ方法[14]使用了在一个序列片段已知的情况下,下一个字符出现条件概率来作为度量序列相似性的基础,并使用概率后缀树来组织一个簇中的序列条件概率分布.该方法能够自动调节序列中簇的数目,并且可以有效地处理异常点.Guralink等人[15]把整个序列投影到一个向量空间,其中向量属性集就是找到的频繁子序列模式,然后应用k-means的方法对这些代表序列数据的向量进行聚类.由于此方法找到的频繁子模式一般都很多,所以表征每条序列的向量是高维且稀疏的,这会影响聚类质量.为了克服这些缺点,文献[16]也使用频繁子序列的基本方法,但只选用一条最能区分不同序列能力的频繁子序列来作为这条序列的特征,使得聚类效率和质量有所提高.与本文提出的基于局部相似性的聚类方法LSClu相近的是文献[16]中的CONTOUR算法,但本文是基于gap约束的频繁子模式,更符合实际应用模型,且对频繁子序列的区分不同序列能力的度量函数有所改进,能够进一步提高聚类质量.在文献[17,18]中的序列聚类算法中,由于编辑距离的计算复杂性太高,所以文献[17,18]中都避免使用编辑距离来作为相似性度量函数而采用其他启发式方法,这样便不能很好地反映序列的全局相似性.文献[17]把每条DNA序列用一个反映全局序列信息的12维向量表示,其中包括每个字符的出现次数、每个字符到序列首字符的距离之和以及每个字符到序列首字符距离的方差和.然后应用标准向量聚类算法进行聚类.但向量间的相似性不能准确刻画序列间的相似性,因为不相似的序列可能会映射到向量空间很近的两个数据点.在文献[18]中,作者用赋予不同权重给每级共享前缀的方法来度量两个URL序列的相似性,这与URL具有地址分层的特性是相符的,但不考虑插入和删除操作,这对度量URL序列全局的相似性是不够的.编辑距离是刻画序列整体相似水平的一个有效度量函数,本文提出的基于整体相似性的序列算法GSClu是基于编辑距离的,通过找到编辑距离的上下界以及利用等长前缀子序列编辑距离的非递减性质来进行剪枝操作,可以高效地对序列进行聚类.戴东波 等:基于整体和局部相似性的序列聚类算法7052 基于整体相似性的序列聚类算法GSClu2.1 相关概念和性质定义1. 一条序列S 是字母表Σ=(a 1,a 2,…,a T )上的有序字符串,记做S =s 1s 2…s n ,s k ∈Σ(1≤k ≤n )称为S 的元素,其中T =|Σ|称为字母表的基数,n =|S |称做S 的长度.定义2. 设序列S =s 1s 2…s n ,n i 是字母表中字母a i 在S 中的出现次数(1≤i ≤T ),则称SN (S )=(n 1,n 2,…,n T )是序列S的签名.若有序列S 1和S 2,其各自的签名为111112()(,,...,),T SN S n n n =222212()(,,...,),T SN S n n n =则称函数12(,)SD S S =122111max (),()T T P N i i i j j j i j I n n I n n ==⎛⎞−−⎜⎟⎜⎟⎝⎠∑∑为序列S 1和S 2的签名距离,其中P i I 和N j I 分别为示性函数,当12i i n n >时,P i I =1,否则P i I =0;当21j j n n >时,N j I =1,否则N j I =0.两条序列S 1和S 2的签名距离只反映了S 1和S 2在字母组成上的差异,没有考虑序列中字母的序关系.S 1和S 2的编辑距离ED (S 1,S 2)定义为将S 1映射到S 2所需要的最少操作步骤,其中的操作包括插入、删除和替代[19].计算S 1和S 2的编辑距离的基本方法是应用动态规划方法,将S 1和S 2的每个局部片段的编辑距离存储在一张最优比对表中,ED (S 1,S 2)就是表中的最后一个元素值.下面的定理给出了序列的签名距离和编辑距离的关系,这给后面的序列聚类算法中的剪枝策略提供了理论依据.定理1. 设有两条序列S 1和S 2,则值SD (S 1,S 2)和|S 1|+|S 2|分别是ED (S 1,S 2)的下界和上界,即SD (S 1,S 2)≤ED (S 1, S 2)≤|S 1|+|S 2|.证明:设序列S 1和S 2的签名分别为111112()(,,...,)T SN S n n n =和222212()(,,...,)T SN S n n n =.不失一般性,可设SN (S 1)向量中只有前k 个项比SN (S 2)中的对应前k 个项要小,121212121111,...,,,...,k k k k T Tn n n n n n n n ++<<≥≥,且设211k i i i n n =⎛⎞−≥⎜⎟⎝⎠∑ 121T j j j k n n =+⎛⎞−⎜⎟⎜⎟⎝⎠∑,则SD (S 1,S 2)=211k i i i n n =⎛⎞−⎜⎟⎝⎠∑.S 1经过ED (S 1,S 2)步插入、删除或替代操作后变为S 2,则在ED (S 1,S 2)步操作中,肯定存在一些操作要包括把S 1中的字母a 1,a 2,…,a k 的出现次数11112,,...,k n n n 增加为22212,,...,k n n n .因为增加字母出现次数的操作是插入操作和替代操作,且每个插入操作使得字母出现次数增1,而替代操作使得一个字母的出现次数增1,另一个字母的出现次数减1.所以,在ED (S 1,S 2)步操作中,S 1至少要经过SD (S 1,S 2)= 211k i i i n n =⎛⎞−⎜⎟⎝⎠∑步插入或替代操作才能转化为S 2,即SD (S 1,S 2)≤ED (S 1,S 2). 在S 1和S 2的最优比对表中,当进行回溯求解将S 1变为S 2的操作序列时,从表的(m ,n )位置开始(其中m =|S 1|, n =|S 1|),回溯到位置(0,0)终止,每次回溯要么是m 减1,要么是n 减1,要么是m 和n 同时减1,所以最多经过m +n −2(即|S 1|+|S 1|)步可以回溯到位置(0, 0).即ED (S 1,S 2)≤|S 1|+|S 2|.综上所述,SD (S 1,S 2)≤ED (S 1,S 2)≤|S 1|+|S 2|.□ 由定理1,易得出下面的推论:推论1. 设有3条序列S 1,S 2和S 3,若SD (S 1,S 2)≥|S 1|+|S 3|,则ED (S 1,S 2)≥ED (S 1,S 3).由编辑距离的定义易知,两条序列的编辑距离是一个度量,所以满足三角不等式,从而有以下定理:定理2. 设有3条序列S 1,S 2和S 3,已知S 1和S 2的编辑距离为ED (S 1,S 2),若ED (S 1,S 2)≥2×(|S 1|+|S 3|),则ED (S 1, S 3)≤ED (S 2,S 3).证明:由于|S 1|+|S 3|是ED (S 1,S 3)的上界,所以有ED (S 1,S 2)≥2×(|S 1|+|S 3|)≥2×ED (S 1,S 3),即ED (S 1,S 2)−ED (S 1,S 3)≥ ED (S 1,S 3).因为编辑距离满足三角不等式,所以ED (S 2,S 3)≥ED (S 1,S 2)−ED (S 1,S 3),从而有ED (S 1,S 3)≤ED (S 2,S 3). □因为对于长度分别为m 和n 的序列,它们之间编辑距离计算的时间开销为O (m ×n ),而计算两条序列的签名距离和长度的时间开销都是O (m +n ),若推论1和定理2中的前提条件满足,则可不必计算编辑距离,从而可以高效地进行编辑距离大小的比较.若推论1和定理2中的前提条件不满足,我们有可能只要进行编辑距离的部分706 Journal of Software 软件学报 V ol.21, No.4, April 2010 计算来进行大小比较.当对序列S =s 1s 2…s m 和P =p 1p 2…p n 进行比对求其编辑距离时,设其最优比对表为T (n +1行和m +1列),则有下面性质:性质1. (,)(,)1i j T i j T i j −−Δ−Δ≤.其中,T (i ,j )表示表T 中第i 行和第j 列的值,0≤i ≤n ,0≤j ≤m ,Δi =0或1,Δj =0或1,且0,0i j i j −Δ≥−Δ≥.证明:最优比对表的生成过程是:T (0,j )=j ,T (i ,0)=i (0≤i ≤n ,0≤j ≤m )和递归式(1,1)(,)(,)min (,1)1(1,)1i j T i j P s p T i j T i j T i j −−+⎧⎪=−+⎨⎪−+⎩(1,1),i j ≥≥且其中,如果s i =p j ,则P (s i ,p j )=0,否则,P (s i ,p j )=1.由归纳法易得证. □性质1反映了在生成的最优比对表中,任何一个值与其左边、左上角和上边近邻的差值的绝对值不超过1,表1所示的序列writers 和vintner 的最优比对表反映了性质1.这个性质可以用来证明下面的定理3.Table 1 Optimal alignment table of sequence writers and vintner表1 序列writers 和vintner 的最优比对表 T (i ,j )− w r i t e r s −0 1 2 3 4 5 6 7 v1 1234567 i2 2 2 23456 n3 3 3 3 3456 t4 4 4 4 3 456 n5 5 5 5 4 4 56 e6 6 6 6 5 4 5 6 r7 7 6 7 6 5 4 5定理3. 设序列S =s 1s 2…s m 和P =p 1p 2…p n (m ≥n )的最优比对表为T ,则当i ≤j ≤n 时,有T (i ,i )≤T (j ,j ).证明:我们证明T (i ,i )≤T (i +1,i +1),即可证明原定理.由表T 的生成过程: (1) 若T (i +1,i +1)=T (i ,i )+P (s i ,t i ),由P (s i ,t i )=0或1,有T (i ,i )≤T (i +1,i +1).(2) 若T (i +1,i +1)=T (i +1,i )+1,由性质1,|T (i +1,i )−T (i ,i )|≤1,分3种情况: ①T (i +1,i )−T (i ,i )=1,T (i +1,i +1)=T (i ,i )+2, T (i ,i )<T (i +1,i +1). ②T (i +1,i )−T (i ,i )=0,T (i +1,i +1)=T (i ,i )+1,T (i ,i )<T (i +1,i +1). ③T (i +1,i )−T (i ,i )=−1,T (i +1,i +1)=T (i ,i ).(3)若T (i +1,i +1)=T (i ,i +1)+1,证明与(2)类似,也有T (i ,i )≤T (i +1,i +1). 综合上述(1),(2)和(3),有T (i ,i )≤T (i +1,i +1). □ 定理3表明,在两序列的全局比对中,其局部等长前缀子序列的编辑距离具有非递减性质.如表1中两个不同阴影部分所示,有ED (wr ,vi )≤ED (wri ,vin ).对于不同长度的序列,下面的定理4给出了在进行其编辑距离的比较时,其中一个编辑距离只需部分求出即可进行比较.定理4. 设有序列S =s 1s 2…s m ,P =p 1p 2…p n (m ≥n )和Q ,且已知ED (S ,Q ),若存在某个k ≤n ,使得ED (s 1s 2…s k , p 1p 2…p k )−(m −n )≥ED (S ,Q )成立,则有ED (S ,P )≥ED (S ,Q ).证明:设S 和P 的最优比对表为T ,由性质1,T (n ,m )+1≥T (n ,m −1),T (n ,m −1)+1≥T (n ,m −2),…,T (n ,n +1)+1≥T (n ,n ).即T (n ,m )≥T (n ,n )−(m −n ).而由定理3可知,当k ≤n 时,T (n ,n )≥T (k ,k ).所以当存在某个k ≤n ,使得ED (s 1s 2…s k ,p 1p 2…p k ) −(m −n )≥ED (S ,Q )成立时,有ED (S ,P )=T (n ,m )≥T (n ,n )−(m −n )≥T (k ,k )−(m −n )≥ED (S ,Q ). □定理4表明,只要部分地计算ED (S ,P ),即可与ED (S ,Q )进行比较.如表1所示,若已知序列vintner 和某序列P 的ED (vintner,P )小于3,只需计算ED (wri ,vin )(其值为3),表中虚线部分的值无需计算即可推知ED (vintner , writers )≥ED (vintner ,P ).2.2 序列聚类算法GSClu 的实现过程给定t 条平均长度为L 的序列S 1,S 2,…,S t ,在编辑距离作为序列相似性度量的前提下,若采用基于两两比较的方法来进行聚类(如基于凝聚的层次聚类算法),算法时间复杂度为O (t 2L 2),在一般应用中,t 和L 都很大,这对算法的执行效率影响很大,由此我们可以从以下几个方面来考虑加速算法的运行:戴东波 等:基于整体和局部相似性的序列聚类算法707① 在算法的选择上,我们选用二分k 均值算法.二分k 均值算法最先是在文本聚类中提出来的[20],它避免了两两数据点之间的距离计算,时间复杂度是与数据集大小呈线性增长的.二分k 均值基本算法如下所示:二分k 均值算法:把所有数据点初始化为一个簇加入簇表.(1) 从簇表中选出一个总体相似度水平最低的簇C ;(2) 利用k -menas 方法二分簇C 为C 1和C 2;(3) 将C 1和C 2加入簇表中.重复(1)~(3)步,直到簇表中有k 个簇为止.当应用二分k 均值方法来聚类现有的序列数据时,由于其中用到了基本的k -means 算法,所以簇间数据点的移动和重新计算簇内质心称为核心问题.簇间数据点的移动涉及到每条序列数据与两个质心之间编辑距离的计算,如何利用剪枝策略高效地移动簇间数据点在下面的②和③中会加以讨论,这里给出如何计算簇内质心的启发式方法.对于序列数据组成的簇C ,使得函数(,)i i S C ED S S ∈∑最小的序列S 可定义为簇C 内的中心点[19].由于没有有效的方法来找到S ,可在C 中选一条序列S m 来近似S ,其中S m 使得(,)i i m S C ED S S ∈∑最小.文献[19]已证明,2(,)2(,),i i i m i S C S CED S S ED S S C ∈∈⎛⎞≤−×⎜⎟⎜⎟⎝⎠∑∑所以S m 是S 的一个有界近似.由于找到S m 要进行C 中所有序列两两编 辑距离的计算,所以会使得二分k 均值算法关于序列数t 仍是二次项时间复杂度的.下面给出一种启发式的质心求解方法,关于序列数t 是多项式时间复杂度的.假设簇C 中的t ′(t ′<t =条序列为S 1,S 2,…S t ′,我们先创建一张(T +1)×Q 的表Tab ,其中(T +1)行表示字母表中的T 个字母和空格符“−”(在比对中表示插入一个字母),Q 列对应当前比对结果.Tab [i ,j ]表示比对结果中第j 列中的第i 个字母在此列中的出现次数.我们用著名的Needleman-Wunsch 方法[21]先比对S 1和S 2,将结果填入表Tab 中,然后比对表Tab 和S 3,接着更新表Tab ,继续比对Tab 和S 4,再更新表Tab ,…,直到最后比对完序列S t ′,得到更新的表Tab .如表2所示,假设字母表是Σ={a ,b ,c },当前比对的结果放在Tab 表中.假设Tab 表和下一条序列aabbc 进行比对,比对方法仍可用Needleman-Wunsch 方法,只是把Tab 表的每一列当成一个字母,比对距离是序列aabbc 中每个字母与Tab 中每列的每个字母比对的加权之和.如图3所示,在Tab 表和序列aabbc 比对结果中a 和Tab 表中第1列比对,则这列比对距离是0×0.75+1×0.25=0.25,因为在表2中的当前比对结果表Tab 的第1列中,a 的出现概率是0.75,c 的出现概率是0.25.更新表结果只是在原表每列中增加所比对字母的计数,新增加的列也要加入表中.结果如表3中更新后的Tab 表所示,其中第2列C 2是新添加的列,即字母a 和空格符号“−”的比对结果,而第1列C 1的更新是在表2中C 1列的基础上,通过对a 的出现次数增1的操作完成的.表Tab 可以看作是当前序列比对的一个摘要(profile),它刻画了当前所有比对序列的“一致性”水平.当C 中所有序列比对完毕后,从最后更新的Tab 表中提取一致序列作为C 的质心,一致序列就是从Tab 表每列中提取出现次数最多的字母组成的序列.从后面的实验可以看到,这样求得的近似质心能够比较准确地逼近有界质心S m .设簇C 中逐步比对Tab 表和序列的距离总和为T _Score ,T _Score 可用来估算簇的总体相似性水平.由于Tab 表和序列比对距离是与序列长度相关的,所以可用规范化后的距离值C _Sim =_T Score t L ′′来表示簇C 中序列的总体相似性水平,其中L ′是簇C 中各序列的平均长度,C _Sim 越大,C 中各序列的相似性水平越低.所以,在二分k 均值算法的第1步,我们选择C _Sim 最大的簇作为即将进行二分的候选簇.Table 2 Current alignment result in table Tab表2 当前在Tab 表中的比对结果C 1 C 2 C 3 C 4 C 5 C 6 b 0 0 4 0 4 0c 1 0 1 2 0 2− 0 1 0 2 1 1 Table 3 Updated table Tab 表3 更新后的Tab 表 C 1C 2C 3C 4 C 5 b 0 3 0 3 0 c 1 1 2 0 1 −0 0 1 1 1708Journal of Software 软件学报 V ol.21, No.4, April 2010Fig.3 图3 Tab 表与序列aabbc 的比对结果② 在处理簇间数据点的移动时,我们采取剪枝策略避免不必要的编辑距离计算.假设在应用二分k 均值算法时,当前的两个质心是C 1和C 2,p 点表示序列集中的任何一条序列,ED (C 1,C 2)已知.当找到离p 点最近的簇时,需计算ED (p ,C 1)和ED (p ,C 2),并进行大小比较.由第2.1节中的推论1和定理2可知:Ⅰ.当max(SD (p ,C 1),ED (C 1, C 2)/2)≥|C 2|+|p |时,有ED (p ,C 2)≤ED (p ,C 1),p 点放入C 2所代表的簇.Ⅱ.当max(SD (p ,C 2),ED (C 1,C 2)/2)≥|C 1|+|p |时,有ED (p ,C 1)≤ED (p ,C 2),p 点放入C 1所代表的簇.若上述Ⅰ,Ⅱ条件不满足,需计算ED (p ,C 1)和ED (p ,C 2)并进行比较,但在进行编辑距离的直接计算时,我们也有可能没必要把整个编辑距离完全计算出来,这时有下面③的剪枝策略.③ 对于序列S ,我们设计S 的一个概貌向量V S ={n 1,n 2,…,n T ,d 1,d 2,...,d T },其中n i (1≤i ≤T )是S 签名向量中的值,d i (1≤i ≤T )是S 中字母a i 到序列首字母的距离之和.S 的概貌向量V S 反映了S 中各字母组成和位置的基本情况.在ED (p ,C 1)和ED (p ,C 2)未计算之前,我们是不能准确知道ED (p ,C 1)和ED (p ,C 2)之间的大小的,但通过一遍扫描序列得到序列p ,C 1和C 2各自的概貌向量以及L 1(V p ,1C V )和L 1(V p ,2C V ),其中L 1表示曼哈顿距离函数,V p ,1C V 和2C V 分别表示序列P ,C 1和C 2的概貌向量.若L 1(V p ,1C V )≤L 1(V p ,2C V ),由第2.1节中定理4,则先计算ED (p ,C 1),后计算ED (p ,C 2)时期望只需计算p 和C 2的某个等长前缀子序列的编辑距离.尽管序列之间概貌向量的L 1距离不能等同于编辑距离,但当ED (p ,C 1)和ED (p ,C 2)相差较大时,它可有效指导编辑距离的计算次序,且ED (p ,C 1)和ED (p ,C 2)中较大者的计算一般会在较短的等长前缀子序列编辑距离计算完毕后停止.综合上述①~③点,基于整体相似性的序列聚类算法GSClu 如下所示:GSClu 算法.输入:t 条平均长度为L 的序列集SS ={S 1,S 2,…,S t },参数k ;输出:k 个序列簇.{CL ←SS ; CN =1; //初始化簇表CL 为SS ,开始只有一个全序列组成的簇SS ,CN 计数簇的个数for (i =1;i ≤t ;i ++)一遍扫描序列集SS ,计算S i 的签名SN (S i )和概貌向量;i S Vend for ;while (CN <k )从簇表CL 中选一个距离值C _Sim 最大的簇C ;从C 中选取最长序列和最短序列作为质心CO 1和CO 2;计算出ED (CO 1,CO 2),1CO V 和2;CO Vwhile (C 中所有序列不再在CO 1和CO 2所代表的簇间移动)for (C 中每条序列S ′)if ( max (SD (S ′,CO 1),ED (CO 1,CO 2)/2)≥|CO 2|+|S ′|)序列S ′放入CO 2所代表的簇C 2;else if (max(SD (S ′,CO 2),ED (CO 1,CO 2)/2)≥|CO 1|+|S ′|)序列S ′放入CO 1所代表的簇C 1;else if (L 1(V S ′,1CO V )≥L 1(V S ′,2CO V ))先计算ED (S ′,CO 2);若存在S ′和CO 1的等长前缀子序列满足定理4,则停止计算并把S ′放入CO 2所代表的簇C 2,否则继续计算完ED (S ′,CO 1),然后决定S ′点的放入.戴东波 等:基于整体和局部相似性的序列聚类算法709else先计算ED (S ′,CO 1); 若存在S ′和CO 2的等长前缀子序列满足定理4,则停止计算并把S ′放入CO 1所代表的簇C 1,否则继续计算完ED (S ′,CO 2),然后决定S ′点的放入.end for ;对簇C 1和C 2中的序列分别进行逐步比对求出Tab 表,并从Tab 表中提取一致序列更新各自的质心CO 1和CO 2;end while ;CN =CN +1;计算簇C 1和C 2各自的C _Sim 值,并把C 1和C 2加入到簇表CL 中;end while ;}因为在文献[22]中,k -means 算法的初始质心采用启发式方法:首先在数据集中随机选取一个质心,然后对于每个后继初始质心,选择离选取过的初始质心最远的数据点.所以在算法GSClu 中,当用k -means 方法二分选定的簇C 时,我们不是随机初始化质心,而是分别选最长序列和最短序列来作为初始化质心.因为在一般情况下,这样操作比随机选取质心的方法更能加快算法的收敛.GSClu 的最坏时间复杂度是O (ITER ×k ×t ×L 2),ITER 是内循环k -means 算法收敛时的平均循环次数.由于GSClu 不采用基于序列两两比对的方法,且通过启发式方法获得质心,使得整个算法关于序列数t 是多项式时间复杂度的.当序列数据集SS 的自然分类情况比较明显时,在移动簇间数据点时采取的剪枝策略可以有效地加速算法的运行.3 基于局部相似性的序列聚类算法LSClu现有很多基于局部相似性的序列聚类算法都采用频繁子模式的方法进行[13,15,16].下面先给出频繁子模式的定义:定义3. 设有长度分别为n 和k 的序列S =s 1s 2…s n 和S ′=t 1t 2…t k ,如果n ≥k ,且存在有序整数集11i ≤< 2...k i i n <≤,使得121,2,...,k i i k i t s t s t s ===,则称S ′是S 的子序列,也称S 支持S ′(或S ′被S 支持),记做S ′p S .若进一步地,对于任意的j (1≤j ≤k −1),都有11j j i i S S d +−≤+成立,则称S ′在S 中满足d -gap 约束.定义4. 设有序列集SS =S 1,S 2,…,S p ,给定一条序列S 和支持度阈值α,若{|,}S S SS S S p α′′′∈≥且p ,则称序列S 是序列集SS 中的子模式.子模式挖掘算法最先是在文献[23]中提出来的,其主要思想是先产生候选项,然后利用Apriori 反单调性质进行剪枝.文献[24]给出了子模式的更高效挖掘算法PrefixSpan.算法PrefixSpan 为了避免大量候选项的产生和多次扫描整个数据库,先迭代地求出子模式的前缀,然后在前缀投影数据库中求出频繁项来逐步增长子模式.文献[16]给出一种有效挖掘强区分度子序列(discriminating subsequence)的方法CONTOUR,对给定序列数据库中的每条序列S ,只用S 所支持的一条强区分度子模式序列来表征S ,然后在强区分度子序列的基础上定义序列的相似度函数,用层次凝聚的方法对序列数据库进行聚类.尽管算法CONTOUR 改进了文献[15]中用多个子模式表征序列S 的方法,在聚类质量和效率上有所提高,但仍存在以下两个方面的问题:(1) CONTOUR 算法从序列数据库中找到的子模式不具有gap 约束,即子模式中各元素在被支持序列中的距离可任意大,这不符合很多应用场合的要求,且降低了算法的执行效率.文献[25]中指出,很多实际中的序列数据都只有短程记忆性,即在一个字母c 之前的子序列已知的前提下,c 在序列中出现的概率可近似认为只与这个子序列至多L 长的后缀序列片段有关.此外,在生物序列中,许多功能片段在整个序列上也满足gap 约束,即功能片段中各元素是处于某个局部区域的,而不会随机、均匀地散布在整个序列的各个位置中.如图2中所示的子序列CCAA- - A 就满足2-gap 约束.(2) 用文献[24]中PrefixSpan 方法为每条序列S =s 1s 2…s n 找到所支持的子模式有很多,CONTOUR 算法吸取。

（完整版）高级英语第二册LESSON1课后答案Pub Talk and the King's English 课后练习题I. Write short notes on: Carlyle, and Lamb.Suggested Reference Books[SRB]1. The Oxford Companion to English Literature2. Any standard book on the history of English literature3. Encyclopaedia BritannicaIII. Questions on appreciation:1. In what way is “pub talk” connected with “the King’s English”? Is the title of the piece well-chosen?2. Point out the literary and historical allusions used in this piece and comment on their use.3. What is the function of para 5? Is the change from "pub talk" to "the King's English" too abrupt?4. Do the simple idiomatic expressions like "to be on the rocks, out of bed on the wrong side, etc., " go well with the copious literary and historical allusions the writer uses? Give your reasons.5. Does the writer reveal his political inclination in this piece of writing? How?IV. Paraphrase:1. And it is an activity only of humans. (para 1)2. Conversation is not for making a point. (para 2)3. In fact, the best conversationalists are those who are prepared to lose. (para 2)4. Bar friends are not deeply involved in each other's lives. (para 3)5. it could still go ignorantly on (para 6)6. There are cattle in the fields, but we sit down to beef(boeuf). (para 9)7. The new ruling class had built a cultural barrier against him by building their French against his own language. (para11)8. English had come royally into its own. (para 13)9. The phrase has always been used a little pejoratively and even facetiously by the lower classes. (para 15)10. The rebellion against a cultural dominance is still there. (para 15)11. There is always a great danger that "words will harden into things for us. " (para 16)12. Even with the most educated and the most literate, the King's English slips and slides in conversation. (para 18) V. Translate paras 9--11 into Chinese.VI. Look up the dictionary and explain the meaning of the italicized idiomatic phrases:1. their marriage may be on the rocks (para 3)2. they got out of bed on the wrong side (para 3)3. the conversation was on wings (para 8)4. the Norman lords of course turned up their noses at it (para 10)5. we ought to think ourselves back into the shoes of the Saxon peasant (para 11)6. English had come royally into its own. (para 13)7. we sit up at the vividness of the phrase (para 18)VII. Discriminate the following groups of synonyms:1. ignorant, illiterate, uneducated, unlearned2. jeer, scoff, sneer, gibe, floutVIII. Give ten synonymous and/or related words of the word conversation (meaning 'communication'). Give words of the same part of speech.[SRB]1. Roget ' s International Thesaurus2. Webster's Collegiate ThesaurusIX. Give ten antonymous and/or contrasted words of the word intricate. Give words of the same part of speech.[SRB]1. Roget's International Thesaurus2. Webster's Collegiate ThesaurusX. Look up the dictionary, find out from what languages the following words are borrowed, and then put them into Chinese:1. buffet 8. soireé 15. attaehé2. cuisine 9. cloisonné 16. liaison3. lemonade 10. omelette 17. déjàvu4. liqueur 11. restaurateur 18. encore5. déjeuner 12. repertoire 19. discothèque6. menu 13. coup d'état 20. chandelier7. salon 14. corps de balletXI. The following sentences all contain metaphors or similes. Explain their meaning in plain, non-figurative language:1.no one has any idea where it will go as it meanders or leaps and sparkles or just glows.2.they got out of bed on the wrong side is simply not a concern.3.They are like the musketeers of Dumas who, although they lived side by side with each other, did not delve into each other's lives or the recesses of their thoughts and feelings.4.suddenly the alchemy of conversation took place5.The glow of the conversation burst into flames.6.we ought to think ourselves back into the shoes of the Saxon peasant.7.The Elizabethans blew on it as on a dandelion clock, and its seeds multiplied, and floated to the ends of the earth.8.I have an unending love affair with dictionaries9. Otherwise one will bind the conversation, one will not let it flow freely here and there.10. We would never have gone to Australia, or leaped back in time to the Norman Conquest. XII. Study the model given below. Then read the next two paragraphs and show how coherence and unity is improved by the use, of transitional devices.Model: But this is only one aspect of the problem. Another, no less essential, is the wider gap between generations since the rate of social development has speeded up. The tastes and habits of young people today differ markedly from those of the young people of the thirties, let alone of the twenties. Still influenced by the tastes and habits of their own youth, the "fathers" are inclined to think these habits and tastes are absolutes and to deny their children the right to independent creativity which they demanded from their own parents. Hence the artificial conflicts, in which a dance or the width of trousers is elevated to the dignity of crucial issues. The writer uses the following transitional devices:1) Transitional words and expressionsbut another still hence2) Pronoun referencethose their these they3) Repetition of important wordstastes and habits young people1. And since we (teenagers) are so new, many people have some very wrong ideas about us. For instance, the newspapers are always carrying advice-columns telling our mothers how tohandle us, their "bewildered maladjusted offspring, " and the movies portray us as half-witted bops (hoodlums-ed. ); and in the current best sellers, authors recall their own confused, unhappy youth. On the other hand, speakers tell us that these teen-years are the happiest and freest of our lives, or hand us the "leaders of tomorrow, forge on the future" line. The general opinion is that teen-agers are either car-stealing, dope-taking delinquents, or immature, weepy adolescents with nothing on our minds but boys (or girls as the case may be ). Most adults have one or two attitudes toward the handling of teens--some say that only a sound beating will keep us in line; others treat us as mentally unbalanced creatures on the brink of insanity, who must be pampered and shielded at any cost.2. As of today, I am fed up with the food served in the campus dining hall. My disenchantment started in September---the day I bit into a hamburger to find myself staring at a long strand of grey hair that trailed out of the meat, through the mayonnaise, and over the edge of the bun. After that, I was not much surprised by the little things I came across in October and November: bugs in the salad and bobby pin in the meatloaf, for example. Then in December the food was worse--and a little dirtier. For Christmas dinner, for in- stance, the cook gave me a thin slice of rolled turkey, straight out of the can, and dished up a cock-roach in my pudding. Even that was excusable (nobody is perfect), but what happened today is not" I had already eaten most of my clam chowder before I found it, at the bottom of the bowl, nestled among the diced potatoes and the chopped onions: one band-aid, slightly used.XIII. Topics for oral work:1. In your opinion, what makes or spoils a good conversation?2. Is spoken English different from written English? In what ways are they different?XIV. Write a short composition describing some of the peculiarities of spoken EnglishPub Talk and the King's English 课后练习题答案Ⅰ .1. Carlyle : Thomas Carlyle (1795-1881), English essayist and historian born at Ecclefechan,a village of the Scotch lowlands. After graduating from the University of Edinburgh, he rejected the ministry, for which he had been intended, and determined to he a writer of hooks. In 1826 he married Jane Welsh, a well-informed and ambitious woman who did much to further his career. They moved to Jane' s farm at Craigenputtoeh where they lived for 6 years (1828-1834 ). During this time he produced Sartor Resartus (1833-1834), a book in which he first developed his char- acteristic style and thought. This book is a veiled sardonic attack upon the shams and pretences of society, upon hollow rank, hollow officialism, hollow custom, out of which life and usefulness have departed. In 1837 he published The French Revolution, a poetic rendering and not a factual account of the great event in history. Besides these two masterpieces, he wrote Chartism (1840), On Heroes, hero Worship, and the Heroic in History (I841), Past and Present (1843) and others. "Carlylese", a peculiar style of his own, was a compound of biblical phrases, col loquialisms, Teutonic twists, and his own coinings, arranged in unexpected sequences. One of the most important social critics of his day, Carlyle influenced many men of the younger generation, among them were Mathew Arnold and Ruskin.2. Lamb : Charles Lamb (1775-1834), English essayist, wasborn in London and brought up within the precincts of the ancient law courts, his father being a servant to an advocate of the inner Temple. He went to school at Christ's Hospital, where he had for a classmate Coleridge, his life-long friend. At seventeen, he became a clerk in the India House and here he worked for 33 years until he was re-tired on a pension. His devotion to his sister Mary, upon whom rested an hereditary taint of insanity, has done al-most as much as the sweetness and gentle humor of his writings to endear his name. They collaborated on several books for children, publishing in 1867 their famous Tales from Shakespeare. His dramatic essays, Specimens of English Dramatic Poets (1808), established his reputation as a critic and did much in reviving the popularity of Eliza-be then drama. The Essays of Ella, published at intervals in London Magazine, were gathered together and republished in two series, the first in 1823, the second ten years later. They established Lamb in the title which he still holds, that of the most delightful of English essayists.Ⅱ.1.A good conversation does not really start from anywhere, and no one has any idea where it will go. A good conversation is not for making a point. Argument may often be a part of it, but the purpose of the argument is not to convince. When people become serious and talk as if they have something very important to say, when they argue to convince or to win their point, the conversation is spoilt.2. The writer likes bar conversation very much because he has spent a lot of time in pubs and is used to this kind of conversation. Bar friends are companions, not intimates. They are friends but not intimate enough to be curious about each other'sprivate life and thoughts.3. No. Conversation does not need a focus. But when a focal subject appears in the natural flow of conversation, the conversation becomes vivid, lively and more interesting.4. The people talked about Australia because the speaker who introduced the subject mentioned incidentally that it was an Australian who had given her such a definition of "the King's English. " When the people talked about the resistance in the lower classes to any attempt by an upper class to lay down rules for "English as it should be spoken", the conversation moved to Norman England because at that time a language barrier existed between the Saxon peasants and the Norman conquerors.5. The Saxon peasants and their Norman conquerors used different words for the same thing. For examples see paragraph 9.6. The writer seems to be in favor of bilingual education. He is against any form of cultural barrier or the cultural humiliation of any section or group of people.7. The term "the Queen's English" was used in 1953 by Nash because at that time the reigning monarch was a queen, Elizabeth I. The term "the King's English" is the more common form because the ruling monarch is generally a king. Those who are not very particular may use the term "the King's English", even when the ruling monarch is a queen. In 1602, Dekker used the term "the King's English", although the reigning monarch was still Queen Elizabeth.8．“The King’s English” was regarded as a form 0f racial discrimination during the Norman rule in England about 1154—1399．9．The writer thinks “the King’s English” is a classrepresentation of reality．1t is worth trying to speak “the King’s English”，but it should not be 1aid down as an edict，and made immune to change from below．The King’s English is a model a rich and instructive one- but it ought not to be an ultimatum．10．During the Norman period，the ruling class spoke Anglo—French while the peasants spoke their native Saxon language．Language bears the stamp of the class that uses it．The King’s English today refers to the language used by the upper，educated class in England．Ⅲ．1．The title of this piece is not well chosen．It misleads the readers into thinking that the writer is going to demonstrate some intrinsic or linguistic relationship between pub talk and the King’s English．Whereas the writer．in reality，is just discoursing on what makes good conversation．The King’s English is connected with “pub talk” when the writer describes the charming conversation he had with some people one evening in a pub on the topic “the King’s English” to illustrate his point that bar conversation in a pub has a charm of its own．2．1n this essay the writer alluded to many historical and literary event such as the Norman conquest，the saloons of 18th century Paris，and the words of many a man of letters．For a short expository essay like this，the allusions used are more than expected and desirable．3．Paragraph 5 is a transition paragraph by means of which the writer passes from a general discourse on good conversation to a particular instance of it．But one feels the change from “pub talk” to “the King's English” a bit too abrupt．4．The simple idiomatic expressions like "to be on the rocks，out of bed on the wrong side，etc．”may be said to go well with the copious literary and historical allusions the writer used for an informal conversational style to Suit the theme of this essay in which the writer tries to defend informal uses of language．5．The writer’s attitude towards “the King’s English” shows that he is a defender of democracy．Ⅳ．1．And conversation is an activity which is found only among human beings. (Animals and birds are not capable of conversation.)2．Conversation is not for persuading others to accept our idea or point of view．3．In fact a person who really enjoys and is skilled at conversation will not argue to win or force others to accept his point of view．4．People who meet each other for a drink in the bar of a pub are not intimate friends for they are not deeply absorbed or engrossed in each other’s lives．5．The conversation could go on without anybody knowing who was right or wrong．6．These animals are called cattle when they are alive and feeding in the fields；but when we sit down at the table to eat．we call their meat beef．7．The new ruling class by using French instead of English made it difficult for the English to accept or absorb the culture of the rulers.8．The English language received proper recognition and was used by the King once more.9．The phrase, the King’s English, has always been used disrespectfully and jokingly by the lower classes. The workingpeople very often make fun of the proper and formal language of the educated people.10．There still exists in the working people, as in the early Saxon peasants, a spirit of opposition to the cultural authority of the ruling class.11．There is always a great danger that we might forget that words are only symbols and take them for things they are supposed to represent. For example, the word “dog” is a symbol representing a kind of animal. We mustn’t regard the word “dog” as being the animal itself.12．Even the most educated and literate people do not use standard, formal English all the time in their conversation.V．See the translation of the text．Ⅵ·1. on the rocks：metaphor，comparing a marriage to a ship wrecked on the rocks2．get out of bed on the wrong side: be in a bad temper for the day (The meaning is perhaps derived from the expression “You got out of bed the wrong way”. It was an ancient superstition that it was unlucky to set the left foot on the ground first on getting out of bed.) 3．on wings：metaphor，comparing conversation to a bird flying and soaring．It means the conversation soon became spirited and exciting．4．turn up one’s nose at：scorn；show scorn for5．into the shoes：metaphor(or more appropriately an idiomatic expression)，think as if one were wearing the shoes of the Saxon peasant，i．e．as if one were a Saxon peasant6 come into one’s own：receive what properly belongs to one，especially acclaim or recognition657．sit up at：(colloquial)become suddenly alert and takenotice ofⅦ．1．ignorant指缺乏知识，可以是就整体而言(如an ignorant man)，也可以是就某一具体方面或问题而言(如ignorant of the reason of their quarrel对他们争吵的起因毫无所知)；illiterate意为缺乏文化修养，尤指读写能力的缺乏；uneducated指没有受到正规的、系统的学校教育；unlearned意为学问不富(未必无知)，既可指一无所长，又可指某一方面所知有限，如unlearned in science，意为对科学懂得有限，但对其他学科，如文学、哲学等，倒可能是很精通的。