94695

COMPUTER RESEARCH

Конспект урока

Иностранные языки, филология и лингвистика

The IBM Computer Science team explores foundational issues that confront the computing industry today. Because theory cuts across every aspect of computer science, they tend to interact with a large number of other research teams. The IBM research center has ongoing projects in the following areas...

Английский

2015-09-15

85.5 KB

0 чел.

116

UNIT IX

COMPUTER RESEARCH

INTRODUCTORY

INTRODUCTORY TEXT

    The IBM Computer Science team explores

                                           foundational issues that confront the computing industry today. Because theory cuts across every aspect of computer science, they tend to interact with a large number of other research teams. The IBM research center has ongoing projects in the following areas:

-Algorithms: How can you get computers to solve problems efficiently?

-Complexity: What computational resources (time, storage, etc) do problems inherently require?

-Database: What models and algorithms are useful in helping computers store and retrieve information efficiently?

-Web: What is the overall structure of the World-wide Web, and how can algorithms take advantage of this?

IBM’s focus on algorithms falls under the following broad categories: (1) Massive data set algorithms: The design of algorithms that work on massive data sets is inevitable from a practical point of view. These algorithms have to work with very limited main memory. Three computational models have been proposed in this setting: the data stream model where the algorithm can make one or few passes over the data; the sampling model, where the algorithm is allowed random access; and the sublinear model, where the running time of the algorithm has to be sublinear in its input size. (2) Approximation algorithms: To overcome the curse of NP-hardness, developing approximation algorithms becomes important. The primal-dual and the semi-definite programming methods have been of immense help in this regard. These tools have yielded remarkably powerful algorithms to to solve many important combinatorial optimization problems. (3) Aggregation algorithms: Developing algorithms for improving the performance of large-scale databases and information retrieval system is a challenging task. Recent interests include aggregation algorithms with performance guarantees and static pruning methods for reducing the index size in IR systems. (4) Other algorithms: Other interests of the IBM research team include lattice algorithms, online algorithms, and property testing algorithms.

Complexity theory is a field that concerns itself with the intrinsic computational difficulty of problems. It focuses on the effect of limiting natural computational resources, e.g. time and space, on the class of problems that need to be solved. The emphasis is on generality, and this is usually achieved by defining appropriate models of computation. The classical Turing machine captures the notion of general computation. In dealing with specific classes of problems, it has been fruitful to also consider other models such as circuits, probabilistic Turing machines, random access machines, interactive proof systems, sampling/data stream models etc. The group at IBM Almaden has focused on a variety of problems in this area. Recent work has addressed the complexity of lattice problems, zero-knowledge protocols, fault-tolerant computing, property testing, derandomization, communication complexity, sampling, an data stream algorithms.     

There is a long history of research at IBM on the theory of databases, going back to the early days of the relational model, which was invented, developed, and studied extensively here. Their main database focus now, both in theory and in more practical projects, is on less traditional ways of storing data, such as in multimedia databases and in emerging databases and data service technologies for the Internet. In the area of multimedia databases, IBM investigated aggregation algorithms for combining fuzzy information from multiple sources

Algorithmic tools for searching and mining the web are becoming increasingly sophisticated and vital. In this context, algorithms that use and exploit structural information about the web perform better than generic methods in both efficiency and reliability. The IBM research center provides a characterization of the web that shows that the web emerges as the outcome of a number of essentially independent stochastic processes that evolve at various scales. A striking consequence of this scale invariance is that the structure of the web is “fractal”- cohesive sub-regions displays the same characteristics as the web at large. An understanding of this underlying fractal nature is therefore applicable to designing data services across multiple domains and scales. We describe potential applications of this line of research to optimized algorithm design for web-scale data analyses.

The IBM focuses on two kinds of Web-related research. The first is understanding and modeling the seemingly chaotic Web and the second is developing algorithms that exploit this understanding. Several macro-level micro-level connectivity properties of the Web were studied and the bow-tie model was proposed to abstract the connectivity properties. A simple stochastic model was constructed to explain experimentally observed phenomena; such models can be used to predict the evolution of the Web.

TOPICAL VOCABULARY

  1.  massive data set algorithms          алгоритмы большого

                                                                      объёма данных

  1.  data stream model                         модель потока данных
  2.  sampling model                            модель выборочного типа
  3.  random access                              прямой (произвольный)

                                                                      доступ

  1.  sublinear model                            сублинейная модель
  2.  approximation algorithms            алгоритмы

                                                                      аппроксимирующего

                                                                      типа

  1.  primal-dual method                      основной двухвариантный

                                                                      метод

  1.  semi-definite method                    метод нечёткого типа
  2.  diverse                                           разнообразный
  3.  aggregation algorithms                 алгоритмы совокупного

                                                                      типа 

  1.  information retrieval system         система возвращения

                                                                       информации

  1.  performance guarantees                гарантии эффективности

                                                                       эксплуатации

  1.  static pruning method                   статический метод

                                                                      отсечения решений

  1.  lattice algorithm                           алгоритм решётчатого

                                                                      типа

  1.  online algorithm                           интерактивный алгоритм
  2.  property testing algorithm           алгоритм проверки

                                                                      свойств

  1.  intrinsic                                        свойственный,

                                                                      внутренний

  1.  Turing machine                            машина Тьюринга

                                                                      (гипотетический

                                                                       вычислитель)

  1.  interactive proof systems             системы интерактивных

                                                                       испытаний

  1.  fault-tolerant                                отказоустойчивый
  2.  relational model                           модель отношения,

                                                                      сравнения

  1.  fuzzy information                        нечёткая информация
  2.  generic method                            базовый (общий) метод
  3.  fractal structure/nature                фрактальная

                                                                     структура/природа

  1.  cohesive                                      способный к сцеплению,

                                                                      связующий

  1.  bow-tie model                             модель в виде завязанного банта

 EXERCISES

1. Read the introductory text again and answer these questions.

  •  What ongoing projects does IBM develop?
  •  What categories does their focus on algorithms fall under?
  •  What is the IBM’s complexity theory concerned with?
  •  Can you name the ways of storing data employed in the IBM?
  •  What characterization of the Web do IBM researchers give?
  •  What for was the bow-tie model proposed?     

2. Find in the text equivalents for the following words and word-combinations:

разрабатываемые проекты; круг интересов в ч-л.; с практической точки зрения; неизбежный; сотрудничать с; исследовать проблемы; делиться на категории; время работы; вычислительная модель; преодолеть проблему; улучшить работу; сложная задача; крупномасштабные базы данных; заниматься/интересоваться ч-л.; хранение данных; надёжность; потенциальное применение; исследование всемирной сети; экспериментально выявленное явление.

3. Read the text. Do the tasks given below.

CAN COMPUTERS OUTSMART US?

If the world’s population continues to grow at its present rate- doubling every 40 years- there isn’t going to be enough room for us all on Earth by the year 2600. The only sounds in the room are the clicking of the pressure pads and the whirring of the computer. We need to become more complex if biological systems are to keep ahead of electronic ones. At the moment computers have an advantage of speed but they show no sign of intelligence. This is not surprising as our present computers are less complex than the brain of an earthworm, a species not known for its intellectual powers. But computer’s speed and complexity double every eighteen months and this will probably continue until computers have a similar complexity to the human brain.

But will computers ever show true intelligence, whatever it might be? It seems to me that if very complicated chemical molecules can operate in humans to make them intelligent, then equally complicated electronic circuits can also make computers act in an intelligent way. And if they are intelligent, they can presumably design computers that have even greater intelligence and complexity.

  •  Choose the words given below to complete the text:

Twenty years ago we relied mainly on TVs, radios and stereo equipment to provide entertainment in our homes, (1)___ their place is quickly being taken over by computers. (2)___ do we use computers to lighten or load at work, increasingly we are using computers for fun. (3)___. More and more home computers have access to the Internet. (4)___ we can now access a huge range of leisure facilities in our homes, such as reading newspapers on screen, shopping from home, (5)___ downloading music and films. Developments in optical fibre cables and DVD videos CDs mean that we can now download entire albums or feature films onto our computers and soon video players and hi-fis could become totally obsolete

But now; but then; also; it’s true that; as well; not only; so, in this sense; but more importantly; this means that; as well as; after all.

  •   Make sentences out of the two parts:

1. Computers’ speed and complexity

A. will have a similar complexity to the human brain.

2. To keep ahead of electronic systems

B. may become the only sounds in the room in the future.

3. Is it possible that computer

C. double every ten years.

4. The clicking of the pressure pads and computer whirring

D. no sign of intelligence.

5. At the moment computers show

E. people need to become more complex.

DISCUSSION

Working in pairs discuss the following problems:

  1.  What role does the computer play in your everyday life?
  2.  Do you think it will be the same in ten years’ time?
  3.  Do you use e-mail or the Internet? If you do, what do you use them for?

SUPPLEMENTARY READING

    VIDEO GAMES  

                                               

Video games these days are extremely popular. One in four households in Britain has a Playstation and in 1999 the video game industry made nearly a billion pounds, which was 60 percent more than cinema box office takings.

So, why are video games so popular? Well, they combine very fast moving, well-designed graphical images with very interesting sound design and music. But crucially they’re interactive, so they can change according to what you do from moment to moment, so the computer system concentrates on what you are saying to it, and poses you very interesting challenges and difficulties at very high speed.

The first commercial video game came along in 1971. IT was called Computer Space. Unfortunately it wasn’t very successful because it was a very complicated game involving spaceships and torpedoes and black holes and so forth. The same man who had invented that invented a game called Pong in 1972 and that’s when the video game explosion really took off. It was a very simple tennis game.

The very early video games like Pong just took place on one screen and the boundaries of the screen were the boundaries of the playing area. But then the space in video games started to get larger. The games started to scroll from side to side or up and down, so that the playing area became larger than the total size o one screen. The graphics in games slowly became more colourful and more detailed and then the big innovation took place in the 90’s, which was the invention of full 3D. This meant that you started to control characters who explored fully realized, solid 3D environments. You could wander round landscapes and buildings and look at them from any angle.

I think video games are close to becoming an art form in itself. Certainly, when cinema was only around 30 years old, as video games are today, a lot of people thought films were mindless entertainment and rotted peoples’ brains and were no good. But now we know that cinema is an art form and we have film critics who can analyse films and enhance our enjoyment of them, so in the future it will be true of video games as well. The current research in video games is concentrating on artificial intelligence. People want to play video games that give a greater illusion of interacting with real characters.       

 

FINAL TEST

  •  Put the following sentences in the same sequence as the information is arranged in the introductory text (Расположите следующие предложения в той же последовательности как информация представлена в вводном тексте)

1.  A. Complexity theory developed by the IBM research center is concerned with the intrinsic computational difficulty of problems.

     B. The bow-tie model was proposed to abstract the connectivity properties of the Web.

     C. The IBM investigated aggregation algorithms for combining fuzzy information from multiple sources.

     D. Other algorithms developed by the IBM include lattice algorithms, online algorithms, and property testing algorithms.

  •  Choose the right English equivalent to the following Russian sentence (Выберите верный английский эквивалент следующему русскому предложению)

 Алгоритмические инструменты для исследования сети постоянно усложняются.

2. A. Algorithmic tools for searching the web are becoming increasingly vital.

        B.  Algorithmic tools for searching the web are becoming more reliable.

       C. Algorithmic tools for searching the web are becoming increasingly sophisticated.

  •  Choose the right Russian equivalent to the following English sentence (Выберите верный русский эквивалент следующему английскому предложению)

Because theory cuts across every aspect of computer science, the IBM tends to interact with a large number of other research teams.

3.  A. Так как теория полностью соответствует компьютерной науке, IBM взаимодействует с большим количеством исследовательских групп.

     B. Так как теория затрагивает все аспекты компьютерной науки,

IBM взаимодействует с большим количеством исследовательских групп.

     C. Так как теория идёт в разрез с компьютерной наукой, IBM не склонна сотрудничать с большим количеством исследовательских групп.

  •  Find the equivalents in two languages (Найдите эквиваленты в двух языках)

4. fault-tolerant                         A. модель выборочного типа

5. sampling model                    B. произвольный доступ

6. random access                      C. базовый метод

7. fuzzy information                 D. нечёткая информация

8. generic method                     E. отказоустойчивый

                                                 F. метод отсечения

  •  Complete the sentences with the proper word (Закончите предложения подходящим по смыслу словом)

9. To overcome NP-hardness the IBM developed good … … .

10. The algorithms are allowed random access to data in the … … .

11. The IBM focuses now on less traditional ways of storing … .

12. It was discovered that the structure of the Web is … .

13. Stochastic models can be used to predict the evolution of the …

14. Algorithms for improving the performance of  large scale databases

are … .

15. Massive data set algorithms have to work with very limited main … .

16. To abstract the connectivity properties of the Web there was proposed the … … .

17. The intrinsic computational difficulty is a field of concern of … … .

  •  Choose the right variant (выберите правильный вариант)

18. The running time of the algorithm is of great importance in

A. sampling model    B. data stream model      C. sublinear model

19. Random access to data is allowed to the algorithm in the

A. sampling model    B. data stream model      C. sublinear model

20.The algorithm can make one or few passes over the data in the

A. sampling model    B. data stream model      C. sublinear model

21. At the moment computers have an advantage of speed but they show no sign of

  1.  Complexity                       C. vitality
  2.  Intelligence                        D. reliability

22. In the future computers may have a similar complexity to the human

A. thoughts                 B. ideas                  C. Brain

23. The problem of computational resources is touched upon in the IBM’s project

A.”algorithms”                      C. “complexity”

B.”web”                                 D. “database principles”

24. The aspect of efficient problem solving is discussed in the IBM’s project

A.”algorithms”                      C. “complexity”

B.”web”                                 D. “database principles

25.To overcome the curse of NP-hardness … algorithms become important.

A. massive data set        B. approximation         C. aggregation


 

А также другие работы, которые могут Вас заинтересовать

61622. Н. Рыленков «К родине» 20.92 KB
  Цель: формировать навыки словесного рисования; развивать внимание к образным средствам языка; учить умению выражать свои чувства по отношению к прочитанному.
61623. РАБОТА С «КАРТИННОЙ ГАЛЕРИЕЙ». АНДРЕЙ РУБЛЕВ «ТРОИЦА» 18.89 KB
  Цель: развивать умение работать в картиной; обогащать словарный запас детей; воспитывать любовь к литературе и искусству, чувство патриотизма. Оборудование: слайд картины, А. Рублева «Троица», диапроектор
61626. ВЫЧИТАНИЕ С ЗАНИМАНИЕМ ЕДИНИЦЫ ЧЕРЕЗ НЕСКОЛЬКО РАЗРЯДОВ ВИДА 30007-648 42.65 KB
  Складываем сотни 8 пишем под сотнями складываем единицы тысяч 2 пишем под единицами тысяч Что общего заметили у остальных выражений в уменьшаемом отсутствуют единицы некоторых разрядов.
61627. Уравнения. Учимся решать уравнения 25.62 KB
  Этапы урока Деятельность учителя Деятельность учащихся Теоретическое обоснование Молодцы А теперь посмотрим на эту таблицу: d 5 4 3 2 1 D5 11D Ребята объясните как изменятся сумма при изменении одного из слагаемых.
61628. Рисуем и измеряем. Продолжаем знакомство 31 KB
  Найдите там задание обозначенное галочкой. Физминутка А теперь берём наши книжки и открываем страницу 46 смотрим на первое задание. На доске буду вывешены фигуры которые нарисованы в книжке эти же фигурки будут у каждого ребёнка на парте...
61630. Умножение многозначного числа на однозначное 18.44 KB
  Цель: учить находить способы определения значений произведений, в которых один множитель – однозначное число, а второй – многозначное.